Головоломка переправа представляет собой тип головоломки , в которой объект должен нести элементы из одной реки в другую, как правило , в наименьшее количество поездок. Сложность головоломки может возникнуть из-за ограничений на то, какие или сколько предметов можно транспортировать одновременно, или какие или сколько предметов можно безопасно оставить вместе. [1] Настройку можно изменить косметически, например, заменив реку мостом. [1] Самые ранние известные проблемы с переходом через реки встречаются в рукописи Propositiones ad Acuendos Juvenes (английский язык: проблемы для заострения молодых ), традиционно написанной Алкуином.. Самые ранние копии этой рукописи датируются IX веком; он содержит три проблемы перехода через реку, включая загадку лисы, гуся и мешка с фасолью и проблему ревнивых мужей . [2]
Известные головоломки о переходе через реки включают в себя:
- Лисица, гусь и мешок фасоль головоломки , в которой фермер должен транспортировать лисица, гусь и мешок бобов с одной стороны реки на другой , используя лодку , которая может содержать только один элемент в дополнении к фермеру, при условии ограничения, что лису нельзя оставлять наедине с гусем, а гуся нельзя оставлять наедине с бобами. Также были заявлены эквивалентные головоломки с участием лисы, курицы и мешка с зерном, или волка, козы и капусты и т. Д.
- Проблема ревнивых мужей , в которой три супружеские пары должны пересечь реку на лодке, вмещающей не более двух человек, при условии, что ни одна женщина не может находиться в присутствии другого мужчины, если ее муж также не присутствует. Это похоже на проблему миссионеров и каннибалов , в которой три миссионера и три каннибала должны пересечь реку с тем ограничением, что в любое время, когда и миссионеры, и каннибалы стоят на любом берегу, людоедов на этом берегу не может быть больше миссионеров. .
- Проблема с мостом и факелом .
- Propositio de viro et muliere ponderantibus plaustrum . В этой задаче, также встречающейся в Propositiones ad Acuendos Juvenes , мужчина и женщина равного веса вместе с двумя детьми, каждый из которых весит половину своего веса, хотят пересечь реку, используя лодку, которая может нести вес только одного взрослого. [3]
Эти проблемы могут быть проанализированы с использованием теории графов методы, [4] [5] с помощью динамического программирования , [6] или путем целочисленного программирования . [3]
См. Также [ править ]
Ссылки [ править ]
- ^ a b Петерсон, Иварс (2003), "Tricky crossings" , Science News , 164 (24) , получено 07 февраля 2008 г. CS1 maint: обескураженный параметр ( ссылка ).
- ^ стр. 74, Прессман, Ян; Singmaster, Дэвид (1989), " " Ревнивая Мужья "и "Миссионеры и каннибалы " ", Математическая газета Математическая ассоциация, 73 (464): 73-81, DOI : 10,2307 / 3619658 , JSTOR 3619658 .
- ^ a b Borndörfer, Ральф; Грёчель, Мартин ; Лёбель, Андреас (1995), Проблемы транспортировки и целочисленное программирование Алкуина , Препринт SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, архивировано из оригинала 19.07.2011. CS1 maint: обескураженный параметр ( ссылка ).
- ^ Schwartz, Benjamin L. (1961), "Аналитический метод "трудное пересечение" головоломки", Математика Magazine , 34 (4): 187-193, DOI : 10,2307 / 2687980 , JSTOR 2687980 .
- ^ Чорба, Петер; Hurkens, Cor AJ; Woeginger, Gerhard J. (2008), «Число Алкуина графа», Алгоритмы: ESA 2008 , Lecture Notes in Computer Science, 5193 , Springer-Verlag, pp. 320–331, doi : 10.1007 / 978-3-540 -87744-8_27.
- ^ Беллман, Ричард (1962), "Динамическое программирование и "трудный переход" головоломка", Математика Журнал , Математическая ассоциация Америки, 35 (1): 27-29, DOI : 10,2307 / 2689096 , JSTOR 2689096 CS1 maint: обескураженный параметр ( ссылка ).
Внешние ссылки [ править ]
- YouTube видео