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

Волк, коза и капуста

YouTube video

Задачи о переправе через реку — тип головоломки, в которой цель состоит в том, чтобы переправить предметы с одного берега реки на другой, обычно за наименьшее количество рейсов.

Общая информация

Сложность головоломки может возникать из-за ограничений на то, какие или сколько предметов можно перевозить одновременно, или какие или сколько предметов можно безопасно оставлять вместе. Обстановка может незначительно меняться, например, река — на мост.

Самые ранние известные задачи о переправе через реку встречаются в рукописи 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$; это образует нижнюю границу числа Алькуина графа $G$: $Alcuin(G)\geq \tau (G)$.

С другой стороны, можно совершить успешную переправу с размером лодки, равным $\tau (G)+1$. Этого можно добиться, потребовав, чтобы члены $V'$ минимального вершинного покрытия все время оставались в лодке; их количество равно $\tau (G)$, и, таким образом, в лодке остается ещё одно место. Поскольку среди оставшихся предметов $V\setminus V'$ нет конфликтов, их можно перевозить через реку по одному в любом порядке, занимая одно оставшееся место в лодке. Таким образом, $Alcuin(G)\leq \tau (G)+1$, что образует верхнюю границу для $Alcuin(G)$. Объединяя их вместе, получаем $\tau (G)\leq Alcuin(G)\leq \tau (G)+1$, то есть либо $Alcuin(G)=\tau (G)$, либо $Alcuin(G)=\tau (G)+1$.

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

См. также

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

Источники

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Руниверсалис» («Руни», руни.рф) под названием «Задачи о переправе», расположенная по адресу: — «https://руни.рф/index.php/Задачи_о_переправе» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC BY-SA. Всем участникам Руниверсалиса предлагается прочитать «Обращение к участникам Руниверсалиса» основателя Циклопедии и «Почему Циклопедия?».