Informed (Heuristic) Search
A* Graph Search
A* Graph Search is an enhancement of the A* Tree Search algorithm, designed to optimize its efficiency by addressing a key limitation: the
re-exploration of nodes. In tree search, the same node can be expanded multiple times across different branches, wasting time and
computational resources.
A* Graph Search mitigates this issue by introducing a critical rule: a node is not expanded more than once. This improvement allows the
algorithm to explore paths more efficiently while retaining the benefits of A*’s heuristic-based approach.
Example of use
<?php
use app\classes\search\InformedSearchGraph;
// Create the graph and add vertices with their levels
$graph = new InformedSearchGraph();
// Add vertices with their levels and heuristic values
$graph->addVertex('S', 0, 7); // Start node
$graph->addVertex('A', 1, 9);
$graph->addVertex('D', 1, 5);
$graph->addVertex('B', 2, 4);
$graph->addVertex('E', 2, 3);
$graph->addVertex('C', 3, 2);
$graph->addVertex('G1', 4, 0); // First G node (from C)
$graph->addVertex('G2', 3, 0); // Second G node (from E)
$graph->addVertex('G', 4, 0); // Third G node (from E)
// Add edges with their costs
$graph->addEdge('S', 'A', 3);
$graph->addEdge('S', 'D', 2);
$graph->addEdge('D', 'B', 1);
$graph->addEdge('D', 'E', 4);
$graph->addEdge('B', 'C', 2);
$graph->addEdge('B', 'E', 1);
$graph->addEdge('C', 'G1', 4); // Path to first G
$graph->addEdge('E', 'G2', 3); // Path to second G
$graph->addEdge('E', 'G', 3); // Path to third G (the one highlighted in orange)
// Find path using A* Group search to G3 (the highlighted goal node)
echo "Performing A* Group Search from S to G:\n";
echo "---------------------------------------\n\n";
$searchResult = $graph->aStarGroupSearch('S', 'G');
if ($searchResult !== null) {
$graph->printPath($searchResult);
} else {
echo "No path found!\n";
}
Graph:
Starting A* Graph traversal...
Result:
Memory: 0.179 Mb
Time running: 0.002 sec.
Performing A* Group Search from S to G:
---------------------------------------
Node: S (Level 0, h=7.0)
Edge cost from S to D: 2.0
Node: D (Level 1, h=5.0)
Edge cost from D to B: 1.0
Node: B (Level 2, h=4.0)
Edge cost from B to E: 1.0
Node: E (Level 2, h=3.0)
Edge cost from E to G: 3.0
Node: G (Level 4, h=0.0)
Total path cost: 7.0