Блог

Главная - Вопросы по программированию - график венгерского алгоритма на python

график венгерского алгоритма на python

#python #hungarian-algorithm

#python #венгерский-алгоритм

Вопрос:

Я пытаюсь реализовать венгерский алгоритм в своем проекте, но я не понимаю, почему он дает бесконечный цикл…Я пробовал с другим бибартовым графом, и он работает. Поэтому я хочу знать, что не так с моим графиком G 

  from hungarian_algorithm import algorithm
 G={
'agt2': {'Commentaire':200,'PhotoProfil': 8, 'PhotoSupp': 10, 'Prenom': 0}, 
'coco': {'Commentaire': 300, 'PhotoProfil': 200, 'PhotoSupp': 300, 'Prenom': 300}
 }
res=algorithm.find_matching(G,matching_type='max',return_type='list')
print(res)

Комментарии:

1. Это объект hungarian_algorithm

2. Я не знаком с этим конкретным пакетом, это может быть ошибка в этой реализации. Возможно, вы могли бы использовать более устоявшуюся реализацию, например scipy.optimize.linear_sum_assignment ?

3. Вы можете попробовать свой график в этой онлайн-версии алгоритма, чтобы доказать, что это не ваш график: венгерский алгоритм . Он также предоставляет пошаговое описание решения.

4. Проблема не в моем графике! Я буду использовать scipy.optimize.linear_sum_assignment. Спасибо

5. @TojoRandrianarimanana SciPy наконец-то сработал для вас? Я нахожусь в очень похожем положении, и я понял, что библиотека венгерского алгоритма не работает для некоторых входных графиков. Я тоже хочу переключиться на SciPy, поэтому просто хотел спросить, получилось ли у вас, чтобы он работал на вас

Ответ №1:

График в порядке, вероятно, это ошибка в реализации этого пакета. Как указано в моем комментарии, вместо этого вы можете использовать scipy.optimize.linear_sum_assignment from SciPy.

Например

 import numpy as np
from scipy.optimize import linear_sum_assignment

# solve the assignment problem
G = np.array([[200, 8,   10,  0],
              [300, 200, 300, 300]])
row_indices, col_indices = linear_sum_assignment(G, maximize=True)

# print results
row_names = ['agt2', 'coco']
col_names = ['Commentaire', 'PhotoProfil', 'PhotoSupp', 'Prenom']
edges = [((row_names[r], col_names[c]), G[r, c]) for r, c in zip(row_indices, col_indices)]
print(edges)

С принтами

 [(('agt2', 'Commentaire'), 200), (('coco', 'PhotoSupp'), 300)]

Комментарии:

1. Хорошо, извините меня, я новый участник: D