algorithm - 枚举 *all* hamiltonian 路径

Question

我知道以前有人问过这个问题，但我在任何帖子中都没有找到答案。有人可以建议我一种算法，它可以在图中枚举所有哈密顿路径吗？

一点背景知识：我正在研究一个问题，我必须枚举每个哈密顿路径，进行一些分析，然后返回结果。为此，我需要能够列举所有可能的汉密尔顿路径。

谢谢。

Answer 1

按照建议使用 BFS/DFS，但不要停留在第一个解决方案上。BFS/DFS 的主要用途（在这种情况下）将是找到所有解决方案，您需要为其设置一个条件以在第一个解决方案处停止。

Answer 2

我的java代码：（绝对基于递归方法）

算法：

+从一个点开始连接到它可以看到的另一个点（形成一条路径）。

+删除路径并在最新点递归查找新路径，直到连接图形的所有点。

+如果不能从最新点形成汉密尔顿路径，则删除路径并回溯到初始图

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 3

Python3中的解决方案：

def hamiltonians(G, vis = []):
    if not vis:
        for n in G:
            for p in hamiltonians(G, [n]):
                yield p
    else:
        dests = set(G[vis[-1]]) - set(vis)
        if not dests and len(vis) == len(G):
            yield vis
        for n in dests:
            for p in hamiltonians(G, vis + [n]):
                yield p
G = {'a' : 'bc', 'b' : 'ad', 'c' : 'b', 'd' : 'ac'}
print(list(hamiltonians(G)))

Answer 4

深度优先的详尽搜索可以为您提供答案。我刚刚完成了有关此问题的 Java 实现的文章（包括代码）：

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