23. AI using Python | Randomized Search Methods |Random Walk Algorithm |by Sunil Sir

Randomized Search Algorithms
1. Random Walk (RW) Algorithm

2. Analysis of RW
------------
The Iterated Hill Climbing (IHC) randomly selects different stating points with the intention that at least one of the solutions from these starting point will be the global optima. IHC is partially random in nature.

The Random Walk (RW) on the other hand is completely random in nature and randomly selects stating points in each step of each iteration without bothering of the gradient.

The RW thus uses exploration approach while utilizing the search space.
----------
Def MOVEGEN(Node)
Succ ={}
For Node in S do
Succ= Succ U {Children of Node}
Return Succ

Def h(Node)
Return (Heuristic value of Node)



Def Random_Walk(Start, n)
node=random candidate solution or Start Node
bestNode=node
For i= 1 to n do
Child = {MOVEGEN(node)}
if (Child list not Empty) then
node=random(Child)
if (h(node) GREATER-THAN h(bestNode)) then
bestNode=node
Return bestNode

-----------
Analysis:


1. Completeness: The RW guarantees the solution if randomly selected starting points lie in the global optimal region.

2. Optimality: The solution given by RW is optimal if randomly selected starting points lie in the global optimal region.

3. Time Complexity: If the randomly selected point lies in the global optimal region and the heuristic function is properly defined then search will take a linear time.

4. Space Complexity: linear Space across the path while finding solution.