1
$\begingroup$

The aim is to guide a bot from Source S to Goal G while passing through all the checkpoints @ (in any order).

########
#@....G#
##.##@##
#..@..S#
#@.....#
########

One way to solve it would be to select one checkpoint as goal from current state and then guide the bot to it. Then select the next checkpoint as goal and current checkpoint as source and guide the bot to its new goal. Eventually guide it to the state G from the last checkpoint.

But this technique relies heavily on the order of checkpoints traversed.

I would like to know if a good heuristic can be found to decide which checkpoint to go to next?

$\endgroup$
  • 1
    $\begingroup$ If you're not particularly asking for a robot to do it, stackoverflow would give you much better answers. $\endgroup$ – Shahbaz Aug 24 '14 at 7:12
2
$\begingroup$

This type of problem is called the travelling salesman problem, which is a heavily studied problem. The wikipedia entry lists a few heuristics in the middle.

| improve this answer | |
$\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.