巡回セールスマン問題(Traveling Salesman Problem)

リポジトリ

巡回セールスマン問題(TSP: Traveling Salesman Problem)

最短ハミルトン閉路(各頂点を1回だけ含む(開始・終了点を除く)閉じた歩道(閉路))を見つける問題
NP困難なため、多項式時間で解けない。競技プログラミングでは、ビットDPによる解法を知っていれば十分だと思われる。

まずは、頂点集合、スタートノード(最後に戻ってくるノード), 頂点から頂点への距離(辺の重み)の最短ハミルトン閉路長を考える。

を現時点で到達済みの頂点集合、を現時点で最後に到達した頂点としたときの
を状態(S,v)になるまでの最短距離と定義すると次のようにDPで解ける。
初期化

更新

ここで、Sは集合であるが、これを01のビット系列で表して実装する(ビットDP)。
例えば、, は２進数でと表す。
の表現の仕方は通りなので、計算量はとなる。

/**
 * Gets length of the shortest Hamilton cycle and back pointers for building the shortest path.
 * O(2^|V| |V|^2)<br>
 * @param G adjacency matrix
 * @param s source node (※= destination node)
 * @return  TSPResult
 */
static TSPResult TSP(int[][] G, int s){
	int n = G.length, N = 1 << n;
	int[][] DP = new int[N][n], prev = new int[N][n];
	for(int i = 0; i < N; ++i) Arrays.fill(DP[i], INF);
	for(int i = 0; i < n; ++i){
		DP[1<<i][i] = G[s][i];
		prev[1<<i][i] = s;
	}
	for (int S = 1; S < N; ++S) {
		for (int i = 0; i < n; ++i) {
			if ((S & (1<<i)) == 0) continue;
			for (int j = 0; j < n; ++j) {
				if ((S & (1<<j)) != 0 ) continue;
				//i in S, j not in S 
				int newDist = DP[S][i]+G[i][j];
				if(DP[S|(1<<j)][j] > newDist) {
					DP[S|(1<<j)][j] = newDist;
					prev[S|(1<<j)][j] = i;
				}
			}
		}
	} 
	return new TSPResult(s, DP[N-1][s], prev);
}

計算結果クラス。buildPathは未検証

/** Result of Traveling Salesman Problem (TSP) */
public static class TSPResult{
	private int s;		//source node (※= destination node)
	private int length;	//length of shortest Hamilton cycle
	private int[][] prev;	//back pointers
	public TSPResult(int s, int length, int[][] prev){ set(s, length, prev); }
	final private void set(int s, int length, int[][] prev){ this.s = s; this.length = length; this.prev = prev; }
	final public int getLength(){ return length; }
	final public int getPrev(int S, int v){ return prev[S][v]; }
	/** Builds the shortest Hamilton cycle */
	public List<Integer> buildPath(){ return buildPath(false); }
	/**
	 * Builds the shortest Hamilton cycle
	 * @param useRecursive
	 * @return the shortest Hamilton cycle
	 */
	public List<Integer> buildPath(boolean useRecursive){
		int N = prev.length, S = N - 1;
		LinkedList<Integer> path = new LinkedList<Integer>();
		if(length < INF ){
			if(useRecursive) buildPath(S, s, path);
			else buildPath(path);
		}
		return path;
	}
	/** buildPath non recursive ver. */
	private void buildPath(LinkedList<Integer> path){
		int N = prev.length, S = N - 1;
		int prevNode = -1;
		for(int i = s; S != 0; S ^= (1<<i), i = prevNode){
			path.addFirst(i);
			prevNode = prev[S][i];
		}
		path.addFirst(s);
	}
	/** buildPath recursive ver. */
	private void buildPath(int S, int v, List<Integer> path){
		if(S != 0) buildPath(prev[S][v], S & ~(1<<v), path);
		path.add(v);
	}
}