1

我想在 Python 中实现禁忌搜索来解决与图形相关的问题（查找树、着色问题和那种东西）。我已经用 Python 编写了基本代码，这是我第一次编写类似的代码。我知道算法是如何工作的（理论上），但我在实现它时遇到了一些麻烦。

生成随机解决方案以便我可以启动算法的最佳方法是什么？我想从初始图生成一棵随机树：

graph = { "a" : ["c"],
      "b" : ["c", "e"],
      "c" : ["a", "b", "d", "e"],
      "d" : ["c"],
      "e" : ["c", "b"],
      "f" : []
    }

我正在使用这些函数来查看边缘和孤立节点：

def generate_edges(graph):
    edges = []
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))

    return edges

print(generate_edges(graph))


def find_isolated_nodes(graph):
    """ returns a list of isolated nodes. """
    isolated = []
    for node in graph:
        if not graph[node]:
            isolated += node
    return isolated

print(find_isolated_nodes(graph))

而这个找到路径：

def find_all_paths(self, start_vertex, end_vertex, path=[]):
""" find all paths from start_vertex to
    end_vertex in graph """
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
    return [path]
if start_vertex not in graph:
    return []
paths = []
for vertex in graph[start_vertex]:
    if vertex not in path:
        extended_paths = self.find_all_paths(vertex,
                                             end_vertex,
                                             path)
        for p in extended_paths:
            paths.append(p)
return paths

我需要的是找到一棵树作为随机解决方案，这样我就可以更改它，直到我拥有的图表中最大的可能。

最好的方法是什么？谢谢你。

4

0 回答 0