-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.

Community
  • 1
  • 1
cuzmAZN
  • 377
  • 1
  • 7
  • 25
  • 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? – Adrian Wragg Aug 21 '13 at 08:37
  • 1
    Start by converting the table into a graph. You can calculate the distance between all pairs. – rdrmntn Aug 21 '13 at 08: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 '13 at 08: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 '13 at 09: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 '13 at 09:49
  • @Teepeemm: The problem is throughout all of these researches, I still don't understand how it works, due to my language limit and that all of them were implied by math, not programming tactic. If I understand any of them, I would not have been here to ask. I just ask for suggestion and way to solve it graphically, I didn't ask for specific code. I just need to imagine how it works, and I did spend couple days on this, how didn't that consider efforts? Just because I couldn't understand them meant I didn't do researches, did you say? – cuzmAZN Aug 21 '13 at 20:03
  • @fjardon You are correct that this isn't exactly the Traveling Salesman Problem. But this is close to that problem (and TSP is the best known of that family of problems), and any approach to TSP will work here, with only minimal adjustments. – Teepeemm Aug 21 '13 at 21:48

3 Answers3

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.

Mattsjo
  • 627
  • 5
  • 11
  • Can you be more specific, please? I would appreciate that much. – cuzmAZN Aug 21 '13 at 08: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: http://gebweb.net/blogpost/2011/06/24/the-dynamic-programming-algorithm-for-the-travelling-salesman-problem/ where "dist" is calculated as I've given you – Mattsjo Aug 21 '13 at 08: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)

nic
  • 443
  • 3
  • 12
  • 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 '13 at 08: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 http://xkcd.com/399/ :) – Mattsjo Aug 21 '13 at 08: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 '13 at 09:11
1

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

Micromega
  • 12,486
  • 7
  • 35
  • 72