Salesman problem solution - how to get through the set of points with shortest possible way.
category: residue [glöplog]
Heya poets!
Here's my version of salesman problem solution, made in Amos Pro. you can easily port it to any language you want. i think it works fine. It is to late in the evening to check all properly.
Here it goes:
Cheers!
Here's my version of salesman problem solution, made in Amos Pro. you can easily port it to any language you want. i think it works fine. It is to late in the evening to check all properly.
Here it goes:
Code:
Input "number of points:";MADIM
Input "circularily? (1/0):";WKOLKO
Dim X(MADIM)
Dim Y(MADIM)
Global WKOLKO
Global MADIM
Global X(),Y()
F=1
For E=1 To MADIM
F=F*E
Next
Dim DISTS#(F)
Dim PERMS$(F)
Global DISTS#(),PERMS$()
PERMN=0
Global PERMN
For A=1 To MADIM
Print "x("+Str$(A)+"): ";
Input X(A)
Print "y("+Str$(A)+"): ";
Input Y(A)
Next
For B=1 To MADIM
ITER[1,Str$(B),0]
Next
For A=1 To F
For B=1 To F-1
If DISTS#(B)>DISTS#(B+1)
D#=DISTS#(B)
DISTS#(B)=DISTS#(B+1)
DISTS#(B+1)=D#
S$=PERMS$(B)
PERMS$(B)=PERMS$(B+1)
PERMS$(B+1)=S$
End If
Next
Next
Print "shortest permutation: ";PERMS$(1)
Print "distance: ";DISTS#(1)
Print "and: "
For A=2 To PERMN
If DISTS#(A)=DISTS#(1)
Print PERMS$(A)
End If
Next
Procedure ITER[N,ST$,TDI#]
If N<MADIM
For B=1 To MADIM
V=0
For C=1 To N
If B=Val(Mid$(ST$,(C-1)*2+1,2))
V=1
End If
Next
If V=0
ITER[N+1,ST$+Str$(B),TDI#]
End If
Next
Else
PERMN=PERMN+1
'Print "'"+ST$+"'"
PERMS$(PERMN)=ST$
For N=1 To MADIM-1
M1=Val(Mid$(ST$,(N-1)*2+1,2))
M2=Val(Mid$(ST$,(N)*2+1,2))
'Print M1,M2
DIST#=Sqr(((X(M1)-X(M2))^2)+((Y(M1)-Y(M2))^2))
'Print DIST#
TDI#=TDI#+DIST#
Next
If WKOLKO=1
M2=Val(Mid$(ST$,1,2))
M1=Val(Mid$(ST$,(MADIM-1)*2+1,2))
'Print M1,M2
DIST#=Sqr(((X(M1)-X(M2))^2)+((Y(M2)-Y(M1))^2))
'Print DIST#
TDI#=TDI#+DIST#
End If
'Print TDI#
DISTS#(PERMN)=TDI#
End If
End Proc
Cheers!
version for Amos on my website:
https://www.laffik.com/freebies/salesman%20problem.amos
https://www.laffik.com/freebies/salesman%20problem.amos
Cool. Still hard to read without comments.
no comments is not a problem! let me explain all the things here:
this part of code, as it is easy to guess, takes number of points from user and asks wheather to calculate the way in circular mode or singular mode. it simply means if the way from the last visited city to the first city has to be added to a total distance.
then, we declare variables x and y, where coordinates of each city has to be kept. it is good, when they are some resonable amounts, like geographical width 0-359 and height -90 - +90. should work fine. I didn't test on some crazy amounts. it should work fine, Amos can have some difficulties with variable range and such.
we also make the variables global, which means they will be accessible inside the procedure calculating permutations.
later we calculate the factorial of the amount of cities - as we should know from the skuuuull all possible and unique ways of getting through the set of points are permutations, and amount of permutations of number of cities is the factorial of it number. so, we need factorial.
then, having the factorial, we initiate variables for keeping each possible permutation and it's distance. we make it global, to access it from the permutation procedure. we zero and globalize the counter of permutations, needed in the permutation procedure.
later, we input from user the coordinates of x and y of each city. it can be angular positions on earth, the distance will be calculated in degrees remapped on a flat surface in such a case.
then, we shoot iterative permutation procedure ITER. first argument describes which position of permutation changes. as it is usual with permutations at the first digit of each permutation can be any number from the range. that's why the second argument simply contains numbers from 1 to the amount of the cities. it means we can start from any city we want. not each start will bring the shortest way. for now we permutate all the possibilities and we gonna find which is the shortest. zero on the third argument is total distance, calculated by further iterations.
after all iterations return we sort the arrays made by the procedures according to distance:
wen finished, we drop shortest permutation on the screen together with it's distance and all alternative routes, which has the same distance. we can do the way backwards and from any point on the way, both ways and such as long as it is on the shortest way...
within self invoking procedure ITER we're having two cases. when we didn't reach last digit of permutation yet and the other case when we are in iteration which finds the last digit. when N, which is the number of the digit in permutation is smaller than the maximum number of digits, we search along the permutation kept in string st$ from 1 to N. we search to check if number B that we are up to add at the end of the string st$ is already used in the string. if it is not present within any digit from 1 to N, we adjoin it at Nth position. if B is used somewhere in the string already, we skip to another B, up to the maximum number of the cities. Also, when B is adjoined we drop ITER procedure once again to adjoin another numbers on further positions, by invoking ITER with the next digits place in the permutation: N+1.
in case we reached the last digits position in permutation string st$, we increase counter of permutations PERM, as we found new one. also we get through the string with the one and for each pair of numbers we calculate the distance of Pitagorean lemma, by calculating the root of squares of differences in coordinates between each pair of the cities in permutation. we write the distance down in TDI# variable. if mode is set to circular, we add also the way from the last city to the first one on the way. finally we note down the distance in an array with the index of the number of this particular permutation - PERM.
and that's it! it is good to add commands:
at the beginning of the program, as Amos may not calculate such a big amount of permutations for amount of points bigger than 5. also, procedure doesnt work on cities in number higher than 9, as I can not figure out how to make Amos to adjoin string with numbers having leading zeros before the number and it works on numbers from 1 to 9.
here's the example of shortest way between 7 cities with coordinates in brackets on a picture. calculated distance is written below. it's calculated as a circular, so distance from 3 to 6 is added to the length of total way.
i think it counts right, and there's no mistakes anywhere in the code, whatsoever.
cheers and regards!
this part of code, as it is easy to guess, takes number of points from user and asks wheather to calculate the way in circular mode or singular mode. it simply means if the way from the last visited city to the first city has to be added to a total distance.
Code:
Input "number of points:";MADIM
Input "circularily? (1/0):";WKOLKOthen, we declare variables x and y, where coordinates of each city has to be kept. it is good, when they are some resonable amounts, like geographical width 0-359 and height -90 - +90. should work fine. I didn't test on some crazy amounts. it should work fine, Amos can have some difficulties with variable range and such.
we also make the variables global, which means they will be accessible inside the procedure calculating permutations.
Code:
Dim X(MADIM)
Dim Y(MADIM)
Global WKOLKO
Global MADIM
Global X(),Y()later we calculate the factorial of the amount of cities - as we should know from the skuuuull all possible and unique ways of getting through the set of points are permutations, and amount of permutations of number of cities is the factorial of it number. so, we need factorial.
Code:
F=1
For E=1 To MADIM
F=F*E
Nextthen, having the factorial, we initiate variables for keeping each possible permutation and it's distance. we make it global, to access it from the permutation procedure. we zero and globalize the counter of permutations, needed in the permutation procedure.
Code:
Dim DISTS#(F)
Dim PERMS$(F)
Global DISTS#(),PERMS$()
PERMN=0
Global PERMNlater, we input from user the coordinates of x and y of each city. it can be angular positions on earth, the distance will be calculated in degrees remapped on a flat surface in such a case.
Code:
For A=1 To MADIM
Print "x("+Str$(A)+"): ";
Input X(A)
Print "y("+Str$(A)+"): ";
Input Y(A)
Next then, we shoot iterative permutation procedure ITER. first argument describes which position of permutation changes. as it is usual with permutations at the first digit of each permutation can be any number from the range. that's why the second argument simply contains numbers from 1 to the amount of the cities. it means we can start from any city we want. not each start will bring the shortest way. for now we permutate all the possibilities and we gonna find which is the shortest. zero on the third argument is total distance, calculated by further iterations.
Code:
For B=1 To MADIM
ITER[1,Str$(B),0]
Next after all iterations return we sort the arrays made by the procedures according to distance:
Code:
For A=1 To F
For B=1 To F-1
If DISTS#(B)>DISTS#(B+1)
D#=DISTS#(B)
DISTS#(B)=DISTS#(B+1)
DISTS#(B+1)=D#
S$=PERMS$(B)
PERMS$(B)=PERMS$(B+1)
PERMS$(B+1)=S$
End If
Next
Next wen finished, we drop shortest permutation on the screen together with it's distance and all alternative routes, which has the same distance. we can do the way backwards and from any point on the way, both ways and such as long as it is on the shortest way...
Code:
Print "shortest permutation: ";PERMS$(1)
Print "distance: ";DISTS#(1)
Print "and: "
For A=2 To PERMN
If DISTS#(A)=DISTS#(1)
Print PERMS$(A)
End If
Next within self invoking procedure ITER we're having two cases. when we didn't reach last digit of permutation yet and the other case when we are in iteration which finds the last digit. when N, which is the number of the digit in permutation is smaller than the maximum number of digits, we search along the permutation kept in string st$ from 1 to N. we search to check if number B that we are up to add at the end of the string st$ is already used in the string. if it is not present within any digit from 1 to N, we adjoin it at Nth position. if B is used somewhere in the string already, we skip to another B, up to the maximum number of the cities. Also, when B is adjoined we drop ITER procedure once again to adjoin another numbers on further positions, by invoking ITER with the next digits place in the permutation: N+1.
Code:
If N<MADIM
For B=1 To MADIM
V=0
For C=1 To N
If B=Val(Mid$(ST$,(C-1)*2+1,2))
V=1
End If
Next
If V=0
ITER[N+1,ST$+Str$(B),TDI#]
End If
Next in case we reached the last digits position in permutation string st$, we increase counter of permutations PERM, as we found new one. also we get through the string with the one and for each pair of numbers we calculate the distance of Pitagorean lemma, by calculating the root of squares of differences in coordinates between each pair of the cities in permutation. we write the distance down in TDI# variable. if mode is set to circular, we add also the way from the last city to the first one on the way. finally we note down the distance in an array with the index of the number of this particular permutation - PERM.
Code:
PERMN=PERMN+1
'Print "'"+ST$+"'"
PERMS$(PERMN)=ST$
For N=1 To MADIM-1
M1=Val(Mid$(ST$,(N-1)*2+1,2))
M2=Val(Mid$(ST$,(N)*2+1,2))
'Print M1,M2
DIST#=Sqr(((X(M1)-X(M2))^2)+((Y(M1)-Y(M2))^2))
'Print DIST#
TDI#=TDI#+DIST#
Next
If WKOLKO=1
M2=Val(Mid$(ST$,1,2))
M1=Val(Mid$(ST$,(MADIM-1)*2+1,2))
'Print M1,M2
DIST#=Sqr(((X(M1)-X(M2))^2)+((Y(M2)-Y(M1))^2))
'Print DIST#
TDI#=TDI#+DIST#
End If
'Print TDI#
DISTS#(PERMN)=TDI#and that's it! it is good to add commands:
Code:
Set Buffer 1024
Set Stack 2048at the beginning of the program, as Amos may not calculate such a big amount of permutations for amount of points bigger than 5. also, procedure doesnt work on cities in number higher than 9, as I can not figure out how to make Amos to adjoin string with numbers having leading zeros before the number and it works on numbers from 1 to 9.
here's the example of shortest way between 7 cities with coordinates in brackets on a picture. calculated distance is written below. it's calculated as a circular, so distance from 3 to 6 is added to the length of total way.
i think it counts right, and there's no mistakes anywhere in the code, whatsoever.
cheers and regards!
Nice, now implement a faster solver using branch-and-cut :)
what you mean would be choosing shortest way every-time? of what they say on Numeric Methods of Maths choosing local minimum not always leads to global minimum, and there's possibility of falling in a cul-de-sac, where to exit you have to make longer way, that damages total distance of solution. sometimes shorter way to global high is to go throughout the pit. it's so lifelike... that's why many look for the high in a pits and stay there. i doubt about this method. i doubt about all. but as for knowledge of usual owner of the head, sometimes, behind the hill is another one, bigger. and to get htere we have to get up and down the smaller one. so, choosing shortest way from city to city not always results in best reslut. monte-carlo method - choosing ways at random and measuring the distance everytime we get unique way is slowest, not optimal but brings proper results. the one with permutations is fairest. i think. faster than monte-carlo and checking all possibilities right. do the branch and cut yourself for the same set of this 7 points here. we gonna compare results.
amos can have problems with comparing fractions sometime. it affects results when fractional distance is calculated. fixed version is on my webpage an under the link above. overwritten and updated.
for this 7 cities above, the other and same good results are:
- 1475632
- 2147563
- 2365741
- 3657412
- 4123657
- 4756321
- 5632147
- 5741236
- 7563214
- 1236574
- 3214756
- 6321475
- 7412365
all of the having the distance of 28,5467 units (pixels seemingly) in circular way.
with no circular mode there are ways: 6321457 and 7541236 with the distance of 21,6099 pixels.
keep the vibes !!!
amos can have problems with comparing fractions sometime. it affects results when fractional distance is calculated. fixed version is on my webpage an under the link above. overwritten and updated.
for this 7 cities above, the other and same good results are:
- 1475632
- 2147563
- 2365741
- 3657412
- 4123657
- 4756321
- 5632147
- 5741236
- 7563214
- 1236574
- 3214756
- 6321475
- 7412365
all of the having the distance of 28,5467 units (pixels seemingly) in circular way.
with no circular mode there are ways: 6321457 and 7541236 with the distance of 21,6099 pixels.
keep the vibes !!!
PieS:
if someone was interested (surely you are!!! :) ) in the dark side of the power, here is the worst way for our points:
1527346
with the distance 50,4057
as well as:
1643725
2516437
2734615
3461527
3725164
4372516
4615273
5164372
5273461
6152734
6437251
7251643
7346152
with the same distance, circularily.
and without circling:
5164372 and 2734615 (backwards) with the distance 47,4057 pixels.
full spectrum of ways for all 5040 ways between 7 points (buehehehe, life is a trip!), here:
https://www.laffik.com/salesman%20reports.txt
Mucias Gracjas Siniors!
if someone was interested (surely you are!!! :) ) in the dark side of the power, here is the worst way for our points:
1527346
with the distance 50,4057
as well as:
1643725
2516437
2734615
3461527
3725164
4372516
4615273
5164372
5273461
6152734
6437251
7251643
7346152
with the same distance, circularily.
and without circling:
5164372 and 2734615 (backwards) with the distance 47,4057 pixels.
full spectrum of ways for all 5040 ways between 7 points (buehehehe, life is a trip!), here:
https://www.laffik.com/salesman%20reports.txt
Mucias Gracjas Siniors!
PieS #02:
Of oddities, that this procedure can count, is the distance of the longest flight between airports (for those who usually enjoys the flights. I do.):
1. Singapore Changi Airport - 1°21′33″N 103°59′22″E - (103;1)
2. Denver - 39°51′42″N 104°40′23″W - (-104;39)
3. Paryż-Roissy-Charles de Gaulle - 49°00′35″N 2°32′52″E - (2;49)
4. Sydney Airport - 33°52′04″S 151°12′36″E - (151;-33)
5. Mauritius Airport - 20°25′48.10″S 57°40′58.88″E - (57;-20)
6. Cancún International Airport Mexico - 21°02′12″N 86°52′37″W - (-86;21)
7. Sheremetyevo International Airport, moscow - 55°58′22″N 37°24′53″E - (37;55)
8. Łódź - Reymont's Airport - 51°43′19″N 19°23′53″E - (19;51)
I picked up some nice ones, together with its' angular coordinates, which can be easily transformed on Cartesian coordinates - in brackets. One degree of angle on surface of the Earth is the same distance in kilometers evrywhere. apart from the fact, that earth is told to have 40000 km in surrounding. that divided by 360 degrees of full round around makes 111 km per angular degree. if we divide distance from Łódź to Moscow in kilometers by it angle between the cities, we've got 1397km by 18 degrees, what is just 77 kilometers per degree. So, the length around the Earth can be wrong, or angular positions of cities can be wrong, or distances between them can be wrong. fcuk know what's wrong. the method is rather fine. maybe the Earth is flat? or maybe the map is wrong too. it failed in Toruń and the direction of Vistula river (east-west or west-east), so most likely it's the map. like usual. pity it's Google being wrong too, if so.
Anyway...
the longest solution (BLUE) is 8 5 3 1 6 7 2 4 and the distance of 1161 degrees. which is 128871 km according to equator's length or 87000 as if from Łódź to Moscow was 1397 km and 18 degrees. Specifically:
8. Łódź - Reymont's Airport
5. Mauritius Airport
3. Paryż Roissy-Charles de Gaulle
1. Singapore Changi Airport
6. Cancún International Airport Mexico
7. Sheremetyevo International Airport, Moscow
2. Denver, Colorado, USA
4. Sydney Airport
shortest solution (RED) is: permutation 1 4 5 6 2 3 8 7 with the distance of 555 degrees of way, being 61000 km if calculated according to distance around the Earth and 41000 calculating by distance from Łódź to Moscow divided by angle difference. all that circurally starting from any point on the way and going in any direction along it (red way on the map). Particularly:
1. Singapore Changi Airport
4. Sydney Airport
5. Mauritius Airport
6. Cancún International Airport Mexico
2. Denver, Colorado, USA
3. Paryż Roissy-Charles de Gaulle
8. Łódź - Reymont's Airport
7. Sheremetyevo International Airport, Moscow
about your branch-and-cut, mr byteobserver, if we went from Sydney, then shortest way wouold be Singapore. From there the closest would be to go to Mauritius, and that already is not on the way of shortest travel. Shortest way having Sydney, Singapore and Mauritius in a line is 569 degrees long and is 38 in the rank of quickest. so, closest solution everytime is not always the closest one globally.
Cheers!
Of oddities, that this procedure can count, is the distance of the longest flight between airports (for those who usually enjoys the flights. I do.):
1. Singapore Changi Airport - 1°21′33″N 103°59′22″E - (103;1)
2. Denver - 39°51′42″N 104°40′23″W - (-104;39)
3. Paryż-Roissy-Charles de Gaulle - 49°00′35″N 2°32′52″E - (2;49)
4. Sydney Airport - 33°52′04″S 151°12′36″E - (151;-33)
5. Mauritius Airport - 20°25′48.10″S 57°40′58.88″E - (57;-20)
6. Cancún International Airport Mexico - 21°02′12″N 86°52′37″W - (-86;21)
7. Sheremetyevo International Airport, moscow - 55°58′22″N 37°24′53″E - (37;55)
8. Łódź - Reymont's Airport - 51°43′19″N 19°23′53″E - (19;51)
I picked up some nice ones, together with its' angular coordinates, which can be easily transformed on Cartesian coordinates - in brackets. One degree of angle on surface of the Earth is the same distance in kilometers evrywhere. apart from the fact, that earth is told to have 40000 km in surrounding. that divided by 360 degrees of full round around makes 111 km per angular degree. if we divide distance from Łódź to Moscow in kilometers by it angle between the cities, we've got 1397km by 18 degrees, what is just 77 kilometers per degree. So, the length around the Earth can be wrong, or angular positions of cities can be wrong, or distances between them can be wrong. fcuk know what's wrong. the method is rather fine. maybe the Earth is flat? or maybe the map is wrong too. it failed in Toruń and the direction of Vistula river (east-west or west-east), so most likely it's the map. like usual. pity it's Google being wrong too, if so.
Anyway...
the longest solution (BLUE) is 8 5 3 1 6 7 2 4 and the distance of 1161 degrees. which is 128871 km according to equator's length or 87000 as if from Łódź to Moscow was 1397 km and 18 degrees. Specifically:
8. Łódź - Reymont's Airport
5. Mauritius Airport
3. Paryż Roissy-Charles de Gaulle
1. Singapore Changi Airport
6. Cancún International Airport Mexico
7. Sheremetyevo International Airport, Moscow
2. Denver, Colorado, USA
4. Sydney Airport
shortest solution (RED) is: permutation 1 4 5 6 2 3 8 7 with the distance of 555 degrees of way, being 61000 km if calculated according to distance around the Earth and 41000 calculating by distance from Łódź to Moscow divided by angle difference. all that circurally starting from any point on the way and going in any direction along it (red way on the map). Particularly:
1. Singapore Changi Airport
4. Sydney Airport
5. Mauritius Airport
6. Cancún International Airport Mexico
2. Denver, Colorado, USA
3. Paryż Roissy-Charles de Gaulle
8. Łódź - Reymont's Airport
7. Sheremetyevo International Airport, Moscow
about your branch-and-cut, mr byteobserver, if we went from Sydney, then shortest way wouold be Singapore. From there the closest would be to go to Mauritius, and that already is not on the way of shortest travel. Shortest way having Sydney, Singapore and Mauritius in a line is 569 degrees long and is 38 in the rank of quickest. so, closest solution everytime is not always the closest one globally.
Cheers!
Now write a solution that is in P and thus proves P = NP.
so far I can not figure out why someone moved this thread to residue again. no way to respect you!
see it as a last opportunity before you get banned maybe?
Laffik: Branch-and-cut is not a heuristic. I think you should read the book "In Pursuit of the Traveling Salesman" by William Cook before continuing this thread.