Лексикографически наименьшее идеальное соответствие

Question

Я хочу найти лексикографически наименьшее идеальное соответствие в двух частичных графиках.Я должен использовать алгоритм Куна, но я не понимаю, как сделать совпадение лексикографически наименьшим.Это вообще возможно в алгоритме Куна?Я могу предоставить свой код, но он достаточно классический.

Answer 1

В большинстве случаев, как это, обычно проще сделать сокращение, а не модифицировать алгоритм:

• Найдите способ изменить исходные данные в вашей задаче так, чтобы лексикографический порядок разорвал все связи (но таким образом, чтобы идеальные соответствия все же имели более высокий балл, чем несовершенные)
• Запустить измененный граф по алгоритму Куна.
• При необходимости переведите ответ обратно на исходную задачу.

---

Я не пытался на самом деле решить это сам или прочитать проблему подробно. Но, похоже, это учебное упражнение, и я чувствую, что этого ответа достаточно: -)

Answer 2

Подумайте, как вы можете создать цены заданий, которые поощряют лексикографически раннее сопоставление.

Answer 3

В качестве подсказки подумайте, как вы можете определить, где должен совпадать только первый узел в лекс-минском сопоставлении.