AI with PHP Examples (v0.7.0)

Informed (Heuristic) Search

Hill Climbing Search

Show Code

Hill climbing is an iterative optimization technique that attempts to find the best solution by making incremental changes to a given solution, similar to climbing up a hill to reach its peak. The algorithm starts with an initial solution and continuously moves toward better solutions until no further improvements can be made.

 
<?php

use app\classes\search\InformedSearchGraph;

// Create the graph and add vertices with their levels
$graph = new InformedSearchGraph();

// Add all vertices with their heuristic values
// First parameter is vertex name, second is level (optional), third is heuristic value
$graph->addVertex('S', 0, 10.0);  // Start node
$graph->addVertex('A', 1, 8.5);
$graph->addVertex('B', 1, 8.0);
$graph->addVertex('C', 1, 9.0);
$graph->addVertex('D', 2, 7.0);
$graph->addVertex('E', 2, 6.5);
$graph->addVertex('F', 2, 7.5);
$graph->addVertex('H', 3, 5.0);
$graph->addVertex('I', 3, 4.5);
$graph->addVertex('J', 3, 6.0);
$graph->addVertex('K', 4, 3.0);
$graph->addVertex('L', 4, 2.5);
$graph->addVertex('M', 4, 4.0);
$graph->addVertex('N', 3, 5.5);
$graph->addVertex('O', 4, 3.5);
$graph->addVertex('P', 5, 1.5);
$graph->addVertex('Q', 5, 2.0);
$graph->addVertex('G', 6, 0.0);  // Goal node

// Add all edges with their costs
// Main paths
$graph->addEdge('S', 'A', 1.5);
$graph->addEdge('S', 'B', 2.1);
$graph->addEdge('S', 'C', 1.1);
$graph->addEdge('A', 'D', 2.5);
$graph->addEdge('B', 'E', 2.0);
$graph->addEdge('C', 'F', 1.5);
$graph->addEdge('D', 'H', 2.0);
$graph->addEdge('E', 'I', 2.0);
$graph->addEdge('F', 'J', 2.0);
$graph->addEdge('H', 'K', 2.0);
$graph->addEdge('I', 'L', 2.5);
$graph->addEdge('J', 'M', 2.0);
$graph->addEdge('K', 'P', 3.0);
$graph->addEdge('L', 'P', 2.0);
$graph->addEdge('M', 'Q', 2.5);
$graph->addEdge('P', 'G', 2.0);
$graph->addEdge('Q', 'G', 3.0);

// Cross connections
$graph->addEdge('D', 'E', 1.5);
$graph->addEdge('E', 'F', 1.0);
$graph->addEdge('H', 'I', 1.0);
$graph->addEdge('I', 'J', 1.5);
$graph->addEdge('K', 'L', 1.0);
$graph->addEdge('L', 'M', 1.5);
$graph->addEdge('F', 'N', 2.0);
$graph->addEdge('N', 'O', 2.5);
$graph->addEdge('O', 'Q', 2.0);

// Perform hill climbing search from S to G
echo "Performing Hill Climbing Search from S to G:\n";
echo "-------------------------------------------\n\n";

$searchResult = match ($searchType ?? 'simple') {
    'stochastic' => $graph->stochasticHillClimbing('S', 'G'),
    'steepest'   => $graph->steepestAscentHillClimbing('S', 'G'),
    default      => $graph->simpleHillClimbing('S', 'G'),
};

if ($searchResult === null) {
    echo "No path found!\n";
} else {
    echo "[!] Path found using Hill Climbing Search:\n";
    echo "\n\nSearch Analysis:\n";
    echo "---------------\n";
    $graph->searchAnalysis($searchResult);
}

echo "\n\nVerifying Hill Climbing search decisions:\n";
echo "----------------------------------------\n";
$path = match ($searchType ?? 'simple') {
    'stochastic' => $graph->debugStochasticHillClimbing($searchResult, 'S', 'G'),
    'steepest'   => $graph->debugSteepestAscentHillClimbing('S', 'G'),
    default      => $graph->debugSimpleHillClimbing('S', 'G'),
};

Graph:

Starting Hill Climbing traversal...
Search Type:
Result: Memory: 0.196 Mb Time running: 0.002 sec. 
Performing Hill Climbing Search from S to G:
-------------------------------------------

[!] Path found using Hill Climbing Search:


Search Analysis:
---------------
Path sequence:
 -> 
 -> 
 -> 
 -> 
 -> 
 -> 
 -> 

Path analysis:
Step 1: S (level 0, h=10.0) -> A (level 1, h=8.5): cost: 1.5
Step 2: A (level 1, h=8.5) -> D (level 2, h=7.0): cost: 2.5
Step 3: D (level 2, h=7.0) -> H (level 3, h=5.0): cost: 2.0
Step 4: H (level 3, h=5.0) -> K (level 4, h=3.0): cost: 2.0
Step 5: K (level 4, h=3.0) -> P (level 5, h=1.5): cost: 3.0
Step 6: P (level 5, h=1.5) -> G (level 6, h=0.0): cost: 2.0
Step 7: G (level 6, h=0.0)

Total path cost: 13.0


Verifying Hill Climbing search decisions:
----------------------------------------

=== Simple Hill Climbing Debug ===
Starting from S to reach G

Initial state:
Vertex: S
Level: 0
Heuristic: 10

----------------------------
Current path: S
At vertex: S (h=10)
  Evaluating A:
    Heuristic: 8.5
    Edge cost: 1.5
    Current best: 10
  → Better neighbor found: A

----------------------------
Current path: S -> A
At vertex: A (h=8.5)
  Evaluating D:
    Heuristic: 7
    Edge cost: 2.5
    Current best: 8.5
  → Better neighbor found: D

----------------------------
Current path: S -> A -> D
At vertex: D (h=7)
  Evaluating H:
    Heuristic: 5
    Edge cost: 2
    Current best: 7
  → Better neighbor found: H

----------------------------
Current path: S -> A -> D -> H
At vertex: H (h=5)
  Evaluating K:
    Heuristic: 3
    Edge cost: 2
    Current best: 5
  → Better neighbor found: K

----------------------------
Current path: S -> A -> D -> H -> K
At vertex: K (h=3)
  Evaluating P:
    Heuristic: 1.5
    Edge cost: 3
    Current best: 3
  → Better neighbor found: P

----------------------------
Current path: S -> A -> D -> H -> K -> P
At vertex: P (h=1.5)
  Evaluating G:
    Heuristic: 0
    Edge cost: 2
    Current best: 1.5
  → Better neighbor found: G

Goal reached!
Final path: 
 ->  ->  ->  ->  ->  -> 
Total cost: 13