-1

I have a NxN table, let's say 5 times 5, in which given a point A at random position and unknown number of point Bs:

+---+---+---+---+---+
| B |   |   |   |   |
+---+---+---+---+---+
|   | A |   |   | B |
+---+---+---+---+---+
|   |   | B |   |   |
+---+---+---+---+---+
|   |   |   | B |   |
+---+---+---+---+---+
| B |   |   | B |   |
+---+---+---+---+---+

From point A, is there any way to find the shortest way to pass through all points B?

The same question has been asked here and I've done several researches about the travelling salesman problem. However, the approach to the solution on graph and on a table-like is different, as I can't determine the length between 2 slots, and on this table-like graph, A can only move up/down/left/right. Also, wiki doesn't break down to details of how the algorithm works or how to translate it into programming rather than Math operations all the way. I am stuck and not sure where to move on now. Any advice is high appreciated. Please suggest me some solutions.

EDIT: Adrian Wragg suggested me to draw lines as distance, so 1 problem is done. I'm not sure how to solve the problem to exact steps, because all the resources I found (even in my language) is about theory with Math symbols. Too far to my knowledge.

Tim.

7
  • 3
    You mention the travelling salesman problem, but I don't see the difference here. If you replace the boxes with points, and then draw lines horizontally and vertically between them all, isn't that fundamentally the same problem? Aug 21, 2013 at 8:37
  • 1
    Start by converting the table into a graph. You can calculate the distance between all pairs.
    – rdrmntn
    Aug 21, 2013 at 8:41
  • I can convert it now, it is a minor problem after Adrian's suggestion. Could you guys please help me out with the algorithm, too? I can't understand even half of what was said on Internet. They are full of Math symbols instead of explanation.
    – cuzmAZN
    Aug 21, 2013 at 8:46
  • If you need help with some aspect of the traveling salesman problem, we'd be happy to do so. If you want us to do everything from scratch, we usually look for more effort and implementation on your part.
    – Teepeemm
    Aug 21, 2013 at 9:38
  • 1
    Can someone explain why everybody speaks about the Traveling Salesman Problem ? There is no condition on the number of times he can visit a node and not even the condition he must return to point A after visiting all other points...
    – fjardon
    Aug 21, 2013 at 9:49

3 Answers 3

3

You can make this the travelling salesman problem by finding the shortest distance between all pairs. Since you can only go up, down, left and right, distance between arbitrary K and L nodes will be Math.abs(L.y-K.y) + Math.abs(L.x-K.x) where x and y are their coordinates.

2
  • Can you be more specific, please? I would appreciate that much.
    – cuzmAZN
    Aug 21, 2013 at 8:44
  • The most computationally efficient way to solve TSP is with Dynamic Programming (that we've found so far, at least :P) Read this, perhaps: gebweb.net/blogpost/2011/06/24/… where "dist" is calculated as I've given you
    – Mattsjo
    Aug 21, 2013 at 8:49
2

Is there any way

Yes, most certainly. For example a brute force solution is guaranteed to give you an optimal solution in due time.

If you are searching for an efficient algorithm (that runs in polynomial time) you will probably be dissapointed as this problem can be reduced to the traveling salesman and is in the NP class. If you DO manage to solve this problem in polynomial time I believe there is a cash reward for 1.000.000 usd or something like that.

See: http://en.wikipedia.org/wiki/Reduction_(complexity)

http://en.wikipedia.org/wiki/NP_(complexity)

3
  • I should have mentioned no Bruce Force search, because it's not really algorithm, in my opinion. And I think the data I work on is less than 100.
    – cuzmAZN
    Aug 21, 2013 at 8:50
  • A dynamic programming solution will do it in O(n^2 2^n) which is as fast as you can do it, really. See xkcd.com/399 :)
    – Mattsjo
    Aug 21, 2013 at 8:54
  • 1
    @cuzmAZN well, what is and is not an algorithm isn't really an matter of opinion but well defined. Brute force search is a perfectly valid algorithm and is sometimes and excellent choice under some circumstances.
    – nic
    Aug 21, 2013 at 9:11
1

You can try a travelsalesman algorithm with a different distance function, for example the manhattan distance.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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