Geek asks and answers

TSP solution using reverse tracking

I tried to figure out how to solve TSP using backtracking. How do you calculate the cost?

The matrix:

∞   20  30  10  11
15  ∞   16  4   2
3   5   ∞   2   4
19  6   18  ∞   3
16  4   7   16  ∞

Cost:

3 -> 1 -> 2 -> 4 -> 5 -> 3 cost = 37
3 -> 1 -> 2 -> 5 -> 4 -> 3 cost = 59
3 -> 1 -> 5 -> 2 -> 4 -> 3 cost = 50
3 -> 1 -> 5 -> 4 -> 2 -> 3 cost = 62
3 -> 1 -> 4 -> 2 -> 5 -> 3 cost = 28
3 -> 1 -> 4 -> 5 -> 2 -> 3 cost = 36

I found out that it is calculated using the Bellman equation, I just don’t know a way to do this.

Any help would be greatly appreciated!

+3
source share
1 answer

To calculate costs, you just need to summarize all regional costs. For example, for a route 3 -> 1 -> 2 -> 4 -> 5 -> 3this gives

(3,1) => 3
(1,2) => 20
(2,4) => 4
(4,5) => 3
(5,3) => 7
------------
sum      37

So, in essence, you need to create the first sample of the route and calculate its cost. Once you do this, you know that the bottom line may be the best solution.

, , , , , , .

. , 1 2 3 4 5 6 7 8 9 1 40. , - , : 1 2 4 5 6 ... , 41. , - , , 40 , , ! , 1 2 4 5 6.

( , !)

+2

More articles:


All Articles