Я ищу код Python для сопоставления максимального веса/минимальной стоимости на двухстороннем графике. Я использую общий код соответствия максимального веса в NetworkX, но я нахожу его слишком медленным для своих нужд. Вероятно, это связано как с тем, что общий алгоритм медленнее, так и с тем, что решение NetworkX полностью реализовано в Python. В идеале я бы хотел найти некоторый код Python для двухсторонней проблемы соответствия, которая обертывает некоторый код C/С++, но прямо сейчас, что-то быстрее, чем реализация NetworkX, будет полезна.
Максимальный вес/минимальная стоимость Двусторонний код соответствия в Python
Ответ 1
После некоторого дальнейшего исследования я нашел особенно полезным следующие два модуля (http://pypi.python.org/pypi/pyLAPJV/0.3 и http://pypi.python.org/pypi/hungarian). Это оба алгоритма, реализованные в С++ с привязками Python, и работают намного быстрее, чем реализация соответствия NetworkX. Однако реализация pyLAPJV, по-видимому, слишком непостоянна для моих нужд и плохо обрабатывает одинаково взвешенные края. Венгерский модуль (хотя, предположительно, медленнее алгоритма pyLAPJV) работает примерно на 3 порядка быстрее, чем реализация NetworkX по размерам данных, с которыми я сейчас сталкиваюсь. Я также собираюсь еще раз взглянуть на код, предложенный кунигами, поскольку я считаю, что его можно запустить, хотя Шедскин довольно легко дать достаточно быструю реализацию.
Ответ 2
Пробовали ли вы scipy реализацию венгерского алгоритма, также известного как алгоритм Munkres или Kuhn-Munkres?
Ответ 3
Не слишком уверен, что это то, что вы ищете, но это реализация python алгоритма сопоставления двухстороннего графа Hopcroft-Karp. Если нет, это может быть хорошим отправным местом для вас.
Ответ 4
Двухуровневое сопоставление минимального веса может быть разрешено венгерским алгоритмом (wikipedia). Ссылка в wikipedia ссылается на python. Я не уверен, что это быстрее, чем код, который вы упомянули.