Informed (Heuristic) Search
A* Tree Search
A* Tree Search, commonly referred to as A* Search, is a widely used pathfinding and graph traversal algorithm. It builds on the strengths of
uniform-cost search and greedy search, offering a robust mechanism for finding the most cost-effective path from a starting node to a goal
node.
A* uses a heuristic function, $f(x) = g(x) + h(x)$, where is the cumulative cost to reach the current node, and is an estimated cost to reach the goal from the
current node. This balance between actual cost and estimated cost makes A* one of the most efficient search algorithms in many applications,
including game development, robotics, and network optimization.
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 heuristic values (h)
$graph->addVertex('S', 0, 7.0); // Start node with h=7
$graph->addVertex('A', 1, 9.0); // h=9
$graph->addVertex('B', 2, 4.0); // h=4
$graph->addVertex('C', 3, 2.0); // h=2
$graph->addVertex('D', 1, 5.0); // h=5
$graph->addVertex('E', 2, 3.0); // h=3
$graph->addVertex('G', 4, 0.0); // Goal node with h=0
// Add edges with costs as shown in the image
$graph->addEdge('S', 'A', 3.0);
$graph->addEdge('S', 'D', 2.0);
$graph->addEdge('A', 'B', 1.0);
$graph->addEdge('B', 'G', 5.0);
$graph->addEdge('D', 'E', 4.0);
$graph->addEdge('D', 'B', 1.0);
$graph->addEdge('B', 'C', 2.0);
$graph->addEdge('B', 'E', 1.0);
$graph->addEdge('E', 'G', 3.0);
$graph->addEdge('C', 'G', 4.0);
// Run A* Tree Search
echo "Performing A* Tree Search from S to G:\n";
echo "-------------------------------------\n\n";
$searchResult = $graph->aStarTreeSearch('S', 'G');
if ($searchResult !== null) {
$graph->printPath($searchResult);
} else {
echo "No path found!\n";
}
Graph:
Performing A* Tree 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