我知道这个问题以前被问过十几次，但我试过遵循几个不同的指南，似乎不明白为什么我的特定算法不起作用。
这是代码：
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
#The reason we went with this algorithm instad of filling a matrix with random int from 0,1 to begin with is because this is always a simple graph, while
#the other approach almost never makes one. So, rather than checking and fixing those graphs, we thought this would be faster and easier
def makeGraph(order):
p = .5 #represents the probability of an edge being created between any 2 verticies, if less than .4 its almost never connected for values 10+.
g = nx.erdos_renyi_graph(order, p) #generates the graph, verticies are 0-order, edges are ordered pairs of these numbers
return g
def Hamiltonian(matrix, order, path, currentVertex):
while(True):
if(currentVertex >= order):
print("There is no H cycle")
return
checkVertex(matrix, order, path, currentVertex)
if(path[currentVertex] == 0):
print("There is no H cycle")
return
if(currentVertex == (order-1) and matrix[path[currentVertex]][0] == 1):
path.append(0)
print("Hamiltonian found, path is:", path)
break
else:
Hamiltonian(matrix, order, path, currentVertex + 1)
return
def checkVertex(matrix, order, path, currentVertex):
i=1
while(True):
path[currentVertex] = ((path[currentVertex]+i)%order)
if(path[currentVertex] == 0):
return
if(matrix[path[currentVertex-1]][path[currentVertex]] == 1):
for j in range (0, currentVertex+1):
if(j != currentVertex and path[j] == path[currentVertex]):
path[currentVertex] = 0
i+=1
break
if(j == currentVertex):
return
else:
path[currentVertex] = 0
i+=1
#IN = input("Enter the number of desired vertices: ") #get input for number of verticies
#order = int(IN) #make input string an int
#TODO remove hard coded order
order = 10
graph = makeGraph(order) #make the graph
#TODO remove printing of edges/nodes
#print("Number of nodes: ", graph.nodes)
print("Edges: ", graph.edges)
#init matrix filled with 0's for conversion
matrix = np.random.randint(0,1,(order,order))
#makes a pretty picture of the graph, great for finding cycles visually
#nx.draw(graph, with_labels=True)
#plt.show()
#convert ordered pairs into adj matrix for easier calculation
for i in range (0, order):
for j in range (0, order):
e = (i,j)
if(graph.edges.__contains__(e)):
matrix[i][j] = 1 #if there is an edge between vertex i and vertex j, append the matrix to have a 1 in the ith column jth row
path = [0] * (order) #init list to have n 0's
currentVertex = 1 #start the current vertex at 1
#matrix = [[0,0,1,0,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,1,0,0],[1,1,1,0,0]] #for testing, known cycle
Hamiltonian(matrix, order, path, currentVertex)
看来这种算法大约有一半的时间是有效的。我认为我的问题是，我没有正确地进行回溯(甚至根本不知道该怎么做(，这意味着一旦算法到达无法继续的位置，它就不会回去尝试其他任何事情。
我该如何实现？有人能给我指一个可以向我解释的资源吗？
谢谢！
对于任何发现这篇没有得到爱并且需要一些指导的帖子的人，我都弄清楚了问题所在。
事实证明，通过在我的checkVertex函数(i(中使用计数器值，它限制了解决问题的方式。我也不需要从一个函数传递到另一个函数，因为从技术上讲，我定义事物的方式是，矩阵、路径等在python中是全局的。(我通常用C++编写代码，但听说使用python更容易解决这个问题(。
无论如何，以下是带有适当注释的代码：
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import sys
import random
#The reason we went with this algorithm instad of filling a matrix with random int from 0,1 to begin with is because this is always a simple graph, while
#the other approach almost never makes one. So, rather than checking and fixing those graphs, we thought this would be faster and easier
def makeGraph(order):
x = random.randint(2,10)
p = (x/10) #represents the probability of an edge being created between any 2 verticies, if less than .2 its almost never connected for values 10+.
g = nx.erdos_renyi_graph(order, p) #generates the graph, verticies are 0 to order, edges are ordered pairs of these numbers
return g
def Hamiltonian(currentVertex):
while(True): #do this until we find a cycle or show there isnt one
if(currentVertex == order): #once the value of cV is the order of G, its likely we found a cycle
if(matrix[path[currentVertex-1]][0] == 1): #but, we should only cont. if there is for sure an edge from the last vertex and 0
path.append(0) #add 0 to the end to illustrate that the path ends at 0
print("There is a cycle, a path is: ", path)
paintGraph()
else:
return
checkVertex(currentVertex) #dont have a cycle yet, so try again
#if after check vertex the current vertex is 0,
#we know that something went wrong so try a new value of cv, starting from 0
if(path[currentVertex] == 0):
return
Hamiltonian(currentVertex+1) #move on to the next vertex and try to find the next proper vertex
def checkVertex(cV):
while(True):
path[cV] = ((path[cV]+1)%order) #starting at 1, try and find a path from the last vertex to the cV
if(path[cV] == 0): #because of the mod, if checkVertex has tried every possible vertex then we know to return
return
if(matrix[path[cV-1]][path[cV]] == 1): #if there is an edge from the last vertex and the current vertex
#loop to ensure there are no duplicates
for j in range (0, cV+1):
if(path[j] == path[cV] and j!=cV):
break
if(j == cV):
if(cV<order): #if we arent at the end of the path yet, keep trying
return
#if we are on a potential end, then we should make sure that we can get back to 0,
#otherwise, we should try again.
if(cV == order and matrix[path[cV]][0] == 1):
return
else:
break
#this is for when we did find a cycle
def paintGraph():
nx.draw(graph, with_labels=True)
plt.show()
#the sys.exit is so that once we did find a cycle we stop looking, because the way
#I have things Hamiltonian would find all possible cycles
sys.exit("Finished")
IN = input("Enter the number of desired vertices: ") #get input for number of verticies
order = int(IN) #make input string an int
graph = makeGraph(order) #make the graph
#init matrix filled with 0's for conversion
matrix = np.random.randint(0,1,(order,order))
nx.draw(graph, with_labels=True)
plt.show()
#convert ordered pairs into adj matrix for easier calculation
for i in range (0, order):
for j in range (0, order):
e = (i,j)
if(graph.edges.__contains__(e)):
matrix[i][j] = 1 #if there is an edge between vertex i and vertex j, append the matrix to have a 1 in the ith column jth row
matrix[j][i] = 1
path = [0]*order #init list to have n 0's
currentVertex = 1 #start the current vertex at 1
Hamiltonian(currentVertex)
#If hamiltonian didn't find a cycle and force sys.exit, then we know no cycle exists
print("There is no Hamiltonian cycle")
#draw the graph again just so we can check.
nx.draw(graph, with_labels=True)
plt.show()
希望这对某人有所帮助。解决这个问题很有趣，所以在复制粘贴之前一定要自己动手！
编辑：如果你想知道为什么我有一个sys.exit调用，那是因为我只关心找到一个H循环。按照这个代码的编写方式，我们将找到给定图的所有H循环。
这可能需要很长时间。事实上，这个算法的运行时间是O(n！*log(n((，其中n是图的顺序。这个代码必须用50阶的图形进行测试，即使找到一个周期也需要我的电脑大约一个小时，而我只测试过一次。