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

Известные головоломки о переправе включают:

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

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

Формулировка с использованием теории графов Пусть — неориентированный граф, множество вершин которого представляет объекты, которые фермер должен перевезти, а множество рёбер которого состоит из конфликтующих пар объектов. Например, если вершина представляет гуся, а представляет мешок бобов, то две эти вершины будут соединены ребром, поскольку гусь не может быть оставлен на берегу вместе с мешком с бобами. Заметим, что рёбра неорентированные, поскольку причина конфликта между объектами не влияет на факт, что они не могут быть оставлены на том же самом берегу. Задача состоит в определении минимальной вместимости лодки, при которой пересечение реки возможно Это число известно как число Алкуина графа .

Рассмотрим успешное пересечение реки, в котором фермер перевозит сначала подмножество через реку, оставив множество объектов на берегу. Поскольку первое пересечение успешно, не должно быть конфликтов между оставшимися объектами на берегу. То есть, в графе нет рёбер из между любыми двумя элементами множества . Из этого следует, что все рёбра имеют одну или две вершины в , то есть, что является вершинным покрытием графа . Таким образом, вместимость лодки должна быть не меньше размера минимального вершинного покрытиямножества . Эта величина равна нижней границей чисел Алкуина графа : .

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

Чсорба, Хуркенс и Воегингер доказали в 2008 году, что определение, которое и равенств и выполняется, является NP-трудной задачей. Задача о вершинном покрытии является NP-полной, из чего следует, что вычисление числа Алкуина графа NP-трудно. Однако для некоторых классов графов выполняются более сильные результаты. Например, для планарных графов, определение, которое из двух равенств выполняется, можно выполнить pf полиномиальное время (хотя определение или остаётся NP-трудной задачей). Для двудольных графов и могут быть вычислены за полиномиальное время.

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

Примечания

Ссылки Видео YouTube

Категория:Логические игры