Перейти к содержанию

Задача о переправе

Статья из Авикипедии. Энциклопедии

Задача о переправе — это разновидность логической головоломки, цель которой заключается в перемещении объектов с одного берега реки на другой, как правило, за минимальное количество ходов. Сложность может определяться ограничениями на количество и тип объектов, перевозимых за один рейс, а также на их безопасное совместное пребывание на берегу. Иногда условия варьируются, например, река заменяется мостом. Самые ранние известные задачи такого рода встречаются в рукописи «Propositiones ad Acuendos Juvenes» («Задачи для развития молодого ума»), традиционно приписываемой Алкуину. Древнейшие копии этого труда датируются IX веком и содержат три задачи о пересечении реки, включая головоломки про лису, гуся и мешок бобов, а также про миссионеров и людоедов.

Известные примеры[править | править код]

Среди классических головоломок о переправе выделяются следующие:

  • **Волк, коза и капуста** — фермеру необходимо перевезти через реку на лодке, вмещающей только его и один предмет, лису, гуся и мешок бобов, при условии, что лиса не может оставаться наедине с гусем, а гусь — с мешком бобов. В других версиях объектами могут выступать волк, коза и капуста или аналогичные комбинации.
  • **Задача о миссионерах и людоедах** — трое миссионеров и трое людоедов должны пересечь реку в лодке, вмещающей не более двух человек, с ограничением: на любом берегу количество людоедов не должно превышать число миссионеров, если они присутствуют вместе. В похожей задаче о семейных парах три пары должны переправиться с условием, что женщина не может находиться рядом с чужим мужчиной без своего мужа.
  • **Propositio de viro et muliere ponderantibus plaustrum** — из сборника «Propositiones ad Acuendos Juvenes», где мужчина и женщина одинакового веса, а также двое детей, каждый из которых весит вдвое меньше взрослого, должны переплыть реку в лодке, выдерживающей вес только одного взрослого.

Для анализа этих задач применяются методы теории графов, динамического программирования и целочисленного программирования.

Формулировка в терминах теории графов[править | править код]

Пусть \(G=(V, E)\) — неориентированный граф, где множество вершин \(V\) соответствует объектам, которые нужно перевезти, а множество рёбер \(E\) состоит из пар конфликтующих объектов. Например, если вершина \(v_1\) представляет гуся, а \(v_2\) — мешок бобов, между ними проводится ребро, поскольку их нельзя оставлять вместе на берегу. Рёбра неориентированы, так как причина конфликта не влияет на запрет их совместного пребывания. Задача сводится к определению минимальной вместимости лодки, при которой переправа возможна; это значение называется **числом Алкуина** графа \(G\).

Рассмотрим успешную переправу, при которой фермер сначала перевозит подмножество \(V'\), оставляя на берегу \(V \setminus V'\). Поскольку конфликтов между оставшимися объектами быть не должно, в графе \(G\) нет рёбер из \(E\), соединяющих любые две вершины из \(V \setminus V'\). Следовательно, все рёбра \(E\) инцидентны хотя бы одной вершине из \(V'\), то есть \(V'\) является вершинным покрытием графа \(G\). Таким образом, вместимость лодки должна быть не меньше размера \(\tau(G)\) минимального вершинного покрытия \(G\), что задаёт нижнюю границу числа Алкуина: \(\rm{Alcuin}(G) \geqslant \tau(G)\).

С другой стороны, переправу можно успешно завершить при вместимости лодки \(\tau(G) + 1\). Для этого элементы минимального вершинного покрытия \(V'\) постоянно находятся в лодке, занимая \(\tau(G)\) мест, а оставшееся место используется для поочерёдной перевозки объектов из \(V \setminus V'\), между которыми нет конфликтов. Отсюда следует верхняя граница: \(\rm{Alcuin}(G) \leqslant \tau(G) + 1\). Объединяя неравенства, получаем \(\tau(G) \leqslant \rm{Alcuin}(G) \leqslant \tau(G) + 1\), то есть число Алкуина равно либо \(\tau(G)\), либо \(\tau(G) + 1\).

В 2008 году Чсорба, Хуркенс и Воегингер доказали, что определение, какое из равенств \(\rm{Alcuin}(G) = \tau(G)\) или \(\rm{Alcuin}(G) = \tau(G) + 1\) выполняется, является NP-трудной задачей. Поскольку задача о вершинном покрытии также NP-трудна, вычисление числа Алкуина для произвольного графа \(G\) относится к этому классу сложности. Однако для некоторых типов графов существуют более эффективные алгоритмы. Например, для планарных графов можно за полиномиальное время определить, какое из равенств верно, хотя нахождение точных значений \(\rm{Alcuin}(G)\) или \(\tau(G)\) остаётся NP-трудным. Для двудольных графов оба параметра вычисляются за полиномиальное время.

См. также[править | править код]

  • Задача о вершинном покрытии

Примечания[править | править код]

Ссылки[править | править код]

Ссылки[править | править код]