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.

 
<?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'07.0); // Start node with h=7
$graph->addVertex('A'19.0); // h=9
$graph->addVertex('B'24.0); // h=4
$graph->addVertex('C'32.0); // h=2
$graph->addVertex('D'15.0); // h=5
$graph->addVertex('E'23.0); // h=3
$graph->addVertex('G'40.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:

Starting A* Graph traversal...
Result: Memory: 0.18 Mb Time running: 0.002 sec.
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