Uninformed (Blind) Search

Random Walk Search (RWS)

The Random Walk Search algorithm is a fundamental search strategy where a search agent randomly selects and moves to a neighboring node without maintaining a history of past states. This approach is often used in scenarios where structured search methods are either infeasible or inefficient due to an unknown or highly complex search space.

 
<?php

// Create new graph instance
use app\classes\search\UninformedSearchGraph;

$graph = new UninformedSearchGraph();

// Add vertices with their levels
$graph->addVertex('S'0);  // Start node (level 0)
$graph->addVertex('A'1);  // Level 1
$graph->addVertex('B'1);  // Level 1
$graph->addVertex('C'2);  // Level 2
$graph->addVertex('D'2);  // Level 2
$graph->addVertex('G'2);  // Level 2
$graph->addVertex('H'2);  // Level 2
$graph->addVertex('E'3);  // Level 3
$graph->addVertex('F'3);  // Level 3
$graph->addVertex('I'3);  // Level 3
$graph->addVertex('K'4);  // Level 4 (target node)

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

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

// Perform random search from S to K - 100 steps maximum
$searchResult $graph->rws('S''K'100);
$graph->printRwsPath($searchResult);

Graph:

Starting RWS traversal...
Result: Memory: 0.089 Mb Time running: 0.001 sec.
RWS traversal starting from vertex 'S':
--------------------------------------

Random Search found target!
Total steps taken: 32/100

Path taken:
Step 0: Node S (Level 0, Visits: 0)
Step 1: Node A (Level 1, Visits: 0)
Step 2: Node C (Level 2, Visits: 0)
Step 3: Node A (Level 1, Visits: 1)
Step 4: Node S (Level 0, Visits: 1)
Step 5: Node A (Level 1, Visits: 2)
Step 6: Node D (Level 2, Visits: 0)
Step 7: Node A (Level 1, Visits: 3)
Step 8: Node S (Level 0, Visits: 2)
Step 9: Node A (Level 1, Visits: 4)
Step 10: Node D (Level 2, Visits: 1)
Step 11: Node A (Level 1, Visits: 5)
Step 12: Node C (Level 2, Visits: 1)
Step 13: Node E (Level 3, Visits: 0)
Step 14: Node C (Level 2, Visits: 2)
Step 15: Node A (Level 1, Visits: 6)
Step 16: Node D (Level 2, Visits: 2)
Step 17: Node A (Level 1, Visits: 7)
Step 18: Node C (Level 2, Visits: 3)
Step 19: Node A (Level 1, Visits: 8)
Step 20: Node D (Level 2, Visits: 3)
Step 21: Node A (Level 1, Visits: 9)
Step 22: Node D (Level 2, Visits: 4)
Step 23: Node A (Level 1, Visits: 10)
Step 24: Node C (Level 2, Visits: 4)
Step 25: Node A (Level 1, Visits: 11)
Step 26: Node S (Level 0, Visits: 3)
Step 27: Node A (Level 1, Visits: 12)
Step 28: Node D (Level 2, Visits: 5)
Step 29: Node A (Level 1, Visits: 13)
Step 30: Node C (Level 2, Visits: 5)
Step 31: Node E (Level 3, Visits: 1)
Step 32: Node K (Level 4, Visits: 0)

Visit counts:
Node S: visited 4 times
Node A: visited 14 times
Node C: visited 6 times
Node D: visited 6 times
Node E: visited 2 times