|
|
I have changed your alg. to take data from file but cannot with with more than 10 cities it gives me that there is no hamilton circuit between cities.
Any help?
|
|
|
|
|
Hello,
I am applying your algorithm in an academic project. I would like to understand a bit more what is happening in your code. Do you have any literature suggestions?. Thanks
|
|
|
|
|
Hy,
You just saved me, based on your algorithm, I finally understood what I needed to do with my homework...
However, I would like to ask, what type of heuristic have you used? As I see it, is it some kind of greedy?
Have a nice day!
|
|
|
|
|
Thank you very much for your great code
You just rescued my life!
Thank you
|
|
|
|
|
This algorithm works fine and gives optimal solution I believe. But there should be a minor change in the algorithm code i.e the you do have to call the get_valid_circuit if S_V_id and i is same. just check.
// algorithm
//for each vertex, S_V as a staring node
for(int S_V_id=0;S_V_id<n;S_V_id++)
{ //for each and non start vertex as i
for(i=0;i<n;i++)
if(S_V_id!=i)
{ //set all to unvisited
set_visited(ALL,FALSE);
// set staring vertex as visited
set_visited(S_V_id,TRUE);
//reset/init minimum circuit
reset_min_circuit(S_V_id);
// obtain circuit for combination of S_V and i
new_circuit_length=get_valid_circuit(S_V_id,i);
// if newer length is less than the previously
//calculated min then set it as min and set the
//current circuit in hamiltonion circuit
if(new_circuit_length<=min_circuit_length)
SET_HAM_CKT(min_circuit_length=new_circuit_length);
}
}
patson33
|
|
|
|
|
Sorry to report, but I have several examples of your algorithm not finding the optimal solution, even for small test cases. Not that it isn't everyone's dream to find a polynomial algorithm for an NP-Complete problem (in this case, it's NP-HARD!). I think every good computer scientist delves into the problem at one point or another and comes out with a better understanding of what makes NP-Complete problems "hard."
That being said, here is proof of non-optimality.
I modified your program to input data in a standard way. In matrix form:
(num nodes)
(dist0to0) (dist0to1) ... (dist0toN)
(dist1to0) (dist1to1) ... (dist1toN)
...
(distNto0) (distNto1) ... (distNtoN)
It makes sure to keep the distance from a node to itself as INFI. Then check out this simple test case (based on 10 points in a Euclidean space):
10
0 583 584 201 291 526 337 327 180 304
583 0 1030 633 854 90 389 353 405 638
584 1030 0 420 362 1010 645 892 712 860
201 633 420 0 254 601 277 475 293 504
291 854 362 254 0 807 528 617 463 516
526 90 1010 601 807 0 384 269 347 554
337 389 645 277 528 384 0 389 247 570
327 353 892 475 617 269 389 0 184 286
180 405 712 293 463 347 247 184 0 325
304 638 860 504 516 554 570 286 325 0
Your program came up with:
Minimum circuit length is: 3063
Circuit is:
<8> <1> <5> <7> <9> <0> <3> <4> <2> <6> <8>
Here is a better tour (probably optimal) found by a simple backtracking algo:
TOUR (2889): 0 4 2 3 6 1 5 7 9 8 0
Here is a much larger example.
rbg443 data from http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/atsp/rbg443.atsp.gz[^].
The best known tour is 2720 (see http://www.informatik.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ATSP.html[^]).
Just strip the header from the rbg443 data file (everything else is in the right format).
tsm < ../final/rbg443.txt
Enter no. of cities(MAX:2000):Enter paths:< source_id destination_id distance >
ids varying from 0 to 442
........................................................................................................................
........................................................................................................................
........................................................................................................................
...................................................................................
Minimum circuit length is: 3758
Circuit is:
<375> <189> <86> <395> <442> <423> <427> <392> <422> <441> <437> <436> <434> <414> <402> <433> <428> <426> <432> <409>
<404> <311> <415> <431> <413> <199> <251> <376> <313> <439> <430> <418> <412> <429> <425> <424> <420> <111> <212> <101>
<19> <364> <2> <140> <139> <34> <116> <95> <294> <81> <378> <417> <390> <142> <97> <239> <416> <252> <75> <388> <411>
<266> <293> <353> <410> <383> <317> <315> <408> <440> <393> <391> <385> <407> <291> <241> <270> <406> <389> <381> <405>
<275> <274> <373> <374> <368> <358> <403> <365> <233> <401> <380> <253> <310> <352> <400> <338> <82> <333> <399> <320>
<325> <357> <258> <286> <398> <89> <331> <397> <355> <123> <246> <319> <175> <396> <316> <394> <225> <269> <156> <387> <185>
<228> <386> <77> <256> <384> <152> <382> <261> <100> <435> <27> <314> <308> <377> <206> <148> <369> <113> <41> <62> <262>
<273> <178> <367> <354> <245> <366> <249> <237> <363> <205> <125> <438> <110> <362> <379> <69> <361> <278> <271> <360>
<240> <106> <267> <257> <234> <192> <191> <359> <283> <323> <356> <40> <183> <351> <226> <171> <350> <55> <349> <332>
<10> <107> <254> <93> <105> <302> <348> <312> <371> <347> <264> <255> <346> <318> <370> <49> <85> <306> <345> <54> <231>
<344> <149> <28> <343> <244> <232> <342> <421> <52> <277> <341> <372> <22> <337> <141> <218> <121> <45> <83> <51> <340>
<48> <272> <339> <265> <25> <336> <229> <126> <58> <335> <94> <39> <334> <243> <50> <71> <330> <248> <236> <329> <215>
<146> <145> <328> <227> <32> <144> <0> <99> <168> <98> <14> <90> <16> <327> <207> <238> <326> <263> <304> <324> <64> <103>
<322> <117> <76> <102> <321> <172> <279> <47> <143> <419> <23> <91> <181> <31> <84> <247> <137> <78> <219> <124> <122>
<309> <186> <153> <138> <56> <307> <20> <88> <305> <182> <37> <303> <1> <169> <87> <33> <79> <3> <118> <26> <301> <242>
<108> <73> <24> <60> <96> <80> <300> <15> <44> <57> <5> <42> <250> <176> <46> <299> <35> <104> <29> <298> <65> <61> <17>
<297> <74> <296> <18> <295> <292> <290> <260> <289> <288> <287> <285> <284> <282> <281> <280> <276> <268> <259> <235>
<230> <224> <223> <222> <221> <220> <217> <216> <214> <213> <211> <210> <209> <208> <204> <203> <202> <201> <200> <198>
<197> <196> <195> <194> <193> <190> <188> <187> <184> <180> <179> <177> <174> <173> <170> <112> <167> <166> <165> <164>
<163> <162> <161> <160> <159> <158> <157> <155> <154> <151> <150> <147> <136> <135> <134> <133> <132> <131> <130> <129>
<128> <127> <120> <119> <115> <114> <109> <92> <72> <70> <68> <67> <66> <63> <59> <53> <43> <38> <36> <30> <21> <13> <12>
<11> <9> <8> <7> <6> <4> <375>
Your solution of 3758 is not close to best known tour of 2720. A greedy algorithm based on Prim's shortest path finds a tour of around 3305.
Here is the modified version of the code (I only modified the input / output -- use diff to see what I changed):
<br />
<br />
<br />
<br />
#include<stdio.h><br />
#include<stdlib.h><br />
#define ALL -1<br />
#define MAXCITIES 2000<br />
<br />
enum BOOL{FALSE,TRUE};<br />
long*visited;
long*min_circuit;
long*ham_circuit;
long min_circuit_length;
<br />
int n;
long matrix[MAXCITIES][MAXCITIES];
long INFI;
<br />
void reset_min_circuit(int s_v_id)<br />
{<br />
min_circuit[0]=s_v_id;<br />
for(int i=1;i<n;i++) min_circuit[i]=-1;<br />
}<br />
<br />
void set_visited(int v_id,BOOL flag)<br />
{<br />
if(v_id==ALL) for(int i=0;i<n;i++) visited[i]=flag;<br />
else visited[v_id]=flag;<br />
}<br />
<br />
void SET_HAM_CKT(long pl)<br />
{<br />
ham_circuit[0]=pl;<br />
for(int i=0;i<n;i++) ham_circuit[i+1]=min_circuit[i];<br />
ham_circuit[n+1]=min_circuit[0];<br />
}<br />
<br />
<br />
long get_valid_circuit(int s_v,int s_n_v)<br />
{<br />
int next_v,min,v_count=1;<br />
long path_length=0;<br />
min_circuit[0]=s_v;<br />
min_circuit[1]=s_n_v;<br />
set_visited(s_n_v,TRUE);<br />
path_length+=matrix[s_v][s_n_v];<br />
for(int V=s_n_v;v_count<n-1;v_count++)<br />
{ min=INFI;<br />
for(int i=0;i<n;i++)<br />
if( matrix[V][i]<INFI && !visited[i]<br />
&& matrix[V][i]<=min<br />
)<br />
min=matrix[V][next_v=i];<br />
set_visited(next_v,TRUE);<br />
V=min_circuit[v_count+1]=next_v;<br />
path_length+=min;<br />
}<br />
path_length+=matrix[min_circuit[n-1]][s_v];<br />
return(path_length);<br />
}<br />
<br />
int main()<br />
{<br />
INFI=(1<<28)-1;<br />
<br />
int pathcount,i,j,source,dest,nxt;<br />
long dist=0;<br />
long new_circuit_length=INFI;<br />
printf("Enter no. of cities(MAX:%d):",MAXCITIES);<br />
scanf("%d",&n);<br />
if (n > MAXCITIES){<br />
printf("ERROR: Number of cities is more than max of %d\n", MAXCITIES);<br />
return -1;<br />
}<br />
<br />
printf("Enter paths:< source_id destination_id distance >\n ids varying from 0 to %d\n",n-1);<br />
for(i=0;i<n;i++)<br />
for(j=0;j<n;j++)<br />
matrix[i][j]=INFI;<br />
<br />
for (i=0;i<n;i++){<br />
for(j=0;j<n;j++){<br />
scanf("%d",&nxt);<br />
if (i != j){ matrix[i][j]=nxt; }<br />
}<br />
}<br />
<br />
<br />
<br />
visited=new long[n];<br />
min_circuit=new long[n];<br />
ham_circuit=new long[n+2];<br />
min_circuit_length=INFI;<br />
for(int S_V_id=0;S_V_id<n;S_V_id++)<br />
{<br />
printf("."); fflush(stdout);<br />
for(i=0;i<n;i++)<br />
{
set_visited(ALL,FALSE);<br />
set_visited(S_V_id,TRUE);<br />
reset_min_circuit(S_V_id);<br />
new_circuit_length=get_valid_circuit(S_V_id,i);<br />
if(new_circuit_length<=min_circuit_length)<br />
SET_HAM_CKT(min_circuit_length=new_circuit_length);<br />
}<br />
}<br />
printf("\n");<br />
if(min_circuit_length<INFI)<br />
{<br />
printf("\n\nMinimum circuit length is: %ld\nCircuit is:\n",min_circuit_length);<br />
for(i=1;i<n+2;i++) printf("<%ld> ",ham_circuit[i]);<br />
printf("\n");<br />
}<br />
else printf("\n\nNo hamiltonian circuit !");<br />
delete []visited;<br />
delete []min_circuit;<br />
delete []ham_circuit;<br />
}<br />
Your algorithm is an interesting approach though. New ideas for an old problem usually provide some insight.
Best,
-Kevin
|
|
|
|
|
Thanks for the example. Now I need to work out why this algorithm missed out the tour provided by you.
Keep updating
regards,
Omkar.
|
|
|
|
|
for the 10 tour i found
Best:2278
9 7 5 1 6 8 0 3 4 2 9
guess its also not optimal
modified 27-Nov-11 10:03am.
|
|
|
|
|
.
modified 17-May-14 11:58am.
|
|
|
|
|
I agree with Cap'n Code. To achieve such a big task (show that P=NP), you need to do more than: "as far as i am concered i think this algorithms yields the optimal hamiltonion circuit". You must produce a prove; testing won't be enough.
There is an "almost optimal" solution to the Traveling Salesman Problem. It is known as the "triangle inequality". Basically, it determines the path starting from the minimum spanning tree. It belongs to the class of algorithms known as approximation algorithms. You might want to compare the results of your algorithm with the results of triangle inequality.
Rui A. Rebelo
Computers are useless, they can only provide answers.
Pablo Picasso
|
|
|
|
|
I know that the problem belongs to NP category, thts why my algorithm is an open issue for proof and thts why i have posted here, and prooving the problem as NP is NP itself.
I took so many days to either prove or disprove my algorithm and cdnt end-up with any satisfactory solution in either case, so its open for all others to prove or disprove.
I have gone thru th concepts of triangle inequality.I want to compare the results of my algorithm with the results of triangle inequality, so will u do favour for me and send me the source code for it? I ll b pleased to explore in this domain.
So please send me the test cases where my algorithm fails, thts the only way someone can prove that my algorithm dsnt giv optimal solution in each case.
Regards.
|
|
|
|
|
I know that the problem belongs to NP category, thts why my algorithm is an open issue for proof and thts why i have posted here, and prooving the problem as NP is NP in itself.
I took so many days to either prove or disprove my algorithm and cdnt end-up with any satisfactory solution in either case, so its open for all others to prove or disprove.
So please send me the test cases where my algorithm fails, thts the only way someone can prove that my algorithm dsnt giv optimal solution in each case.
|
|
|
|
|
I just quickly looked over this, and the key seems to be in the magic call to "get_valid_circuit",
or in your pseudo-code that starts with "for star[t]ing vertex as V" and ends with the cryptic "this path is obtained with the greedy method."
I would say that either this part is exponential, or it potentially misses some cases/solutions.
In your example, you actually do more than an exhaustive (i.e. exponential) search, but, at the same time, it doesn't seem exhaustive enough. I.e. The first case is 0-1-2-3. You then jump to 0-2-3-1. Where is 0-1-3-2? Yes, you stumble across it later, but is that basically coincidence? There are in fact only 6 *circuits*, and you compute 12. I think if you had more than about 6 cities, you would see where you miss possible tours. Do a search on the web -- there are fat data sets you can try your routine out on, and compare it to the known optimal solution.
If you always get it right, in polynomial time, apply for your Turing & Field awards....
Cheers,
Ben
PS if you at least spell-checked your articles, you'd probably get more responses.
|
|
|
|
|
I have tested the code and inserted a variable to count the number of executed lines of code when running a test case. It does show that the approach does behave in n^4 order, but we still need to have a rock-solid proof of correctness before getting too excited about it. Since the number of test cases grows n!, where n is the number of cities, this would be a tedious task and a mathematical proof is necessary.
Nice work.
|
|
|
|
|
While all well and good to say "look we've deduced, P=NP for one scenario" we're left with an N-factorial time algorithm. For grins I decided to see if this would handle even a modest route for a real traveling salesman. I arbitrarily pick 64bits as the maximum value for a number of computations we're willing to spend waiting for our ideal route to be computed. This also made it easy to manually compute the number of cities needed to go exceed FFFFFFFFFFFFFFFF (base 16) or 1,844,674,407,370,9551,615 (base 10) computations performed to find to optimal route. (This is assuming our friends algorithm lives up to the claims).
I started computing at 20 (base 10) and found that this would indeed fit within our parameters; 2432902008176640000 (base 10) 21C3677C82B40000 (base16). But if you add one city to the route, we get a number too large for our allowed number of computations. 51090942171709440000 (base 10) (base 16 omitted because I’m too lazy to convert it)
Switching gears for a moment let’s assume that we can optimize the algorithm to perform each computation in one clock cycle. On the top end 4GHz processors we’re running roughly 4,294,967,296 clock cycles per second (I’m being generous in assuming a binary Gigahertz measure). Now let’s say we’re willing to give our mythical salesman a route no larger than 20 cities. Should the unfortunate sap get this long of a route, and tries waiting for the 'optimum route' to be computed he’ll be waiting somewhere in the neighborhood of 566,454,140.5 seconds; which is roughly 157348.4 hours; which is nearly 6556.12 days; which almost, but not quite 18 years. So my friends, the next time you want to have an 18 year old traveling sales man do a 20 city run, you’ll either need to recruit him in the maternity ward, or invent practical time travel.
Now don’t get me wrong, if we can indeed prove P=NP for select problems like this; we will certainly gain a wealth of knowledge about route planning, and algorithms to implement such items. However we as a community need to put things in perspective. While we gain a wealth of information which will help future generations of software developers create more effective algorithms/heuristics, we still need to temper our excitement with a realistic measure of just what is possible (at the time of discovery of course) with the new discovery.
|
|
|
|
|
Anonymous wrote: "While all well and good to say "look we've deduced, P=NP for one scenario" we're left with an N-factorial time algorithm....."
I said its in O(n^4) so though your calculations hold for n! this is not the case here.
I have put my comments on rest of the issues in other replies.
|
|
|
|
|
approach does behave in n^4 order. The only issue is that I am not sure about its optimality.
I am looking for set of test cases to verify the same.
|
|
|
|
|
Its true. I know that it wont cover all the tours, but thats what the key issue is. I am attempting to exclude the tours as much as possible without excluding the actual solution ( duh ! i said I am attempting ).
So I am here to find any setback on this algorithm.
I will try to run several test sets for this code to evalute the issue, currently looking for the same.
PS: thanks for ur PS. I'll try to improve on it while coding in future.
-- modified at 7:54 Tuesday 24th January, 2006
|
|
|
|
|
True enough, of course you would have to skip over lots and lots of tours. The big question (and likelihood) is that the optimal solution will sometimes be one of them. And if it ever is, well, there are a number of very good traveling salesman *heuristics* out there, that work with massive (1000+ city) data sets, in less than O(n^4) time. Unfortunately for checking correctness, if for smaller cases your method does an exhaustive search (so checks all routes) it will find the best route. You need to test it on bigger data sets. Since finding good heuristics for the problem is also interesting, there are already big data sets with known solutions out there. Have you tried this? Have you tried out even 10-20 cities?
Have fun,
Ben
|
|
|
|
|
I found some loop holes in the algorithm you provided.
1. Why did you considered the TSP problem working on a Complete Graph? You algo would fail once you change this condition.
2. Finding a Circuit is a NP-Complete problem. When you use greedy method to find the circuit, you are loosing the focus from optimal solution.
Let me know if you think i am wrong on any point, i will share the documented proofs.
|
|
|
|
|