Головоломка о переправе через реку

Класс логических головоломок

Собака, овца и капуста

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

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

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

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

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

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

Пусть будет неориентированным графом, множество вершин которого представляет предметы, которые должен нести фермер, а множество ребер состоит из пар предметов, которые конфликтуют. Например, если вершина представляет гуся и мешок с фасолью, то две вершины будут связаны, поскольку гуся нельзя оставить на одной стороне реки с мешком с фасолью. Обратите внимание, что ребра неориентированы, поскольку характер конфликта между двумя предметами не влияет на тот факт, что их нельзя оставить на одной стороне реки. Цель задачи — определить минимальный размер лодки, такой, чтобы поездка была осуществимой; это известно как число Алкуина . ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle G}$

Рассмотрим успешную переправу через реку, в которой фермер сначала переносит подмножество предметов через реку, оставляя оставшиеся предметы на берегу. Поскольку поездка успешна, не должно быть конфликтов в предметах, оставленных на берегу; т. е. в , нет ребер между любыми двумя элементами . Это подразумевает, что все ребра имеют одну или обе вершины в , т. е. что является вершинным покрытием . Следовательно, размер лодки должен быть по крайней мере таким же большим, как размер минимального вершинного покрытия ; это формирует нижнюю границу числа Алкуина : . ${\displaystyle V'}$ ${\displaystyle V\setminus V'}$ ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle V\setminus V'}$ ${\displaystyle E}$ ${\displaystyle V'}$ ${\displaystyle V'}$ ${\displaystyle G}$ ${\displaystyle \tau (G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle Alcuin(G)\geq \tau (G)}$

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

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

Смотрите также

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

Ссылки

1. Peterson, Ivars (2003), "Tricky crossings", Science News , 164 (24) , получено 2008-02-07.
2. стр. 74, Прессман, Ян; Сингмастер, Дэвид (1989), "«Ревнивые мужья» и «Миссионеры и каннибалы»", The Mathematical Gazette , 73 (464), Математическая ассоциация: 73–81, doi : 10.2307/3619658, JSTOR  3619658.
3. Борндорфер, Ральф; Гретшель, Мартин ; Лебель, Андреас (1995), Транспортные проблемы Алкуина и целочисленное программирование , Препринт SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, заархивировано из оригинала 19 июля 2011 г..
4. Шварц, Бенджамин Л. (1961), «Аналитический метод для головоломок «трудного пересечения»», Mathematics Magazine , 34 (4): 187–193, doi :10.2307/2687980, JSTOR  2687980.
5. Csorba, Питер; Хуркенс, Кор А.Дж.; Воегингер, Герхард Дж. (2008), «Число Алкуина графа», Алгоритмы: ESA 2008 , Конспекты лекций по информатике, том. 5193, Springer-Verlag, стр. 320–331, номер документа : 10.1007/978-3-540-87744-8_27..
6. Беллман, Ричард (1962), «Динамическое программирование и головоломки «сложного пересечения»», Mathematics Magazine , 35 (1), Математическая ассоциация Америки: 27–29, doi : 10.2307/2689096, JSTOR  2689096.
7. Numberphile (2018-01-05). Переправы через реку (и числа Алкуина) - Numberphile . Получено 2024-05-17 – через YouTube.

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

• Видео на YouTube