Skip to main content
6 votes
Accepted

Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?

Let's consider a problem where all edge costs are greater than zero, but not above some $\epsilon$: Image a problem where we have an infinite path where the first edge is cost $\frac{1}{2}$, the next ...
Nathan S.'s user avatar
  • 371
1 vote
Accepted

Are hill climbing variations always optimal and complete?

No, they are prone to get stuck in local maxima, unless the whole search space is investigated. A simple algorithm will only ever move upwards; if you imagine you're in a mountain range, this will not ...
Oliver Mason's user avatar
  • 5,397

Only top scored, non community-wiki answers of a minimum length are eligible