Задача о минимальном числе свадеб

[constkir]

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

[gris]

То есть если все ребяты влюблены в королеву деревни, а пастуху нравятся все девушки, то женив его на королеве, мы решаем проблему одной свадьбой.
Мнение девиц не учитывается... О, темпора, понимаешь, о море, море, мир бездонный.
Я видел, как такую задачу, правда в чисто производственной формулировке, решали простым перебором, постепенно удаляя неактуальные рёбра.

[Sefko]

gris в сообщении #479870 писал(а):

Я видел, как такую задачу, правда в чисто производственной формулировке, решали простым перебором, постепенно удаляя неактуальные рёбра.

Необычная для производства, как мне кажется, формулировка. Даже любопытно стало. Обычно (то, с чем приходилось иметь дело) все же ставится задача максимизации, а не минимизации пар.

[gris]

На производстве минимизируют отходы, издержки, затраты, длину маршрутов, время изготовления, брак, да много чего ещё. Самое обидное, что и зарплату тоже
В реальном производстве трудно представить изоморфную задачу, поскольку даже с невестами минимизация количества пар приводит к возрастанию напряжённости. Да и мнение девушек тоже надо учитывать.
Минимизация нужна тогда, когда влюблённость в девушек (перенесённая в производственные термины) является для молодого человека навязанной и обременительной.

На самом деле есть целый ряд задач, упрощенно сводящихся к "невестиной" схеме: Есть некоторое количество объектов двух видов. Между ними возникают паразитные связи. При установлении легальной связи между двумя объектами все паразитные, связанные с ними, уничтожаются. Задача: уничтожить паразитные связи, установив минимальное количество легальных.
Обычно существуют веса рёбер, стоимость установления легальной связи и прочие ограничения, да и задача решается в динамике. А теория, как правило, рассматривает идеальную модель без всяких неприятных неожиданностей. Хотя работает в достаточно стабильных, но огромных системах, где интуиция Петровича уже не срабатывает.

[worm2]

Зацепила задачка
Придумал переформулировку: на шахматной доске $m\times n$ несколько клеток закрашены красным цветом. Требуется поставить на красные клетки минимальное число ладей, чтобы они били все красные клетки (считаем, что ладья бьёт клетку, на которой стоит).

[mserg]

Скорее всего, хороший пакет линейного программирования решит эту задачу, даже если деревня очень большая (типа Москвы

[Sefko]

mserg в сообщении #480439 писал(а):

Скорее всего, хороший пакет линейного программирования решит эту задачу, даже если деревня очень большая (типа Москвы

При практической постановке все много проще - хороший пакет без надобности. На практике вполне достаточен заметное улучшение, в сравнении с методом случайного тыка. Найти оптимальное решение - это совсем другая задача. Требовать Доказательства того, что найденное решение является оптимальным, вообще никто не будет.

Более того. В тех случаях, с которыми приходилось иметь дело мне, даже от предложений улучшения алгоритма отказывались: как-то "свадьбы" происходят - и ладно.

С этой точки зрения - не математической, а скорее психологической - интересно не столько решение, сколько постановка. То есть реальные примеры, когда людям это надо.
Впрочем, тут я могу быть совсем неправ. То, что мне реально не попадалась четко выраженная потребность, не есть повод для обобщений.

[maxal]

constkir в сообщении #479867 писал(а):

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

Цитата из http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximal_matchings
no polynomial-time algorithm is known for finding a minimum maximal matching, that is, a maximal matching that contains the smallest possible number of edges.

Вот здесь утверждается, что задачи NP-полна для регулярных двудольных графов:
http://www.springerlink.com/content/y054412l308t754j/