Uninformed (Blind) Search

Iterative Deepening Depth-First Search (IDDFS)

The Iterative Deepening Depth-First Search (IDDFS) algorithm combines the strengths of two fundamental search algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS). This hybrid approach balances memory efficiency with optimality by progressively exploring deeper levels of the search space. Unlike traditional DFS, which dives to the maximum depth at once, or BFS, which requires significant memory to maintain a queue of explored nodes, IDDFS systematically increases the search depth, ensuring thorough exploration while minimizing resource usage.

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('E', 2);
$graph->addVertex('F', 2);  // Target node
$graph->addVertex('G', 3);
$graph->addVertex('H', 3);
$graph->addVertex('I', 3);
$graph->addVertex('J', 3);

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

// Perform IDDFS to find node 'F'
echo "Performing IDDFS to find node 'F':\n";
echo "---------------------------------\n";

$searchResult = $graph->iddfs('S', 'F');

// Output the DFS traversal
echo "\nSearch Results:\n";
echo "Target found: " . ($searchResult['success'] ? "Yes" : "No") . "\n";
echo "Final depth: " . $searchResult['final_depth'] . "\n\n";

// Print paths explored at each depth
foreach ($searchResult['paths'] as $depthResult) {
    echo "Depth " . $depthResult['depth_limit'] . ":\n";
    foreach ($depthResult['path'] as $node) {
        echo sprintf("  Node: %s (Level %d)\n",
            $node['vertex'],
            $node['level']
        );
    }
    echo "  Found: " . ($depthResult['found'] ? "Yes" : "No") . "\n\n";
}

// Example output for comparison with BFS
echo "BFS traversal for comparison:\n";
$bfsPath = $graph->bfs('S');
$graph->printPath($bfsPath);
echo "\n";

// Example output for comparison with DFS
echo "DFS traversal for comparison:\n";
$dfsPath = $graph->dfs('S', 'F');
$graph->printPath($dfsPath);

Graph:

Starting IDDFS traversal...

Result: Memory: 0.095 Mb Time running: 0.002 sec.


                Performing IDDFS to find node 'F':
---------------------------------

Search Results:
Target found: Yes
Final depth: 2

Depth 0:
  Node: S (Level 0)
  Found: No

Depth 1:
  Node: S (Level 0)
  Node: A (Level 1)
  Node: B (Level 1)
  Found: No

Depth 2:
  Node: S (Level 0)
  Node: A (Level 1)
  Node: C (Level 2)
  Node: D (Level 2)
  Node: B (Level 1)
  Node: E (Level 2)
  Node: F (Level 2)
  Found: Yes

BFS traversal for comparison:
Node: S (Level 0)
Node: A (Level 1)
Node: B (Level 1)
Node: C (Level 2)
Node: D (Level 2)
Node: E (Level 2)
Node: F (Level 2)
Node: G (Level 3)
Node: H (Level 3)
Node: I (Level 3)
Node: J (Level 3)

DFS traversal for comparison:
Node: S (Level 0)
Node: A (Level 1)
Node: C (Level 2)
Node: G (Level 3)
Node: H (Level 3)
Node: D (Level 2)
Node: I (Level 3)
Node: B (Level 1)
Node: E (Level 2)
Node: J (Level 3)
Node: F (Level 2)