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.

 
<?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