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.
Example of use
<?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