7
I have to find out if there is Hamiltonian cycle in a giant graph (1000 vertices in the smallest instance and 5000 vertices in the largest).
My initial idea was to backtrack, and in small instances, it worked fine. But for instance 1000 vertices, I left 6 hours and no response.
My idea was to get a travel salesman code ready (only found using matrix) and put the edges that exist with weight 1, and those that do not exist with weight 9.
If the result of the execution of the function gives the number of vertices, there is a Hamiltonian cycle.
If not, then there is no Hamiltonian cycle (because you had to use some 9-weight edge to find the way).
For small instances, it continued to work, but with the 1000-vertex instance, it also stuck.
No one in the class has the knowledge to do something that runs a lot from backtracking, so we’re supposed to find some code already implemented on the Internet. At most, we should make some small changes.
Does anyone have a traveling salesman or a code that would detect a Hamiltonian cycle with an adjacency list? Or instances up to 5000 in less than 3 hours?
Would someone try to help me by giving at least a hint?
Links to the codes and entries I used:
Follow the link of the code I used (in C): http://ideone.com/qyEipK
Instances I need to pass: https://www.dropbox.com/sh/50ij1m5w5b1mfca/AADzt3XsE9cVg6OlW6SDTygQa?dl=0
Follow the link to an adjacency list: http://ideone.com/Ib9i0P
Follow the link of a code I made to turn the adjacency list into an array file: http://ideone.com/7stdkJ
Follow the link of a small matrix N=18 that contains a Hamiltonian cycle: http://ideone.com/M8PfTu
Follow the link of a small matrix N=18 that does not contain a Hamiltonian cycle: http://ideone.com/GBlyZ5
If the code is not too long, edit the question and add it. Title of the question should give an idea about the problem, the way it looks a little strange.
– rray
Considering that you are trying to get an algorithm that solves an NP-complete problem, it means that there is probably no algorithm that will give you the answer in reasonable time in all cases. However, the typical case is quite different from the worst case, so I will think of some approach that can give a response in reasonable time in "almost all" cases. To help, you could describe more about these graphs, they are random graphs, have some peculiar structure or are graphs particularly created for the purpose of being difficult in this problem?
– Victor Stafusa
I edited the title of the question, because (1) there is no crash and (2) your "Why?" you already know - it is because the graph is too big.
– Victor Stafusa
Victor Stafusa, when I put to execute the code in a machine of the University, Ubuntu, i7 5th generation, 8gb of ram, in 4 minutes appeared a message "Died". I will edit the topic with the instances that should be read.
– peetorres