Informed (Heuristic) Search

Hill Climbing Search

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.

Example of use


<?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.194 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