Максимальное взвешенное двустороннее соответствие, ограничение: порядок каждого графа сохраняется - PullRequest
Новая
       11

Максимальное взвешенное двустороннее соответствие, ограничение: порядок каждого графа сохраняется

6 голосов
/ 28 февраля 2012

Допустим, у меня есть два набора: (n_1, n_2, ...) и (m_1, m_2, ...) и совпадающая функция match (n, m), которая возвращает значение от 0 до 1. Я хочучтобы найти соответствие между двумя наборами так, чтобы были соблюдены следующие ограничения:

  • Каждый элемент должен иметь не более 1 сопоставленного элемента в противоположном наборе.
  • Несопоставленные элементы будут спареныс фиктивным элементом по цене 1
  • Максимальная сумма функции соответствия применительно ко всем элементам
  • У меня возникают проблемы с формальным выражением, но если вы выстроили каждый набор параллельно каждомудругие с их оригинальным порядком и проведут линию между соответствующими элементами, ни одна из линий не пересечется.Пример [n_1 <-> m_2, n_2 <-> m_3] является допустимым отображением, но [n_1 <-> m_2, n_2 <-> m_1] - нет.

(я считаю, что первые триявляются стандартными взвешенными двухсторонними сопоставлениями, но я указал их в случае, если я неправильно понял взвешенное двудольное сопоставление)

Это относительно просто сделать с исчерпывающим поиском по экспоненциальному времени (по отношению к размеру наборов),но я надеюсь, что решение за полиномиальное время (в идеале O ((| n | * | m |) ^ 3) или лучше) существует.

Я искал изрядное количество по "проблеме назначения" / "«Взвешенное двустороннее сопоставление» и видел варианты с различными ограничениями, но не нашел того, который соответствовал или который я смог уменьшить до одного с этим добавленным ограничением порядка.У вас есть идеи о том, как я могу решить это?Или, может быть, грубое доказательство того, что оно не разрешимо за полиномиальное время (для моих целей также подойдет сокращение до NP-завершения)?

1 Ответ

7 голосов
/ 28 февраля 2012

Эта проблема была изучена под названием «несоответствие максимального веса». Есть простая квадратичная динамическая программа. Пусть M (a, b) будет значением оптимального соответствия для n 1 ,…, n a и m 1 ,…, m б . У нас есть повторение

M (0, b) = -b
М (а, 0) = -а
M (a, b) = max {M (a - 1, b - 1) + совпадение (a, b), M (a - 1, b) - 1, M (a, b - 1) - 1}.

Отслеживая значения argmax, вы можете восстановить оптимальное решение по его значению.

Если в совпадении содержится значительно меньше квадратичного числа записей, превышающего -1, существует алгоритм, который выполняется по линейному алгоритму времени по числу полезных записей ( Khoo и Cong, быстрый многослойный маршрутизатор общей области для MCM Дизайн ).

...