New answers tagged traveling-salesman
0
The question is whether the distances between cities fulfil the triangular equation: For any three A, B and C, is distance (A, B) ≤ distance (A, C) + distance (C, B)?
In your example, where distance (A, B) = 10, distance (C, B) = 1,000,000,000 and distance (X, B) = infinite (or very, very large) for all other X: Yes, it seems that going A->B->A avoids the ...
4
Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not.
In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...
-1
It is NP-complete.
It is obviously in NP.
To show it is NP-hard, reduce TSP to your problem. Say you require to repeat a certain sequence of colors. Just take the TSP instance and replace edges by paths with the repeat pattern of colors. Then the only legal way to move from one vertex to the next is by traversing that path.
1
So first of all lets consider the techniques. Nearest neighbour is a heuristic that directs the search. That means that it informs how the search should proceed. It can be seen as preemptive.
The 2-opt is not a search heuristic but is a technique used to attempt to improve a solution(partial solution). You can think of it as massaging the solution into a ...
3
No. A graph with only the edges of a polygon has an Hamilton circle, but the degree of each vertex is 2.
0
This problem is a generalization of TSP known as Set TSP. Not surprisingly, it is both NP-complete and well-studied.
Top 50 recent answers are included
