我知道这已被问过,但我没有在任何帖子中找到答案。有人可以建议我一个枚举图中所有哈密顿路径的算法吗?枚举*所有*哈密尔顿路径
有点背景:我正在研究一个问题,我必须列举每个哈密尔顿路径,做一些分析并返回结果。为此,我需要列举所有可能的哈密尔顿路径。
谢谢。
我知道这已被问过,但我没有在任何帖子中找到答案。有人可以建议我一个枚举图中所有哈密顿路径的算法吗?枚举*所有*哈密尔顿路径
有点背景:我正在研究一个问题,我必须列举每个哈密尔顿路径,做一些分析并返回结果。为此,我需要列举所有可能的哈密尔顿路径。
谢谢。
按照建议使用BFS/DFS,但不要停在第一个解决方案。 BFS/DFS的主要用途(在这种情况下)将是找到所有的解决方案,你需要给它一个条件停止在第一个。
谢谢。你能否详细说明你的意思是“解决方案”。据我所知,在图上运行DFS将简单地给出访问节点序列(例如,对于具有顶点A,B,C,D的图的A→B→C→D)。但它永远不会“探索”所有可能的路径。你能否详细说明一下? – 2011-04-23 23:56:31
DFS和BFS都会为您提供从特定节点开始的所有可能路径。从这些哈密尔顿路径中,那些长度与图形大小完全相同的节点,每个节点只存在一次。所以如果你有一个有5个节点的图,并且有一个p1-> p2-> p3-> p4-> p5的路径,它就是一个哈密尔顿路径。另外请注意,您将不得不从每个节点开始搜索。 – SinistraD 2011-04-24 00:46:39
谢谢SinistraD,这非常有帮助! – 2011-04-24 20:52:31
我的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;
}
}
深度优先穷举搜索给你的答案汉密尔顿路径。我刚刚完成了一个Java实现了这个问题(包括代码)写了起来:
http://puzzledraccoon.wordpress.com/2012/06/07/how-to-cool-a-data-center/
解决方案在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)))
你尝试普通的搜索? BFS/DFS?你的图表有多大? – slezica 2011-04-23 18:47:23
圣地亚哥,谢谢你的回复。我的图很小(6-7节点)。我曾考虑过BFS和DFS,但我认为BFS/DFS用于搜索特定的密钥,而不是列举所有可能的路径。我如何让BFS/DFS生成*所有*可能的周期.. – 2011-04-23 20:11:14
定期BFS/DFS找到匹配的第一个键后停止。你只需要改变它,让它遍历整个图(如果可能的话),并将其记录为解决方案。 – slezica 2011-04-23 23:28:39