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.081 Mb
Time running: 0.002 sec.
RWS traversal starting from vertex 'S':
--------------------------------------
Random Search found target!
Total steps taken: 14/100
Path taken:
Step 0: Node S (Level 0, Visits: 0)
Step 1: Node B (Level 1, Visits: 0)
Step 2: Node H (Level 2, Visits: 0)
Step 3: Node B (Level 1, Visits: 1)
Step 4: Node H (Level 2, Visits: 1)
Step 5: Node B (Level 1, Visits: 2)
Step 6: Node G (Level 2, Visits: 0)
Step 7: Node B (Level 1, Visits: 3)
Step 8: Node S (Level 0, Visits: 1)
Step 9: Node B (Level 1, Visits: 4)
Step 10: Node S (Level 0, Visits: 2)
Step 11: Node A (Level 1, Visits: 0)
Step 12: Node C (Level 2, Visits: 0)
Step 13: Node E (Level 3, Visits: 0)
Step 14: Node K (Level 4, Visits: 0)
Visit counts:
Node S: visited 3 times
Node B: visited 5 times
Node H: visited 2 times
Node G: visited 1 times
Node A: visited 1 times
Node C: visited 1 times
Node E: visited 1 times