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.
Example of use
<?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', 0, 0); // Start node
$graph->addVertex('B', 1, 1);
$graph->addVertex('C', 1, 2);
$graph->addVertex('D', 1, 3);
$graph->addVertex('E', 2, 3);
$graph->addVertex('F', 2, 1);
$graph->addVertex('G', 3, 0); // 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 = [1, 2, 3];
// 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:
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