Привет!Я новичок в Python и до сих пор много часов борюсь с проблемой, касающейся реализации алгоритма Shortest Path в Python.
Ожидается, что я решу некоторую задачу по нахождению кратчайших путей (проблема графа) среди заданных лиц, и в конце найду обычного человека, который соединит их всех.
I 'Пока мы сделали что-то вроде этого:
import itertools
class centralperson():
def initialization(self,N,data,a,b,c):
self.data = data
self.N = N
self.a = a
self.b = b
self.c = c
self.list_of_values = [self.a,self.b,self.c]
self.list_of_paths = []
self.common_person = []
def makeGraph(self):
# Create dict with empty list for each key
graph = {key: [] for key in range(self.N)}
self.graph = graph
for key in self.graph:
for x in self.data:
if key in x:
x = x.copy()
x.remove(key)
self.graph[key].extend(x)
def find_path(self,start, end):
path = []
path = path + [start]
if start == end:
return path
if start not in self.graph.keys():
raise ValueError('No such key in graph!')
for node in self.graph[start]:
if node not in path:
newpath = self.find_path(self.graph, node, end, path)
if newpath: return newpath
return self.list_of_paths.append(path)
def findPaths(self):
for pair in itertools.combinations(self.list_of_values, r=5):
self.find_path(*pair)
def commonperson(self):
list_of_lens = {}
commonalities = set(self.list_of_paths[0]) & set(self.list_of_paths[1]) & set(self.list_of_paths[2])
for i in self.list_of_values:
list_of_lens[i] = (len(self.graph[i]))
if len(commonalities)>1 or len(commonalities)<1:
for k,v in list_of_lens.items():
if v==1 and self.graph[k][0] in commonalities:
output = self.graph[k]
self.common_person.append(output)
else:
output = list(commonalities)
self.common_person.append(output)
return
def printo(self):
#return(self.common_person[0])
return(self.list_of_paths,self.list_of_values)
Описание каждой функции и входов:
N -> количество уникальных узлов
a, b,c -> некоторые произвольно выбранные узлы, чтобы найти общий среди них
initialization -> просто инициализировать наши глобальные переменные, используемые в других методах, и сохранить список выходных данных
makeGraph -> создает смежностьСписок из входа.
find_path -> найти путь между двумя заданными узлами (рекурсия обратного отслеживания)
findPaths -> ожидалось, что здесь будет вызываться find_path для каждой комбинации A, B, C, т. Е. A-> B,A-> C, B-> C
commonperson -> ожидается, что найдет обычного человека из вывода списка list_of_paths
printo -> распечатать этого обычного человека
Обычно это работает (я думаю), когда я запускаю каждую функцию отдельно.Но когда я пытаюсь создать из него огромный класс, он не работает :(
Я думаю, что проблема в этой рекурсивной функции find_path. Предполагается, что нужно найти путь между двумя людьмии добавьте путь к списку результатов со всеми путями. Тем не менее, поскольку у меня есть 3 разных человека, а find_path является рекурсивной функцией только с 2 параметрами.
Следовательно, мне нужно найти все пути, которыесоединяет их (3 пути) и добавляет к большему списку list_of_paths. Я создал def findPaths, чтобы использовать itertools.combinations, и в функции для цикла cal find_path для каждой комбинации аргументов начала и концаэта функция, но, кажется, не работает ...
Можете ли вы помочь мне с этим? Также я не знаю, как запустить все def functions одновременно, потому что, честно говоря, я бы не хотелзапускать все экземпляры класса отдельно ... Моя желаемая версия:
Предоставить входные данные для класса, т. е .: N,data,a,b,c, где N - количество уникальных узлов, данные - это просто список списка сназначенные сети, и A, B, C - мои лица.
Get Output: что является обычным для всех этих 3 человек (я планировал сохранить его в списке common_person.