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

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

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

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

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

Пусть ${\displaystyle G=(V,E)}$ — неориентированный граф, множество вершин которого ${\displaystyle V}$ представляет объекты, которые фермер должен перевезти, а множество рёбер ${\displaystyle E}$ которого состоит из конфликтующих пар объектов. Например, если вершина ${\displaystyle v_{1}}$ представляет гуся, а ${\displaystyle v_{2}}$ представляет мешок бобов, то две эти вершины будут соединены ребром, поскольку гусь не может быть оставлен на берегу вместе с мешком с бобами. Заметим, что рёбра неорентированные, поскольку причина конфликта между объектами не влияет на факт, что они не могут быть оставлены на том же самом берегу. Задача состоит в определении минимальной вместимости лодки, при которой пересечение реки возможно Это число известно как число Алкуина графа ${\displaystyle G}$.

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

С другой стороны, можно завершить успешно переправу с лодкой вместимостью ${\displaystyle \tau (G)+1}$. Этого можно достичь, требуя, чтобы элементы ${\displaystyle V'}$ минимального вершинного покрытия оставались на лодке все время. Это число элементов ${\displaystyle \tau (G)}$ с одним дополнительным место в лодке. Поскольку среди оставшихся элементов ${\displaystyle V\setminus V'}$ нет конфликтов, они могут быть взяты по одному для пересечения реки в любом порядке, занимая одно оставшееся место в лодке. Таким образом, ${\displaystyle {\rm {{Alcuin}(G)\leqslant \tau (G)+1}}}$, что даёт верхнюю границу для ${\displaystyle {\rm {{Alcuin}(G)}}}$. Объединив два неравенства получим ${\displaystyle \tau (G)\leqslant {\rm {{Alcuin}(G)\leqslant \tau (G)+1}}}$, то есть, либо ${\displaystyle {\rm {{Alcuin}(G)=\tau (G)}}}$, либо ${\displaystyle {\rm {{Alcuin}(G)=\tau (G)+1}}}$^[7].

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

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

• Видео YouTube