algorithm - *すべて*のハミルトニアン パスを列挙する

Question

これは以前に尋ねられたことは知っていますが、どの投稿にも答えが見つかりませんでした。グラフ内のすべてのハミルトニアン パスを列挙するアルゴリズムを提案してもらえますか?

ちょっとした背景: 私は、各ハミルトニアン パスを列挙し、何らかの分析を行い、結果を返さなければならない問題に取り組んでいます。そのためには、考えられるすべてのハミルトニアン パスを列挙できる必要があります。

ありがとう。

Answer 1

私のJavaコード：（絶対に再帰的な方法に基づいています）

アルゴリズム：

+ 1 点から開始して、別の点に接続します (パスを形成するため)。

+パスを削除し、グラフのすべてのポイントを接続するまで、最新のポイントで新しいパスを再帰的に見つけます。

+パスを削除し、最新の点からハミルトン パスを形成できない場合は最初のグラフに戻ります

public class HamiltonPath {
public static void main(String[] args){
    HamiltonPath obj = new HamiltonPath();

    int[][]x = {{0,1,0,1,0},  //Represent the graphs in the adjacent matrix forms
                {1,0,0,0,1},
                {0,0,0,1,0},
                {1,0,1,0,1},
                {0,1,0,1,0}};

    int[][]y = {{0,1,0,0,0,1},
                {1,0,1,0,0,1},
                {0,1,0,1,1,0},
                {0,0,1,0,0,0},
                {0,0,1,0,0,1},
                {1,1,0,0,1,0}};

    int[][]z = {{0,1,1,0,0,1},
                {1,0,1,0,0,0},
                {1,1,0,1,0,1},
                {0,0,1,0,1,0},
                {0,0,0,1,0,1},
                {1,0,1,0,1,0}};

    obj.allHamiltonPath(y);   //list all Hamiltonian paths of graph
    //obj.HamiltonPath(z,1);  //list all Hamiltonian paths start at point 1


}

static int len;
static int[]path;
static int count = 0;    

public void allHamiltonPath(int[][]x){  //List all possible Hamilton path in the graph
    len = x.length;
    path = new int[len];
    int i;
    for(i = 0;i<len;i++){ //Go through column(of matrix)
        path[0]=i+1;
        findHamiltonpath(x,0,i,0);
    }
}

public void HamiltonPath(int[][]x, int start){ //List all possible Hamilton path with fixed starting point
    len = x.length;
    path = new int[len];
    int i;
    for(i = start-1;i<start;i++){ //Go through row(with given column)
        path[0]=i+1;
        findHamiltonpath(x,0,i,0);
    }
}

private void findHamiltonpath(int[][]M,int x,int y,int l){

    int i;
        for(i=x;i<len;i++){         //Go through row

            if(M[i][y]!=0){      //2 point connect

                if(detect(path,i+1))// if detect a point that already in the path => duplicate 
                    continue;

                l++;            //Increase path length due to 1 new point is connected 
                path[l]=i+1;    //correspond to the array that start at 0, graph that start at point 1
                if(l==len-1){//Except initial point already count =>success connect all point
                    count++;   
                    if (count ==1)
                System.out.println("Hamilton path of graph: ");
                    display(path);
                    l--;
                    continue;
                }

                M[i][y]=M[y][i]=0;  //remove the path that has been get and
                findHamiltonpath(M,0,i,l); //recursively start to find new path at new end point
                l--;                // reduce path length due to the failure to find new path         
                M[i][y] = M[y][i]=1; //and tranform back to the inital form of adjacent matrix(graph)
            }
     }path[l+1]=0;    //disconnect two point correspond the failure to find the..   
}                     //possible hamilton path at new point(ignore newest point try another one)         

public void display(int[]x){

   System.out.print(count+" : ");
    for(int i:x){
        System.out.print(i+" ");
    }
        System.out.println();   
}

private boolean detect(int[]x,int target){ //Detect duplicate point in Halmilton path 
    boolean t=false;                        
    for(int i:x){
        if(i==target){
            t = true;
            break;
        }
    }
    return t;
}  

}

Answer 2

提案どおりに BFS/DFS を使用しますが、最初の解決策にとどまらないでください。BFS/DFS の主な用途 (この場合) は、すべてのソリューションを見つけることです。最初のソリューションで停止するように条件を設定する必要があります。

Answer 3

深さ優先の徹底的な検索で答えが得られます。この問題に対する Java 実装 (コードを含む) についての記事を書き終えました。

http://puzzledraccoon.wordpress.com/2012/06/07/how-to-cool-a-data-center/