Uninformed (Blind) Search

Depth-Limited Search (DFS)

The Depth-Limited Search (DLS) algorithm is an extension of the Depth-First Search (DFS) algorithm, designed to address the challenge of infinite paths in certain problem spaces. DLS introduces a predetermined depth limit to the search process, treating nodes at this limit as though they have no successors. By constraining the depth, DLS avoids the pitfalls of exploring infinite paths while maintaining the advantages of depth-first traversal.

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);  // Start node at level 0
$graph->addVertex('A', 1);
$graph->addVertex('B', 1);
$graph->addVertex('C', 2);
$graph->addVertex('D', 2);
$graph->addVertex('I', 2);
$graph->addVertex('J', 2);
$graph->addVertex('E', 3);
$graph->addVertex('F', 3);
$graph->addVertex('G', 3);
$graph->addVertex('H', 3);

// Add edges according to the graph structure
$graph->addEdge('S', 'A');
$graph->addEdge('S', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('A', 'D');
$graph->addEdge('B', 'I');
$graph->addEdge('B', 'J');
$graph->addEdge('C', 'E');
$graph->addEdge('C', 'F');
$graph->addEdge('D', 'G');
$graph->addEdge('I', 'H');

// Try DLS with different depth limits
$depths = [1, 2, 3];

echo "DLS traversal starting from vertex 'S':\n";
echo "--------------------------------------\n";

foreach ($depths as $maxDepth) {
    echo "\nTrying DLS with max depth = $maxDepth to find node 'J':\n";
    $searchResult = $graph->dls('S', $maxDepth, 'J');

    echo $searchResult['found']
        ? "✓ Target 'J' found within depth limit!\n"
        : "✗ Target 'J' not found within depth limit of {$searchResult['maxDepth']}\n";

    echo "Path explored:\n";
    foreach ($searchResult['path'] as $node) {
        echo sprintf("  Node: %s (Level %d, Search Depth %d)\n",
            $node['vertex'],
            $node['level'],
            $node['depth']
        );
    }
}

Graph:

Starting DLS traversal with max depth = 2...

Result: Memory: 0.088 Mb Time running: < 0.001 sec.


                DLS traversal starting from vertex 'S':
--------------------------------------

Trying DLS with max depth = 1 to find node 'J':
✗ Target 'J' not found within depth limit of 1
Path explored:
  Node: S (Level 0, Search Depth 0)
  Node: A (Level 1, Search Depth 1)
  Node: B (Level 1, Search Depth 1)

Trying DLS with max depth = 2 to find node 'J':
✓ Target 'J' found within depth limit!
Path explored:
  Node: S (Level 0, Search Depth 0)
  Node: A (Level 1, Search Depth 1)
  Node: C (Level 2, Search Depth 2)
  Node: D (Level 2, Search Depth 2)
  Node: B (Level 1, Search Depth 1)
  Node: I (Level 2, Search Depth 2)
  Node: J (Level 2, Search Depth 2)

Trying DLS with max depth = 3 to find node 'J':
✓ Target 'J' found within depth limit!
Path explored:
  Node: S (Level 0, Search Depth 0)
  Node: A (Level 1, Search Depth 1)
  Node: C (Level 2, Search Depth 2)
  Node: E (Level 3, Search Depth 3)
  Node: F (Level 3, Search Depth 3)
  Node: D (Level 2, Search Depth 2)
  Node: G (Level 3, Search Depth 3)
  Node: B (Level 1, Search Depth 1)
  Node: I (Level 2, Search Depth 2)
  Node: H (Level 3, Search Depth 3)
  Node: J (Level 2, Search Depth 2)