Как я могу создать случайное дерево в Python? - PullRequest
Новая
       25

Как я могу создать случайное дерево в Python?

0 голосов
/ 26 февраля 2019

Я хочу реализовать Tabu Search в 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))

И этот, чтобы найтиpaths: 

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

Мне нужно найти дерево как случайное решение, чтобы я мог менять его до тех пор, пока на графике не появится максимально возможное значение.

Что может бытьлучший способ сделать это?Спасибо.

...