Uninformed (Blind) Search
Bidirectional Search (BDS)
Bidirectional Search (BDS) is an efficient graph traversal algorithm that conducts two simultaneous searches: one starting from the initial state (forward search) and the other from the goal state (backward search). These searches progress until their respective search trees intersect, signaling that a solution path has been found. By effectively replacing a single large search space with two smaller subgraphs, BDS minimizes the computational overhead, making it an attractive option for navigating vast graphs.
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 to show the tree structure
$vertices = [
'A' => 0, // Root level
'B' => 1, 'E' => 1, // Level 1
'C' => 2, 'D' => 2, 'F' => 1, 'G' => 2, // Level 2
'H' => 3, // Intersection node - Level 3
'I' => 2, // Level 2 from the other direction
'J' => 1, 'K' => 1, // Level 1 from the other direction
'L' => 2, 'M' => 2, 'N' => 2, 'O' => 2 // Level 2 from the other direction
];
// Add vertices with their levels
foreach ($vertices as $vertex => $level) {
$graph->addVertex($vertex, $level);
}
// Add edges to create the exact graph structure
// Left side (from root A)
$graph->addEdge('A', 'E');
$graph->addEdge('E', 'B');
$graph->addEdge('E', 'G');
$graph->addEdge('F', 'C');
$graph->addEdge('F', 'D');
$graph->addEdge('F', 'G');
// Center (where searches will meet)
$graph->addEdge('G', 'H');
// Right side (from goal O)
$graph->addEdge('H', 'I');
$graph->addEdge('I', 'J');
$graph->addEdge('I', 'K');
$graph->addEdge('J', 'L');
$graph->addEdge('J', 'M');
$graph->addEdge('K', 'N');
$graph->addEdge('K', 'O');
// Perform bidirectional search from A to O
echo "Bidirectional Search from A to O:\n";
echo "--------------------------------\n";
$searchResult = $graph->bds('A', 'O');
// Print detailed search results
$graph->printBdsPath($searchResult);
// Let's analyze the intersection at node H
if ($searchResult['success'] && $searchResult['intersectionVertex'] === 'H') {
echo "\nSearch Analysis:\n";
echo "----------------\n";
// Forward search path to H
echo "Forward search path (A → H):\n";
foreach ($searchResult['forwardExplored'] as $node) {
if ($node['vertex'] === 'H') {
echo "→ Reached intersection node H\n";
break;
}
echo "→ {$node['vertex']} (Level {$node['level']})\n";
}
// Backward search path to H
echo "\nBackward search path (O → H):\n";
foreach ($searchResult['backwardExplored'] as $node) {
if ($node['vertex'] === 'H') {
echo "→ Reached intersection node H\n";
break;
}
echo "→ {$node['vertex']} (Level {$node['level']})\n";
}
// Complete path
echo "\nComplete path found (A → O through H):\n";
foreach ($searchResult['path'] as $node) {
echo "→ {$node['vertex']} (Level {$node['level']})";
if ($node['vertex'] === 'H') {
echo " [INTERSECTION]";
}
echo "\n";
}
}
// Verify we have a valid path through H
echo "\nPath verification:\n";
echo "-----------------\n";
if ($searchResult['success']) {
echo "✓ Path successfully found\n";
echo "✓ Intersection occurred at node H\n";
echo "✓ Total nodes in path: " . count($searchResult['path']) . "\n";
} else {
echo "✗ No valid path found\n";
}
Graph:
Starting BDS traversal...
Result:
Memory: 0.082 Mb
Time running: 0.001 sec.
Bidirectional Search from A to O:
--------------------------------
Nodes explored from start (forward direction):
Node: A (Level 0, Direction: forward)
Node: E (Level 1, Direction: forward)
Node: B (Level 1, Direction: forward)
Node: G (Level 2, Direction: forward)
Node: F (Level 1, Direction: forward)
Nodes explored from target (backward direction):
Node: O (Level 2, Direction: backward)
Node: K (Level 1, Direction: backward)
Node: I (Level 2, Direction: backward)
Node: N (Level 2, Direction: backward)
Node: H (Level 3, Direction: backward)
Final path found (intersection at G):
Node: A (Level 0)
Node: E (Level 1)
Node: G (Level 2)
Path verification:
-----------------
✓ Path successfully found
✓ Intersection occurred at node H
✓ Total nodes in path: 3