AI with PHP Examples (v0.5.0)

Uninformed (Blind) Search

Random Walk Search (RWS)

Show Code

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