1
$\begingroup$

So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least distance to retrieve the objects and finally go to the cashier register?

I could only find a brute force method of finding optimal path of each permutation of paths and seeing which overall distance covers the least traversing. But this implementation is O(n!). Is there a more efficient approach?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Travelling_salesman_problem $\endgroup$ – François Aug 14 '15 at 7:40
  • $\begingroup$ @François so there is not way to solve it better than exponential time? $\endgroup$ – Armon Safai Aug 14 '15 at 8:57
  • $\begingroup$ It depends on the possible super market topologies. If it's still a corridor and if objects positions are integers, then you can solve your problem in linear time. $\endgroup$ – François Aug 14 '15 at 15:21
  • $\begingroup$ @François well its no A corridor. I'm assuming multiple corridors (or isles). $\endgroup$ – Armon Safai Aug 14 '15 at 20:43
  • $\begingroup$ If an approach solution is ok for you, you can look at cs.brown.edu/~pnk/publications/tsp2005.pdf $\endgroup$ – François Aug 15 '15 at 8:04

Your Answer

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

Browse other questions tagged or ask your own question.