vv

2304 Reputation

9 Badges

1 years, 240 days

MaplePrimes Activity


These are questions asked by vv


 

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


 

restart;

Digits:=10;
to 10 do
evalf(add(sin(k), k = 1 .. 10000)) od;

10

 

1.633891035

 

1.633891035

 

1.633891035

 

1.633891046

 

1.633891046

 

1.633891046

 

1.633891012

 

1.633891012

 

1.633891012

 

1.633891049

(1)

restart;   # execute several times to obtain randomness

interface(version);

`Standard Worksheet Interface, Maple 2016.2, Windows 7, January 13 2017 Build ID 1194701`

(2)

Digits:=18;

18

(3)

to 10 do  
evalf(add(sin(k), k = 1 .. 10000)) od;

1.63389102179246197

 

1.63389102179246223

 

1.63389102179246223

 

1.63389102179246233

 

1.63389102179246233

 

1.63389102179246242

 

1.63389102179246242

 

1.63389102179246371

 

1.63389102179246371

 

1.63389102179246410

(4)

 

Suppose that a finite set of polynomials in C[x,y,z] has a finite number of solutions (i.e. the generated ideal is 0-dimensional).

Suppose also that the Groebner basis wrt plex(x,y,z) is

[f(z), g(y,z), h(y,z), k(x,y,z)]

As well known, the system can be now easily solved: choose a root z0 of f, plug it into g and h and look for a common root (y0) etc.

The question is the following:
Is it true that for EVERY root z0 of f there exist y0, z0 such that (x0,y0,z0) satisfy the system?

In all the examples I have seen this is true, but I don't know whether this is true in general or there is a counterexample.

[This is not a pure Maple question but I know that some members here work in this area].

Thank you.

It is well known that fsolve usually increases (internally) Digits in order to obtain the desired accuracy.

But in the following example, it seems that fsolve highly exaggerates :-)   

restart;
N:=40:
Digits:=100:
F:=expand(mul(x-k,k=1..N)):
f:=evalf(F):
S:=[fsolve(f,complex)];

Error, (in fsolve) Digits cannot exceed 38654705646


Note that the bug does not appear if e.g. F:=expand(mul(x-k-I, k=1..N)):

 

 

with(plots):with(plottools):
p1:=plot( x^3,x=-1..1,thickness=20,color=red):
p2:=plot(-x^3,x=-1..1,thickness=20,color=blue):
p3:=display(rectangle([0.5, 1],[0.75,-1],color=green)):
p4:=display(rectangle([-1,-0.1],[1,0.1],color=yellow)):

display(p1,p2,p3,p4); # order = 4312

 

#  display(p3,p4,p1,p2); # order = 4312 (the same)

It seems that the rectangles are plotted first, in reversed order, and then the curves, in direct order.
Has someone an explanation?

1 2 3 4 Page 1 of 4