找出随机生成的无定向简单图是否有哈密顿圈

2024-03-28 23:09:11 发布

您现在位置:Python中文网/ 问答频道 /正文

我知道这个问题以前已经被问过十几次了,但我试着按照几个不同的指南去做,似乎不明白为什么我的特定算法不起作用

代码如下:

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)

似乎这种算法有一半的时间是有效的。我认为我的问题是,我没有正确地回溯(甚至根本不知道如何回溯),这意味着一旦算法到达无法继续的位置,它就不会回溯并尝试任何其他方法

我如何实现这一点?有人能给我指一个能向我解释的资源吗

谢谢


Tags: andofthepathforreturnifis
1条回答
网友
1楼 · 发布于 2024-03-28 23:09:11

如果有人发现这篇文章没有得到爱,需要一些指导,我就知道问题出在哪里了

事实证明,通过在checkVertex函数(i)中使用计数器值,它限制了解决问题的方式。我也不需要将任何东西从一个函数传递到另一个函数,因为从技术上讲,我定义事物的方式是这样的,矩阵、路径等在python中是全局的。(我通常用C++编写代码,但听说使用Python更容易解决这个问题)。p>

无论如何,下面是带有适当注释的代码:

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阶的图表进行测试,即使找到一个循环也要花我的电脑大约一个小时,我只测试了一次

相关问题 更多 >