#python #algorithm #graph-theory #implementation
Вопрос:
Нам дана m x n матрица w , которая представляет веса ребер в полном двудольном графе K_m,n . Мы хотим найти карту {1,...,m} -> {1,...,n} с минимальным весом, которая является инъективной или сюръективной. выбор карты эквивалентен v {1,...,m} выбору ровно одного ребра, падающего на каждую вершину v .
Позволь m<=n . Инъективную функцию с минимальным весом можно найти, выполнив поиск идеального соответствия с минимальным весом. В Python это реализовано в scipy :
import numpy as np
import scipy, scipy.optimize
w=np.random.rand(5,10)
print(scipy.optimize.linear_sum_assignment(w))
Позволь m>=n . Как можно найти сюръективную функцию с минимальным весом? Я ищу конкретную реализацию в Python.
Комментарии:
1. Все ли веса ребер неотрицательны? Если это так, этот пост может помочь ; так как это проблема с краевым покрытием с минимальным весом
2. @kcsquared Разве это не правда, что покрытие ребра может иметь ребра, которые падают на набор доменов из m вершин? Это означало бы, что у нас нет карты, а скорее многоуровневая карта.
3. Это правда. Насколько велики m и n и являются ли веса неотрицательными? Возможно, это можно преобразовать в целочисленную линейную программу (с экспоненциальным временем выполнения).
4. Я бы рекомендовал, чтобы computer science stackexchange с гораздо большей вероятностью предложил помощь в решении этой проблемы. В scipy.optimize нет функции для вашего вопроса, и эксперт в теории графов с большей вероятностью узнает, является ли это открытой проблемой или доказано, что она NP-трудна.
5. Это хорошее приближение, но оно не всегда самое дешевое (мне не ясен точный коэффициент приближения). Рассмотрим
[[3 5 6], [4 3 8], [8 2 3], [8 5 5]], какой из них имеет 4 строки и 3 столбца. Первые 3 строки имеют минимальное значение 9, например, столбцы0,1,2. Это распространяется на полную карту с минимальной стоимостью 14, добавив элемент последней строки. Однако столбцы0,1,1,2дают полную карту минимальной стоимости 13. Кроме того, назначение минимальной стоимости первых 3 строк не может быть расширено до карты минимальной стоимости всех 4. Чтобы использовать свою стратегию, вам также нужно будет перебрать всеm choose nспособы выбора первых n строк.
Ответ №1:
ПРАВКА: Оказывается, я, возможно, неправильно понял ваш вопрос.
От инъективного к сюръективному
Если m > n у вас уже есть алгоритм , который обрабатывает это дело m <= n , затем поменяйте местами два компонента. Ваш алгоритм даст вам инъективную функцию от второго компонента к первому. Возьмите обратную эту функцию; это будет сюръективная функция от подмножества первого компонента ко второму компоненту.
С помощью networkx
То, что вы ищете,-это соответствие максимальной мощности в двудольном графике.
Библиотека python networkx содержит несколько функций для этого. Стандартными проблемами являются «соответствие максимальной мощности» и «соответствие максимального веса»; Я был бы удивлен, если бы существовала функция для непосредственного решения вашей проблемы «соответствие максимальной мощности с минимальным весом».
Однако мне кажется , что ваша проблема была эквивалентна нахождению соответствия максимального веса в взвешенном графике, полученном путем замены каждого веса w на W-w , где W какое-то очень большое значение (например, в три раза больше максимального веса в исходном графике).
Включив это большое значение W в вес каждого ребра, вы заставляете соответствие максимального веса соответствовать максимальной мощности. И , включая отрицательное значение -w , вы просите алгоритм найти ребра с наименьшим возможным исходным весом в исходном графике.
Комментарии:
1. После перечитывания поста я подозреваю, что утверждение «Выбор карты эквивалентен тому, что для каждой вершины v в {1,…,m} выбор ровно одного ребра, инцидентного v» подразумевает, что OP хочет избежать выбора только подмножества m вершин
2. @kcsquare оооооооооооооооо я вижу
3. Если я правильно понял, вы обращаетесь к «инъекционной» части моего поста, но это я уже решил. Проблема, с которой я сталкиваюсь, связана с «сюръективной» частью.