CODEWITHSUNDEEP
algorithmartificial-intelligencecomputer-science
Strin
Strin

Reputation: 677

How to define the completeness of stochastic search problems?

Can we just define it to be the search with the probability limit of find a solution to be 1?

Upvotes: 0

Views: 849

Answers (1)

amit
amit

Reputation: 178431

short answer: yes

longer answer: In order to claim a search algorithm [even stochastic] is "complete" you must show that if there is an answer, the algorithm will find an answer, in a finite time. This means, you must show that if there is an answer, there cannot be, with any probability, a non-finishing [or finishing with wrong answer] path. So, you need to show that a solution will be found with probability 1 [exactly! not approximately!], to show a stochastic algorithm is "complete"

For example, steepest ascent hill climbing with side walks [you can go to a neighbor with the same utility value] - is not complete, since you can enter an infinite loop and never find any solution. However, if you limit the number of side walks to a finite number K, it is complete, because if there is a local minimum, eventually the algorithm will find one, with probability 1.

Upvotes: 1

Related Questions