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.121 Mb Time running: 0.001 sec.


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

Random Search did not find target.
Total steps taken: 100/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 S (Level 0, Visits: 1)
Step 5: Node B (Level 1, Visits: 2)
Step 6: Node H (Level 2, Visits: 1)
Step 7: Node B (Level 1, Visits: 3)
Step 8: Node H (Level 2, Visits: 2)
Step 9: Node B (Level 1, Visits: 4)
Step 10: Node G (Level 2, Visits: 0)
Step 11: Node B (Level 1, Visits: 5)
Step 12: Node S (Level 0, Visits: 2)
Step 13: Node B (Level 1, Visits: 6)
Step 14: Node G (Level 2, Visits: 1)
Step 15: Node I (Level 3, Visits: 0)
Step 16: Node G (Level 2, Visits: 2)
Step 17: Node I (Level 3, Visits: 1)
Step 18: Node G (Level 2, Visits: 3)
Step 19: Node I (Level 3, Visits: 2)
Step 20: Node G (Level 2, Visits: 4)
Step 21: Node I (Level 3, Visits: 3)
Step 22: Node G (Level 2, Visits: 5)
Step 23: Node B (Level 1, Visits: 7)
Step 24: Node H (Level 2, Visits: 3)
Step 25: Node B (Level 1, Visits: 8)
Step 26: Node H (Level 2, Visits: 4)
Step 27: Node B (Level 1, Visits: 9)
Step 28: Node S (Level 0, Visits: 3)
Step 29: Node B (Level 1, Visits: 10)
Step 30: Node S (Level 0, Visits: 4)
Step 31: Node B (Level 1, Visits: 11)
Step 32: Node G (Level 2, Visits: 6)
Step 33: Node I (Level 3, Visits: 4)
Step 34: Node G (Level 2, Visits: 7)
Step 35: Node B (Level 1, Visits: 12)
Step 36: Node H (Level 2, Visits: 5)
Step 37: Node B (Level 1, Visits: 13)
Step 38: Node G (Level 2, Visits: 8)
Step 39: Node I (Level 3, Visits: 5)
Step 40: Node G (Level 2, Visits: 9)
Step 41: Node B (Level 1, Visits: 14)
Step 42: Node H (Level 2, Visits: 6)
Step 43: Node B (Level 1, Visits: 15)
Step 44: Node H (Level 2, Visits: 7)
Step 45: Node B (Level 1, Visits: 16)
Step 46: Node S (Level 0, Visits: 5)
Step 47: Node B (Level 1, Visits: 17)
Step 48: Node H (Level 2, Visits: 8)
Step 49: Node B (Level 1, Visits: 18)
Step 50: Node G (Level 2, Visits: 10)
Step 51: Node B (Level 1, Visits: 19)
Step 52: Node S (Level 0, Visits: 6)
Step 53: Node A (Level 1, Visits: 0)
Step 54: Node S (Level 0, Visits: 7)
Step 55: Node A (Level 1, Visits: 1)
Step 56: Node S (Level 0, Visits: 8)
Step 57: Node A (Level 1, Visits: 2)
Step 58: Node D (Level 2, Visits: 0)
Step 59: Node A (Level 1, Visits: 3)
Step 60: Node S (Level 0, Visits: 9)
Step 61: Node A (Level 1, Visits: 4)
Step 62: Node C (Level 2, Visits: 0)
Step 63: Node A (Level 1, Visits: 5)
Step 64: Node D (Level 2, Visits: 1)
Step 65: Node A (Level 1, Visits: 6)
Step 66: Node D (Level 2, Visits: 2)
Step 67: Node A (Level 1, Visits: 7)
Step 68: Node C (Level 2, Visits: 1)
Step 69: Node A (Level 1, Visits: 8)
Step 70: Node S (Level 0, Visits: 10)
Step 71: Node B (Level 1, Visits: 20)
Step 72: Node H (Level 2, Visits: 9)
Step 73: Node B (Level 1, Visits: 21)
Step 74: Node G (Level 2, Visits: 11)
Step 75: Node B (Level 1, Visits: 22)
Step 76: Node G (Level 2, Visits: 12)
Step 77: Node I (Level 3, Visits: 6)
Step 78: Node G (Level 2, Visits: 13)
Step 79: Node B (Level 1, Visits: 23)
Step 80: Node G (Level 2, Visits: 14)
Step 81: Node I (Level 3, Visits: 7)
Step 82: Node G (Level 2, Visits: 15)
Step 83: Node B (Level 1, Visits: 24)
Step 84: Node S (Level 0, Visits: 11)
Step 85: Node B (Level 1, Visits: 25)
Step 86: Node H (Level 2, Visits: 10)
Step 87: Node B (Level 1, Visits: 26)
Step 88: Node G (Level 2, Visits: 16)
Step 89: Node B (Level 1, Visits: 27)
Step 90: Node H (Level 2, Visits: 11)
Step 91: Node B (Level 1, Visits: 28)
Step 92: Node G (Level 2, Visits: 17)
Step 93: Node I (Level 3, Visits: 8)
Step 94: Node G (Level 2, Visits: 18)
Step 95: Node I (Level 3, Visits: 9)
Step 96: Node G (Level 2, Visits: 19)
Step 97: Node I (Level 3, Visits: 10)
Step 98: Node G (Level 2, Visits: 20)
Step 99: Node B (Level 1, Visits: 29)
Step 100: Node G (Level 2, Visits: 21)

Visit counts:
Node S: visited 12 times
Node B: visited 30 times
Node H: visited 12 times
Node G: visited 21 times
Node I: visited 11 times
Node A: visited 9 times
Node D: visited 3 times
Node C: visited 2 times