logo标签列表

枚举*所有*哈密顿路径

algorithmhamiltonian-cycle
7

我知道这个问题以前已经被问过了，但是我在任何帖子中都没有找到答案。有人能否建议一个算法来枚举图中的所有哈密顿路径？

一点背景：我正在解决一个问题，在这个问题中，我必须枚举每个哈密顿路径，进行一些分析，并返回结果。为此，我需要能够枚举所有可能的哈密顿路径。

谢谢。

你尝试过普通搜索吗？BFS/DFS算法呢？你的图有多大？ - salezica
Santiago，感谢您的回复。我的图很小（6-7个节点）。我确实考虑过BFS和DFS，但我认为BFS/DFS用于搜索特定键而不是枚举所有可能的路径。我该如何让BFS/DFS生成所有可能的循环？ - Darth.Vader
常规的BFS / DFS在找到第一个匹配的键后就会停止。您只需要更改它，让它遍历整个图（如果可能），并将其作为解决方案记录下来。 - salezica
4个回答
3

我的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;
}

}

3

建议使用BFS/DFS算法，但不要停留在第一个解决方案上。BFS/DFS的主要用途（在这种情况下）是找到所有的解决方案，你需要给它设置一个条件，以便在找到第一个解决方案后停止。

谢谢。您能否详细说明一下什么是“解决方案”。据我所知，在图上运行DFS只会给出一个访问节点的序列（例如，对于具有顶点A、B、C、D的图，序列为A->B->C->D）。但它永远不会“探索”所有可能的路径。您能否详细说明一下？ - Darth.Vader
1
无论是DFS还是BFS，都可以给你从特定节点开始的所有可能路径。其中哈密顿路径是那些长度恰好等于图大小且每个节点仅出现一次的路径。因此，如果你有一个包含5个节点的图，并且存在一条p1->p2->p3->p4->p5的路径，那么它就是一个哈密顿路径。另外请注意，你需要从每个节点开始搜索。 - Máthé Endre-Botond
谢谢SinistraD，非常有帮助！ - Darth.Vader
1

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)))
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接