2
$\begingroup$

I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material:

I understand that with search-methods like e.g. beam search, hill-climbing... you can search based on a certain knowledge about the problem which can tell you in each state an approximation off how close you are to finding the solution. Currently I've reached a chapter about Optimal Search algorithms. An important algorithm in that chapter is Uniform Cost which is based on the lowest accumulated "travel-cost", with as desired consequence that the algorithm will reach a solution in a branch with the lowest accumulated travel cost. Now, I don't understand that travel cost and how it differs from a normal heuristic value. Can someone explain the difference and how it effects finding a solution?

$\endgroup$
  • 1
    $\begingroup$ Where have you looked? What self-study have you done? Have you looked at some examples of Uniform Cost Search? $\endgroup$ – D.W. Jan 15 '16 at 23:33
  • $\begingroup$ Hill climbing is local optimum, not global - if by certain knowledge you mean good starting point, or you provide something in advance (step size?) otherwise it is not heuristic and tells you nothing about how close you are to solution, just how optimal so far you got. $\endgroup$ – Evil Jan 16 '16 at 1:04
2
$\begingroup$

Uniform Cost Search (UCS) does not have a heuristic value and doesn't rely on a heuristic function. I suspect you're getting it confused with some other algorithm (e.g., A*). In Uniform Cost Search, there's no heuristic: we know exactly what the distance from the starting point was, and we use that to determine which nodes to expand.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.