2 ms·
I recall that in a general case finding a hamiltonian cycle (or path) is already NP-complete. Although it should be a simple problem for small real graphs, what
by apronchenkov 6y ago
I recall that in a general case finding a hamiltonian cycle (or path) is already NP-complete. Although it should be a simple problem for small real graphs, what article suggests, I think, is to use a brute-force solution.
[1] https://mathworld.wolfram.com/HamiltonianPath.html https://mathworld.wolfram.com/HamiltonianPath.html
- zaik 6y agoJust deciding the question "Is there a Hamiltonian cycle in this graph?" is already NP complete. The author suggests the problem is easier than TSP because he "just" has to find any hamiltonian path, but the problem is just as hard. If I remember correctly, one can build a graph from any given 3SAT problem instance in polynomial time where: Satisfiable <=> Existence of a hamiltonian cycle.