最短ハミルトン路問題
最短ハミルトン路問題とは，有向・無向グラフが与えられたときに全ての頂点を通過する最短のpathを見つける問題です．巡回セールスマン問題は最短ハミルトン閉路問題であるので紛らわしいが，巡回セールスマン問題が閉路，最短ハミルトン路問題が開路です．最短ハミルトン路問題はあまり有名ではなく，どちらかといえば巡回セールスマン問題の亜種のような捉え方がよくされているようです．巡回セールスマン問題同様にNP困難（多項式時間で計算する手法が見つかっていない問題）となります．
以下の2サイトを参考にさせていただきました．
http://codeforces.com/blog/entry/337
https://algo-logic.info/bit-dp/
動的計画法（Dynamic Programming）
動的計画法は部分最適性のある問題において利用される手法であり，問題サイズを1から順に積み重ねることにより効率的な計算を行う方法です．最短ハミルトン路問題においては，動的計画法を用いることで計算量をO(n*2^n)に短縮することが可能です．総当たりの計算量がO(n!)であり，10回程度で限界を迎えますが，動的計画法を用いることで20回程度まで現実時間で計算することが可能になります．
計算量オーダー
最短ハミルトン路問題では以下のように動的計画法を用います．
dp[S][v] : 頂点集合Sにおいて，終点をvとする最短ハミルトン路長
dp[S][v] = min{dp[S \ v][i] + d(i,v)}
S \ v : vを除いた頂点集合S
i : S \ v の頂点
d(i,v) : i,v間の距離
終点を追加することで上手く動的計画法に落とし込んでいます．
頂点vを終点とする最短ハミルトン路は，頂点iを終点とする最短ハミルトン路でiとvを接続したもののうち，最短のpathである
ということです．少しピンとこないかもしれませんが，
pathである以上，vを終点とするためには，その他の頂点から接続される
⇒その他の頂点までのpathは自由なので，最短ハミルトン路+(i,j)が最短となる
⇒それぞれの頂点での作成したものを比較して，最短のpathが最短ハミルトン路
というロジックです．
これだけ見ると殆ど計算量がないように見えますが，頂点集合Sの取り方は組み合わせ数だけありますので，実際にはかなりの計算量となります．そのため，20程度までしか計算できません．実計算では必要のない部分は計算を行いませんので，その分短縮されて上記のような計算量オーダーとなっています．
以下コードです．
package hamiltonian;
import algorithm.algorithm_core.*;
import groovy.util.PermutationGenerator;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import static java.lang.Math.min;
public class HamiltonianDPCalculator {
private final int oNodeNumber;
private final Presenter oPresenter;
private final List<Node> oNodes;
private int[][] g;
private int[][] dp;
private static int INF = 1000000;
HamiltonianDPCalculator(int aNodeNumber){
oNodeNumber = aNodeNumber;
g = new int[oNodeNumber][oNodeNumber];
dp = new int[1 << oNodeNumber][oNodeNumber];
List<Position> positions = Position.createRandomPositions(oNodeNumber);
oNodes = Node.createNodes(positions, Node.ConnectionCreator.ALL);
oPresenter = SwingPresenter.createPresenter(oNodes, false);
oPresenter.setColorProvider(new ColorProvider(){});
}
public void launch(){
//initialize
StringBuilder builder = new StringBuilder();
for(int i = 0; i < oNodeNumber; i++){
for(int j = 0; j < oNodeNumber; j++){
g[i][j] = (int)oNodes.get(i).getDistance(oNodes.get(j));
builder.append(String.format("%3d", g[i][j])).append(",");
}
builder.append("\n");
}
System.out.println("g[i][j]");
System.out.println(builder.toString());
int min = INF;
int endIndex = -1;
for(int i = 0; i < oNodeNumber; i++){
int mask = (1 << oNodeNumber) - 1;
dp[mask][i] = recursiveSearchMinimum(mask, i);
if(min > dp[mask][i]){
min = dp[mask][i];
endIndex = i;
}
}
System.out.println("shortest hamiltonian path cost:" + min);
//caution:this shortestList requires to be reversed
List<Node> shortestList = new ArrayList<>();
shortestList.add(oNodes.get(endIndex));
int mask = (1 << oNodeNumber) - 1;
while(true){
for(int k = 0; k < oNodeNumber; k++){
if(k == endIndex){
continue;
}
// System.out.println("endIndex:" + k);
// System.out.println("dp[(1 << oNodeNumber) - 1][endIndex]:" + dp[(1 << oNodeNumber) - 1][endIndex]);
// System.out.println("dp[((1 << oNodeNumber) - 1) ^ (1 << endIndex)][k]:" + dp[((1 << oNodeNumber) - 1) ^ (1 << endIndex)][k] + ", g[k][endIndex]:" + g[k][endIndex]);
if(dp[mask][endIndex] == (dp[mask ^ (1 << endIndex)][k] + g[k][endIndex])){
// System.out.println("updated");
mask = mask & ~(1 << endIndex);
endIndex = k;
shortestList.add(oNodes.get(endIndex));
break;
}
}
if(shortestList.size() == oNodeNumber){
break;
}
}
Collections.reverse(shortestList);
int length = 0;
builder.setLength(0);
for(int i = 0; i < shortestList.size(); i++){
builder.append("[").append(shortestList.get(i).getId()).append("],");
if(i < shortestList.size() - 1){
length += shortestList.get(i).getDistance(shortestList.get(i+1));
}
}
System.out.println("shortest path:" + builder.toString() + " cost:" + length);
oPresenter.highLightPathPlan(shortestList);
permutationCheck(g);
}
/**
*
* @param mask
* @param i
* @return
*/
private int recursiveSearchMinimum(int mask, int i){
// System.out.println("mask:" + Integer.toBinaryString(mask) + ",i:" + i);
//mask has only i
// System.out.println("mask >> i : " + Integer.toBinaryString(mask >> i) + ", mask & ~(1 << i):" + Integer.toBinaryString(mask & ~(1 << i)));
if(((mask >> i) & 1) == 1 && (mask & ~(1 << i)) == 0){
// System.out.println("mask has only i:" + i);
return 0;
}
//mask doesn't include i
if(((mask >> i) & 1) == 0){
// System.out.println("mask doesn't include i:" + i);
return INF;
}
//if already calculated
if(dp[mask][i] != 0){
// System.out.println("dp[mask][i]:" + dp[mask][i] + " is already calculated");
return dp[mask][i];
}
int min = INF;
for(int j = 0; j < oNodeNumber; j++){
if(mask >> j == 0){
//do nothing
}else{
min = min(min, recursiveSearchMinimum(mask ^ (1 << i), j) + g[j][i]);
}
}
//update
dp[mask][i] = min;
return min;
}
private void permutationCheck(int[][] g){
new Thread(){
@Override
public void run() {
List<Integer> list = new ArrayList<>();
for(int i = 0; i < oNodeNumber; i++){
list.add(i);
}
PermutationGenerator<Integer> permutationGenerator = new PermutationGenerator<>(list);
int min = INF;
while(permutationGenerator.hasNext()){
List<Integer> candidate = permutationGenerator.next();
int cost = 0;
for(int i = 0; i < candidate.size() - 1; i++){
cost += g[candidate.get(i)][candidate.get(i+1)];
}
if(cost < min){
min = cost;
}
}
System.out.println("permutationCheck:" + min);
}
}.start();
}
}
Presenter関連については，他のmoduleもないと動きません．githubにcodeを公開しています．
https://github.com/cony26/algorithm/blob/774433e4aeabc86f93075a7cffd2d61e4d0eedba/algorithm-core/src/main/java/hamiltonian/HamiltonianDPCalculator.java
permutationCheckは順列による総当たりチェックです．10程度までしか機能しないので気を付けてください．
初めてビットで集合を扱うという方法を取りましたが，すごく便利ですね．勉強になりました．これから集合を扱う場合はこの方法で集合を表現したいと思います．
