Informed (Heuristic) Search

Beam Search

Beam Search is a heuristic search algorithm designed to balance memory consumption and search efficiency in graph-based problems. It is an optimization of the best-first search algorithm, but with a key difference: it retains only a limited number of “best” nodes, referred to as the beam width (β), at each level of the search tree. While it sacrifices completeness and optimality, Beam Search is particularly effective in domains where memory limitations or large search spaces make exhaustive search impractical.

The algorithm works by employing a breadth-first search approach, expanding nodes level by level. At each level, it evaluates all successors of the current states, sorts them by a heuristic cost function, and retains only the top β nodes. This makes it a greedy algorithm, focusing only on the most promising paths at any given time.

 
<?php

use app\classes\search\InformedSearchGraph;

// Create the graph and add vertices with their levels
$graph = new InformedSearchGraph();

// Add vertices with their levels and heuristic values
// Format: vertex name, level, heuristic value
$graph->addVertex('A'00);  // Start node
$graph->addVertex('B'11);
$graph->addVertex('C'12);
$graph->addVertex('D'13);
$graph->addVertex('E'23);
$graph->addVertex('F'21);
$graph->addVertex('G'30);  // Goal node, h=0

// Add edges with their costs
// From level 0 to level 1
$graph->addEdge('A''B'2.0);
$graph->addEdge('A''C'1.0);
$graph->addEdge('A''D'2.0);

// From level 1 to level 2
$graph->addEdge('B''E'3.0);
$graph->addEdge('C''F'2.0);

// From level 2 to level 3 (goal)
$graph->addEdge('E''G'4.0);
$graph->addEdge('F''G'3.0);
$graph->addEdge('D''G'3.0);

// Try different beam widths
$beamWidths = [123];

// Perform greedy search from S to G
echo "Performing Beam Search from A to G:\n";
echo 
"------------------------------------\n\n";

// Init beam
$beam ??= 1;

foreach (
$beamWidths as $width) {
    
// Show only specified width
    
if ($width != $beam){
        continue;
    }

    
$searchResult $graph->beamSearch('A''G'$width);

    if (
$searchResult === null) {
        echo 
"No path found!\n";
    } else {
        echo 
"[!] Path found using Beam Search (width = $width):\n";
        echo 
"\n\nSearch Analysis:\n";
        echo 
"---------------\n";
        
$graph->searchAnalysis($searchResult);
    }
}

Graph:

Starting Beam traversal...
Beam Width:

Result: Memory: 0.18 Mb Time running: 0.001 sec.
Performing Beam Search from A to G:
------------------------------------

[!] Path found using Beam Search (width = 1):


Search Analysis:
---------------
Path sequence:
 -> 
 -> 
 -> 
 -> 

Path analysis:
Step 1: A (level 0, h=0.0) -> B (level 1, h=1.0): cost: 2.0
Step 2: B (level 1, h=1.0) -> E (level 2, h=3.0): cost: 3.0
Step 3: E (level 2, h=3.0) -> G (level 3, h=0.0): cost: 4.0
Step 4: G (level 3, h=0.0)

Total path cost: 9.0