Из Википедии, бесплатной энциклопедии
  (Перенаправлено из загадки о переходе через реку )
Перейти к навигации Перейти к поиску
Собака, овца и капуста

Головоломка переправа представляет собой тип головоломки , в которой объект должен нести элементы из одной реки в другую, как правило , в наименьшее количество поездок. Сложность головоломки может возникнуть из-за ограничений на то, какие или сколько предметов можно транспортировать одновременно, или какие или сколько предметов можно безопасно оставить вместе. [1] Настройку можно изменить косметически, например, заменив реку мостом. [1] Самые ранние известные проблемы с переходом через реки встречаются в рукописи Propositiones ad Acuendos Juvenes (английский язык: проблемы для заострения молодых ), традиционно написанной Алкуином.. Самые ранние копии этой рукописи датируются IX веком; он содержит три проблемы перехода через реку, включая загадку лисы, гуся и мешка с фасолью и проблему ревнивых мужей . [2]

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

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

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

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

Ссылки [ править ]

  1. ^ a b Петерсон, Иварс (2003), "Tricky crossings" , Science News , 164 (24) , получено 07 февраля 2008 г. CS1 maint: обескураженный параметр ( ссылка ).
  2. ^ стр. 74, Прессман, Ян; Singmaster, Дэвид (1989), " " Ревнивая Мужья "и "Миссионеры и каннибалы " ", Математическая газета Математическая ассоциация, 73 (464): 73-81, DOI : 10,2307 / 3619658 , JSTOR 3619658 .
  3. ^ a b Borndörfer, Ральф; Грёчель, Мартин ; Лёбель, Андреас (1995), Проблемы транспортировки и целочисленное программирование Алкуина , Препринт SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, архивировано из оригинала 19.07.2011. CS1 maint: обескураженный параметр ( ссылка ).
  4. ^ Schwartz, Benjamin L. (1961), "Аналитический метод "трудное пересечение" головоломки", Математика Magazine , 34 (4): 187-193, DOI : 10,2307 / 2687980 , JSTOR 2687980 .
  5. ^ Чорба, Петер; 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.
  6. ^ Беллман, Ричард (1962), "Динамическое программирование и "трудный переход" головоломка", Математика Журнал , Математическая ассоциация Америки, 35 (1): 27-29, DOI : 10,2307 / 2689096 , JSTOR 2689096  CS1 maint: обескураженный параметр ( ссылка ).

Внешние ссылки [ править ]

  • YouTube видео