Advanced Search

Question: TravelingSalesman - speed

Question:TravelingSalesman - speed

vv 13065 Maple
iterator travelling-salesman-problem
May 13 2017
2


 

How is it possible that  GraphTheory:-TravelingSalesman  
is much slower than a simple brute-force solution?

 

> 

restart;
> 

n:=10:
> 

A:=Matrix(n, (i,j)->`if`(i=j,0,n*(n-i)^4+2*j+(n-i)^2+j^3)):A[1,2]:=100*n^3:A;

Matrix([[0, 100000, 65724, 65763, 65826, 65919, 66048, 66219, 66438, 66711], [41027, 0, 41057, 41096, 41159, 41252, 41381, 41552, 41771, 42044], [24062, 24071, 0, 24131, 24194, 24287, 24416, 24587, 24806, 25079], [12999, 13008, 13029, 0, 13131, 13224, 13353, 13524, 13743, 14016], [6278, 6287, 6308, 6347, 0, 6503, 6632, 6803, 7022, 7295], [2579, 2588, 2609, 2648, 2711, 0, 2933, 3104, 3323, 3596], [822, 831, 852, 891, 954, 1047, 0, 1347, 1566, 1839], [167, 176, 197, 236, 299, 392, 521, 0, 911, 1184], [14, 23, 44, 83, 146, 239, 368, 539, 0, 1031], [3, 12, 33, 72, 135, 228, 357, 528, 747, 0]])

 (1)
> 

with(GraphTheory):
> 

G:=Graph(A);

GRAPHLN(directed, weighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], Array(%id = 18446744074326770022), `GRAPHLN/table/1`, Matrix(%id = 18446744074326769782))

 (2)
> 

t:=time[real]():
TravelingSalesman(G);
'time'=time[real]()-t;

156750, [1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 1]

  

time = 36.410

 (3)
> 

############### brute-force #############
> 

t:=time[real]():
P:=Iterator:-Permute([seq(2..n)]):
cmin:=infinity: ord:=<"none">:
for  v in P do
  f:=add(A[v[k],v[k+1]],k=1..n-2) + A[1,v[1]]+A[v[n-1],1];
  if f<cmin then cmin:=f; ord:=copy(v) fi;
od:
cmin,[1, entries(ord,'nolist',indexorder),1];
'time'=time[real]()-t;

156750, [1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 1]

  

time = 1.715

 (4)
> 

# And for n=11 I had to interrupt TravelingSalesman;
# brute-force still works for n=12.


 

Download TravelingSalesman-test.mw
Please Wait...