CODEWITHSUNDEEP
algorithmartificial-intelligenceinfinite-loopgraph-algorithm
CodyBugstein
CodyBugstein

Reputation: 23322

Finding a path with Steepest Hill Climbing Function

When using Steepest Hill Climbing Search, what happens when you reach an infinite loop - that is, you find yourself going back and forth between the same two states because they are both the best successors to eachother?

For example, in the graph below, (J) will go to (K) and vice versa repeatedly. If I was programming it, I guess I would put some sort of flag on the visited states so I know if I'm revisiting the same one. However, there is no mention of this in the documentation (i.e here, here) about the Steepest Hill Climbing algorithm.

Steepest Hill Climbing graph search

Upvotes: 0

Views: 4428

Answers (2)

Ishaan Rastogi
Ishaan Rastogi

Reputation: 21

In this question, we can see the starting node as A and ending node as M, that's one thing.

  • Starting with node A, we have total heuristic value sum as 7 at the moment, taking the branch with smallest heuristic value (that's C), now the heuristic, again after arriving at the node C we check for the smallest heuristic value, that's node G and not J since node J doesn't connect the Final Node M, therefore we take node G instead.
  • After that we arrive at node M, i.e. goal node. and the steepest hill climb is complete.

We have the total heuristic sum as: (7+3+3+0) = 13.

Route Followed here: A->C->G->M

Upvotes: 2

David Eisenstat
David Eisenstat

Reputation: 65447

If it's pure hill climbing, then you ignore non-improving moves, and there are no cycles. If it's supposed to be finding the global optimum, then there should be some other mechanism for escaping local maxima (random moves, restarts, etc.).

Upvotes: 3

Related Questions