Uninformed (Blind) Search
Uniform Cost Search (UCS)
Uniform Cost Search (UCS) is a fundamental algorithm widely used in artificial intelligence for traversing weighted trees or graphs. It is designed to handle situations where each edge has a different cost, aiming to find the path to the goal node with the lowest cumulative cost. UCS achieves this by expanding nodes based on their path costs, starting from the root node.
Example of use
<?php
// Create the graph and add vertices with their levels
use app\classes\search\UninformedSearchGraph;
$graph = new UninformedSearchGraph();
// Add all vertices with their respective levels
$graph->addVertex('S', 0); // Starting node at level 0
$graph->addVertex('A', 1);
$graph->addVertex('B', 1);
$graph->addVertex('C', 2);
$graph->addVertex('D', 2);
$graph->addVertex('E', 3);
$graph->addVertex('F', 3);
$graph->addVertex('G', 4); // There are multiple G nodes in different levels, but we'll use the target G
// Add edges with their weights according to the diagram
$graph->addEdge('S', 'A', 1);
$graph->addEdge('S', 'B', 4);
$graph->addEdge('A', 'C', 3);
$graph->addEdge('A', 'D', 2);
$graph->addEdge('B', 'G', 5);
$graph->addEdge('C', 'E', 5);
$graph->addEdge('D', 'F', 4);
$graph->addEdge('D', 'G', 3);
$graph->addEdge('E', 'G', 5);
// Perform UCS from S to G
echo "UCS traversal starting from vertex 'S':\n";
echo "--------------------------------------\n";
$searchResult = $graph->ucs('S', 'G');
// Print the result
echo "\nUCS Path Result:\n";
$graph->printUcsPath($searchResult);
echo "\nThe output should show S -> A -> D -> G as the optimal path";
echo "\nwith a total cost of 1 + 2 + 3 = 6";
Graph:
Starting UCS traversal...
Result:
Memory: 0.077 Mb
Time running: 0.002 sec.
UCS traversal starting from vertex 'S':
--------------------------------------
UCS Path Result:
Nodes explored during UCS (in order of exploration):
Node: S (Level 0, Cost 0.00)
Node: A (Level 1, Cost 1.00)
Node: D (Level 2, Cost 3.00)
Node: B (Level 1, Cost 4.00)
Node: C (Level 2, Cost 4.00)
Node: G (Level 4, Cost 6.00)
Optimal path found:
Node: S (Level 0, Cost 0.00)
Node: A (Level 1, Cost 1.00)
Node: D (Level 2, Cost 3.00)
Node: G (Level 4, Cost 6.00)
Total Cost: 6.00
The output should show S -> A -> D -> G as the optimal path
with a total cost of 1 + 2 + 3 = 6