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.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