Загадка о переправе через реку

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

Проблема волка , козла и капусты

Проблема с мостом и факелом

Решения некоторых загадок обозначены в виде временных рамок

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

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

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

Теоретико-графовая формулировка

Позволять $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$ . ^{[ 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 ]}

См. также

Крышка вершины

Ссылки

^ Перейти обратно: ^а ^б Петерсон, Иварс (2003), «Хитрые переходы» , Science News , 164 (24) , получено 7 февраля 2008 г.
^ с. 74, Прессман, Ян; Сингмастер, Дэвид (1989), «Ревнивые мужья» и «Миссионеры и каннибалы », The Mathematical Gazette , 73 (464), The Mathematical Association: 73–81, doi : 10.2307/3619658 , JSTOR 3619658 .
^ Перейти обратно: ^а ^б Борндорфер, Ральф; Гретшель, Мартин ; Лебель, Андреас (1995), Транспортные проблемы Алкуина и целочисленное программирование , препринт SC-95-27, Центр информационных технологий Конрада Цузе в Берлине, заархивировано из оригинала 19 июля 2011 г.
^ Шварц, Бенджамин Л. (1961), «Аналитический метод для решения головоломок с «трудным скрещиванием»», Mathematics Magazine , 34 (4): 187–193, doi : 10.2307/2687980 , JSTOR 2687980 .
^ Перейти обратно: ^а ^б ^с Чорба, Питер; Хуркенс, Кор А.Дж.; Воегингер, Герхард Дж. (2008), «Число Алкуина графа», Алгоритмы: ESA 2008 , Конспекты лекций по информатике, том. 5193, Шпрингер-Верлаг, стр. 320–331, номер документа : 10.1007/978-3-540-87744-8_27 .
^ Беллман, Ричард (1962), «Динамическое программирование и головоломки с «трудным пересечением»», Mathematics Magazine , 35 (1), Mathematical Association of America: 27–29, doi : 10.2307/2689096 , JSTOR 2689096 .
^ Числофил (05.01.2018). Переправы через реки (и числа Алкуина) — Numberphile . Проверено 17 мая 2024 г. - через YouTube.

Внешние ссылки

видео на YouTube

[a-1] Перейти обратно: ^а ^б Петерсон, Иварс (2003), «Хитрые переходы» , Science News , 164 (24) , получено 7 февраля 2008 г.

[2] с. 74, Прессман, Ян; Сингмастер, Дэвид (1989), «Ревнивые мужья» и «Миссионеры и каннибалы », The Mathematical Gazette , 73 (464), The Mathematical Association: 73–81, doi : 10.2307/3619658 , JSTOR 3619658 .

[b-3] Перейти обратно: ^а ^б Борндорфер, Ральф; Гретшель, Мартин ; Лебель, Андреас (1995), Транспортные проблемы Алкуина и целочисленное программирование , препринт SC-95-27, Центр информационных технологий Конрада Цузе в Берлине, заархивировано из оригинала 19 июля 2011 г.

[4] Шварц, Бенджамин Л. (1961), «Аналитический метод для решения головоломок с «трудным скрещиванием»», Mathematics Magazine , 34 (4): 187–193, doi : 10.2307/2687980 , JSTOR 2687980 .

[:0-5] Перейти обратно: ^а ^б ^с Чорба, Питер; Хуркенс, Кор А.Дж.; Воегингер, Герхард Дж. (2008), «Число Алкуина графа», Алгоритмы: ESA 2008 , Конспекты лекций по информатике, том. 5193, Шпрингер-Верлаг, стр. 320–331, номер документа : 10.1007/978-3-540-87744-8_27 .

[6] Беллман, Ричард (1962), «Динамическое программирование и головоломки с «трудным пересечением»», Mathematics Magazine , 35 (1), Mathematical Association of America: 27–29, doi : 10.2307/2689096 , JSTOR 2689096 .

[7] Числофил (05.01.2018). Переправы через реки (и числа Алкуина) — Numberphile . Проверено 17 мая 2024 г. - через YouTube.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]