Question: What's wrong with TravelingSalesman - GraphTheory?

March 18 2014 Petra Heijnen 100
1

When I check the length of the optimal tour found by TravelingSalesman (GraphTheory package), it's different from the given result. What goes wrong?

See attached file.

``

restart: with(GraphTheory):

G := GRAPHLN(undirected,weighted,[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,

14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25],Array(1..25, [{17, 19},{10, 22

},{10, 14, 23},{6, 12, 14},{6, 7, 19},{4, 5},{5, 13, 15, 16},{12, 13, 14, 15},

{20, 25},{2, 3},{22, 25},{4, 8, 13},{7, 8, 12},{3, 4, 8},{7, 8, 21, 23},{7, 17

, 18},{1, 16, 18, 19},{16, 17, 25},{1, 5, 17},{9, 21, 22},{15, 20, 24},{2, 11,

20, 24},{3, 15, 24},{21, 22, 23},{9, 11, 18}]),`GRAPHLN/table/2`,Matrix(25, 25

, {(12, 13) = 137, (14, 4) = 920, (3, 14) = 902, (5, 6) = 561, (17, 18) = 443,

(22, 11) = 670, (16, 17) = 573, (19, 17) = 330, (18, 17) = 280, (10, 2) = 1630

, (16, 18) = 727, (23, 15) = 760, (17, 1) = 900, (4, 6) = 1216, (16, 7) = 600,

(14, 8) = 260, (12, 4) = 580, (1, 19) = 665, (4, 12) = 733, (19, 5) = 750, (8,

14) = 368, (11, 25) = 1366, (24, 22) = 300, (17, 19) = 495, (21, 15) = 930, (6

, 4) = 1110, (11, 22) = 1049, (12, 8) = 100, (15, 21) = 995, (17, 16) = 520, (

1, 17) = 866, (15, 23) = 833, (5, 19) = 930, (9, 20) = 184, (19, 1) = 630, (7,

15) = 598, (13, 8) = 110, (24, 21) = 250, (3, 10) = 471, (24, 23) = 550, (2,

10) = 1682, (13, 12) = 80, (8, 12) = 202, (21, 24) = 287, (23, 3) = 590, (15,

8) = 410, (14, 3) = 800, (23, 24) = 688, (7, 13) = 526, (8, 15) = 477, (20, 21

) = 245, (2, 22) = 547, (15, 7) = 990, (22, 20) = 420, (10, 3) = 300, (4, 14)

= 933, (5, 7) = 690, (18, 25) = 328, (25, 18) = 270, (21, 20) = 130, (25, 9) =

240, (7, 16) = 406, (20, 9) = 140, (6, 5) = 380, (8, 13) = 236, (20, 22) = 452

, (22, 2) = 500, (9, 25) = 227, (13, 7) = 640, (7, 5) = 670, (25, 11) = 1640,

(3, 23) = 518, (22, 24) = 495, (18, 16) = 700}, storage = sparse));

GRAPHLN(undirected, weighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25], Array(%id = 4487072130), `GRAPHLN/table/2`, Matrix(%id = 4488755818))

(1)

P:=TravelingSalesman(G);

15471, [1, 19, 5, 6, 4, 14, 3, 10, 2, 22, 11, 25, 9, 20, 21, 24, 23, 15, 8, 12, 13, 7, 16, 18, 17, 1]

(2)

add(GetEdgeWeight(G,{P[2][i],P[2][i+1]}),i=1..nops(P[2])-1);

16570

(3)

 

 

``


Download traveling_salesman_e.mw

Please Wait...