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

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

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

Общая информация[править]

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

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

Задача с волком, козой и капустой

Задача с мостом и факелом

Решения некоторых головоломок, представленные в виде временных шкал

К известным головоломкам о переправе через реку относятся:

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

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

Формулировка с использованием теории графов[править]

Пусть Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G=(V, E)} — неориентированный граф, множество вершин Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle V} которого представляет предметы, которые должен нести фермер, а множество ребер Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle E} состоит из пар конфликтующих предметов. Например, если вершина Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle v_1} представляет гуся, а Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle v_2} — мешок фасоли, то эти две вершины будут соединены, поскольку гуся нельзя оставлять на одной стороне реки с мешком фасоли. Обратите внимание, что ребра являются неориентированными, поскольку характер конфликта между двумя предметами не влияет на тот факт, что их нельзя оставлять на одной стороне реки. Цель задачи — определить минимальный размер лодки, при котором переправа возможна; это известно как «число Алькуина» графа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G} .

Рассмотрим успешную переправу через реку, при которой фермер сначала перевозит подмножество Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle V'} предметов через реку, оставляя оставшиеся Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle V \setminus V'} предметы на берегу. Поскольку переправа успешна, не должно быть конфликтов между предметами, оставшимися на берегу; то есть в Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G} нет ребер в Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle E} между любыми двумя элементами из Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle V \setminus V'} . Это подразумевает, что все ребра Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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$ ^[7].

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

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

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

Источники[править]

↑ ^1,0 ^1,1 Peterson, Ivars (2003), "«Tricky crossings»", Science News Т. 164 (24), <http://www.sciencenews.org/articles/20031213/mathtrek.asp>. Проверено 7 февраля 2008. .
↑ p. 74, Pressman, Ian & Singmaster, David (1989), "«"The Jealous Husbands" and "The Missionaries and Cannibals"»", The Mathematical Gazette (The Mathematical Association) . — Т. 73 (464): 73–81, DOI 10.2307/3619658 .
↑ ^3,0 ^3,1 Borndörfer, Ralf; Grötschel, Martin & Löbel, Andreas (1995), «Alcuin's Transportation Problems and Integer Programming», Preprint SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, <http://www.zib.de/Publications/Reports/SC-95-27.ps.Z> .
↑ Schwartz, Benjamin L. (1961), "«An analytic method for the "difficult crossing" puzzles»", Mathematics Magazine Т. 34 (4): 187–193, DOI 10.2307/2687980 .
↑ ^5,0 ^5,1 ^5,2 Csorba, Péter; Hurkens, Cor A. J. & Woeginger, Gerhard J. (2008), "The Alcuin number of a graph", «Algorithms: ESA 2008», vol. 5193, Lecture Notes in Computer Science, Springer-Verlag, сс. 320–331, DOI 10.1007/978-3-540-87744-8_27 .
↑ Bellman, Richard (1962), "«Dynamic programming and "difficult crossing" puzzles»", Mathematics Magazine (Mathematical Association of America) . — Т. 35 (1): 27–29, DOI 10.2307/2689096 .
↑ River Crossings (and Alcuin Numbers) — Numberphile.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Руниверсалис» («Руни», руни.рф) под названием «Задачи о переправе», расположенная по адресу:

—	https://руни.рф/Задачи_о_переправе

Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC BY-SA.

Всем участникам Руниверсалиса предлагается прочитать «Обращение к участникам Руниверсалиса» основателя Циклопедии и «Почему Циклопедия?».

[a-1] 1,0 ^1,1 Peterson, Ivars (2003), "«Tricky crossings»", Science News Т. 164 (24), <http://www.sciencenews.org/articles/20031213/mathtrek.asp>. Проверено 7 февраля 2008. .

[2] . 74, Pressman, Ian & Singmaster, David (1989), "«"The Jealous Husbands" and "The Missionaries and Cannibals"»", The Mathematical Gazette (The Mathematical Association) . — Т. 73 (464): 73–81, DOI 10.2307/3619658 .

[b-3] 3,0 ^3,1 Borndörfer, Ralf; Grötschel, Martin & Löbel, Andreas (1995), «Alcuin's Transportation Problems and Integer Programming», Preprint SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, <http://www.zib.de/Publications/Reports/SC-95-27.ps.Z> .

[4] Schwartz, Benjamin L. (1961), "«An analytic method for the "difficult crossing" puzzles»", Mathematics Magazine Т. 34 (4): 187–193, DOI 10.2307/2687980 .

[:0-5] 5,0 ^5,1 ^5,2 Csorba, Péter; Hurkens, Cor A. J. & Woeginger, Gerhard J. (2008), "The Alcuin number of a graph", «Algorithms: ESA 2008», vol. 5193, Lecture Notes in Computer Science, Springer-Verlag, сс. 320–331, DOI 10.1007/978-3-540-87744-8_27 .

[6] Bellman, Richard (1962), "«Dynamic programming and "difficult crossing" puzzles»", Mathematics Magazine (Mathematical Association of America) . — Т. 35 (1): 27–29, DOI 10.2307/2689096 .

[7] River Crossings (and Alcuin Numbers) — Numberphile.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

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

Содержание

Общая информация[править]

Формулировка с использованием теории графов[править]

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

Источники[править]

Навигация

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

Общая информация[править]

Формулировка с использованием теории графов[править]

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

Источники[править]

Навигация

Поиск