Проблема двудольного назначения с наименьшей стоимостью

Question

Любые идеи о том, как реализовать эффективный алгоритм (лучше, чем O (n ² )) для решения задачи присваивания в двудольном графе?

Основная идея заключается вследующее:

У меня есть два идентичных набора, скажем, S1 = [A,B,C,D] и S2 = [A,B,C,D], и есть некоторые ребра между различными элементами наборов с заданной стоимостью, например, A->B (cost 4), B->C (cost 3), C->A (cost 10), D->A (cost 6).

Я хочу найти лучшее назначение так, чтобы: количество назначенных элементов было максимальным с наименьшей общей стоимостью.(Количество назначенных элементов является более важным).

Таким образом, для этого примера лучшим назначением будет:

A->D (cost 6)  
B->C (cost 3)  

[A,B,C,D] там, где назначено, а стоимость минимальна: 9

Еще один, но не лучший вариант:

A->B (cost 4)  

Остальные не могут быть назначены, поскольку A уже назначено, таким образом, назначение не максимально максимально

Я разработал жадное решение в O (n ² ), которое слишком медленное.

Размеры комплектов обычно небольшие (5-10) элементов.

Answer 1

Звучит так, будто вам нужно максимальное не двудольное соответствие: 1 , 2 .

Алгоритм довольно сложно реализовать, и я не видел ни одногореализации вокруг, особенно если вы хотите минимальную стоимость.Для такого маленького ввода, на мой взгляд, лучше перебором.

Как вы решили это с жадным алгоритмом?Вы уверены, что это работает?

Answer 2

Я предполагаю, что у вас есть неориентированный граф, и вы хотите выбрать максимальное количество ребер таким образом, чтобы на одном узле не было двух ребер (элемент node = set в вашем описании). Вы также хотите разорвать связи, используя минимальную общую стоимость выбранных ребер. Дайте мне знать, если это не соответствует тому, что вы просите.

Создайте двойной граф из приведенного выше (один узел для каждого исходного ребра, два узла соединены, если соответствующие исходные ребра попадают в одну и ту же вершину). Затем вы ищете максимальный независимый набор двойных узлов. К сожалению, это сложная проблема. И это только для максимального количества ребер, возможно, немного сложнее разорвать связи, используя веса. К счастью для вас, ваш N 5-10, так что вы можете использовать его грубо.