# 旅行推销员问题

## 3. Input

There are two different sources for specifying an input graph:

1. Draw Graph: You can put several points on the drawing box, but you must not draw any edge to ensure the (near-)metric property of the graph. After you have finished putting the points, the edges will be drawn automatically for you after.
2. Example Graphs: You can select from the list of graphs to get you started.

## 4. 简单模式匹配算法（Bruteforce）

Bruteforce: It tries all (V-1)! permutation of vertices (not all V! since it does not matter where we start from). It enumerates all possibilities by doing a dfs search with parameters similar to those of Held-Karp algorithm, that is, the dfs search will return the value of the tour starting from current vertex to all vertices that we have not already visited.

Time complexity: O(V * (V - 1)!) = O(V!)

## 6. 近似

Approximation: There are two approximation algorithms available, a 2-approximation algorithm and a 1.5-approximation algorithm that is also well known as Christofides Algorithm.