我知道这个问题以前已经被问过十几次了,但我试着按照几个不同的指南去做,似乎不明白为什么我的特定算法不起作用
代码如下:
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更容易解决这个问题)。p>
无论如何,下面是带有适当注释的代码:
希望这对某人有帮助。这是相当有趣的解决,所以一定要尝试自己做之前,复制粘贴
编辑:如果你想知道为什么我有一个sys.exit调用,那是因为我只关心找到一个H循环。按照编写此代码的方式,我们将找到给定图的所有H圈
这可能需要很长时间。实际上,该算法的运行时间是O(n!*log(n)),其中n是图的顺序。这段代码必须用50阶的图表进行测试,即使找到一个循环也要花我的电脑大约一个小时,我只测试了一次
相关问题 更多 >
编程相关推荐