Travelling Salesman Problem
- Given a graph G = (V, E), find a cycle of edges of this graph such that all of the vertices in the graph is visited exactly once with the minimum total length.
- For example, consider Figure below. There are two cycles satisfying our condition.
They are C1 = a→b→e→d→c→f→a, and C2 = a→c→b→e→d→f→a.
- For the partition problem, the sum of subset problem and the satisfiability problem, their solutions are either “yes” or “no”. They called decision problems.
- The minimal spanning tree problem and the traveling salesperson problem called optimization problems.
- For an optimization problem, there is always a decision problem corresponding to it.
- For instance, consider the minimal spanning tree problem, we can define a decision version of it as follows:
- Given a graph G, determine whether there exists a spanning tree of G whose total length is less than a given constant c. This decision version of the minimal spanning tree can be solved after the minimal spanning tree problem, which is an optimization problem, is solved.
- Suppose the total length of the minimal spanning tree is a. If a<c, the answer is “yes”; otherwise, its answer is “no”. The decision version of this minimal spanning tree problem is called the minimal spanning tree decision problem. Similarly, we can define the longest common subsequence decision problem as follows:
- Given two sequences, determine whether there exists a common subsequence of them whose length is greater than a given constant c. We again call this decision problem the longest common subsequence decision problem. The decision version problem will solve as soon as the optimization problem solved.
- In general, optimization problems are more difficult than decision problems.
- To investigate whether an optimization problem is difficult to solve, we merely have to see whether its decision version is difficult or not. If the decision version is difficult already, the optimization version must be difficult.