алгоритм сокращения минимума karger в python 2.7
Вот мой код для алгоритма минимального разреза karger. Насколько мне известно, алгоритм, который я реализовал, прав. Но я правильно понял ответ. Если кто-то может проверить, что происходит, я был бы признателен.
import random from random import randint #loading data from the text file# with open('data.txt') as req_file: mincut_data = [] for line in req_file: line = line.split() if line: line = [int(i) for i in line] mincut_data.append(line) #extracting edges from the data # edgelist = [] nodelist = [] for every_list in mincut_data: nodelist.append(every_list[0]) temp_list = [] for temp in range(1,len(every_list)): temp_list = [every_list[0], every_list[temp]] flag = 0 for ad in edgelist: if set(ad) == set(temp_list): flag = 1 if flag == 0 : edgelist.append([every_list[0],every_list[temp]]) #karger min cut algorithm# while(len(nodelist) > 2): val = randint(0,(len(edgelist)-1)) print val target_edge = edgelist[val] replace_with = target_edge[0] should_replace = target_edge[1] for edge in edgelist: if(edge[0] == should_replace): edge[0] = replace_with if(edge[1] == should_replace): edge[1] = replace_with edgelist.remove(target_edge) nodelist.remove(should_replace) for edge in edgelist: if edge[0] == edge[1]: edgelist.remove(edge) print ('edgelist remaining: ',edgelist) print ('nodelist remaining: ',nodelist) Данные тестового примера:
- Парные пары, находящие минимальное использование python
- Как ключи работают в мин и макс?
- Поиск наименьшего поплавка в файле, а затем печать и над ним
1 2 3 4 7 2 1 3 4 3 1 2 4 4 1 2 3 5 5 4 6 7 8 6 5 7 8 7 1 5 6 8 8 5 6 7
Скопируйте его в текстовый файл и сохраните его как «data.txt» и запустите программу
Ответ должен быть: число минимальных разрезов равно 2, а разрезы – по краям [(1,7), (4,5)]
4 Solutions collect form web for “алгоритм сокращения минимума karger в python 2.7”
Таким образом, алгоритм Каргера является «случайным алогоритом». То есть каждый раз, когда вы запускаете его, он создает решение, которое никоим образом не гарантируется. Общий подход заключается в том, чтобы запускать его много раз и поддерживать наилучшее решение. Для множества конфигураций будет множество решений, которые являются лучшими или примерно лучшими, поэтому вы эвристически быстро найдете хорошее решение.
Насколько я вижу, вы только запускаете алгоритмы один раз. Таким образом, решение вряд ли будет оптимальным. Попробуйте запустить его 100 раз для цикла и придерживаться наилучшего решения.
Этот код также работает.
import random, copy data = open("***.txt","r") G = {} for line in data: lst = [int(s) for s in line.split()] G[lst[0]] = lst[1:] def choose_random_key(G): v1 = random.choice(list(G.keys())) v2 = random.choice(list(G[v1])) return v1, v2 def karger(G): length = [] while len(G) > 2: v1, v2 = choose_random_key(G) G[v1].extend(G[v2]) for x in G[v2]: G[x].remove(v2) G[x].append(v1) while v1 in G[v1]: G[v1].remove(v1) del G[v2] for key in G.keys(): length.append(len(G[key])) return length[0] def operation(n): i = 0 count = 10000 while i < n: data = copy.deepcopy(G) min_cut = karger(data) if min_cut < count: count = min_cut i = i + 1 return count print(operation(100))
Как сказал Фил, мне приходилось запускать свою программу 100 раз. И еще одна коррекция в коде:
for edge in edgelist: if edge[0] == edge[1]: edgelist.remove(edge)
Эта часть кода неправильно устранила автопилы. Поэтому мне пришлось изменить код:
for i in range((len(edgelist)-1),-1,-1): if edgelist[i][0] == edgelist[i][1]: edgelist.remove(edgelist[i])
И эта линия не нужна. поскольку целевой узел будет автоматически изменен на автоматический цикл, и он будет удален.
edgelist.remove(target_edge)
Затем, как было сказано ранее, программа была зациклирована в 100 раз, и я получил минимальное сокращение по рандомизации. π
Рассматривая ответы этого сообщения, я наткнулся на комментарий Джоэла. Согласно алгоритму Каргера, край должен выбираться равномерно случайным образом. Вы можете найти мою реализацию, основанную на ответе Оскара и комментарии Джоэла ниже:
class KargerMinCutter: def __init__(self, graph_file): self._graph = {} self._total_edges = 0 with open(graph_file) as file: for index, line in enumerate(file): numbers = [int(number) for number in line.split()] self._graph[numbers[0]] = numbers[1:] self._total_edges += len(numbers[1:]) def find_min_cut(self): min_cut = 0 while len(self._graph) > 2: v1, v2 = self._pick_random_edge() self._total_edges -= len(self._graph[v1]) self._total_edges -= len(self._graph[v2]) self._graph[v1].extend(self._graph[v2]) for vertex in self._graph[v2]: self._graph[vertex].remove(v2) self._graph[vertex].append(v1) self._graph[v1] = list(filter(lambda v: v != v1, self._graph[v1])) self._total_edges += len(self._graph[v1]) self._graph.pop(v2) for edges in self._graph.values(): min_cut = len(edges) return min_cut def _pick_random_edge(self): rand_edge = randint(0, self._total_edges - 1) for vertex, vertex_edges in self._graph.items(): if len(vertex_edges) <= rand_edge: rand_edge -= len(vertex_edges) else: from_vertex = vertex to_vertex = vertex_edges[rand_edge] return from_vertex, to_vertex