Проблема миссионеров и каннибалов - Missionaries and cannibals problem
В проблема миссионеров и каннибалов, и тесно связанные проблема ревнивого мужа, классические переправа через реку логические головоломки.[1] Проблема миссионеров и каннибалов - хорошо известная проблема. проблема с игрушкой в искусственный интеллект, где он использовался Саул Амарель как пример представления проблемы.[2][3]
Проблема
В задаче о миссионерах и каннибалах три миссионера и три каннибала должны пересечь реку, используя лодку, которая может перевозить не более двух человек, с ограничением, что для обоих берегов, если на берегу присутствуют миссионеры, их не может превзойти численность каннибалы (если бы они были, каннибалы съели бы миссионеров). Лодка не может самостоятельно пересечь реку без людей на борту. А в некоторых вариантах у одного из каннибалов только одна рука и он не может грести.[1]
В проблеме ревнивых мужей миссионеры и каннибалы становятся тремя супружескими парами с ограничением, что ни одна женщина не может находиться в присутствии другого мужчины, если ее муж также не присутствует. При таком ограничении на берегу не могут находиться и женщины, и мужчины, при этом женщин больше, чем мужчин, поскольку в противном случае эти женщины остались бы без своих мужей. Следовательно, после превращения мужчин в миссионеров и женщин в каннибалов любое решение проблемы ревнивых мужей также станет решением проблемы миссионеров и каннибалов.[1]
Решение
Система для решения проблемы миссионеров и каннибалов, в которой текущее состояние представлено простым вектором ⟨m, c, b⟩. Элементы вектора представляют количество миссионеров, каннибалов и то, находится ли лодка не той стороной, соответственно. Поскольку лодка и все миссионеры и каннибалы стартуют не с той стороны, вектор инициализируется как ⟨3,3,1⟩. Действия представлены с использованием вычитания / сложения векторов для управления вектором состояния. Например, если одинокий каннибал пересек реку, вектор ⟨0,1,1⟩ будет вычтен из состояния, чтобы получить ⟨3,2,0⟩. Состояние могло бы отразить, что три миссионера и два людоеда все еще не на той стороне, и что лодка сейчас находится на противоположном берегу. Для полного решения проблемы формируется простое дерево с исходным состоянием в качестве корня. Тогда пять возможных действий (⟨1,0,1⟩, ⟨2,0,1⟩, ⟨0,1,1⟩, ⟨0,2,1⟩ и ⟨1,1,1⟩) таковы. вычтенный из начального состояния, в результате чего образуются дочерние узлы корня. Любой узел, у которого на любом берегу больше каннибалов, чем миссионеров, находится в недопустимом состоянии и поэтому исключается из дальнейшего рассмотрения. Допустимые сгенерированные дочерние узлы будут ⟨3,2,0⟩, ⟨3,1,0⟩ и ⟨2,2,0⟩. Для каждого из этих оставшихся узлов дочерние узлы генерируются добавление каждый из возможных векторов действия. Алгоритм продолжает чередование вычитания и сложения для каждого уровня дерева до тех пор, пока не будет сгенерирован узел с вектором ⟨0,0,0⟩ в качестве значения. Это состояние цели, и путь от корня дерева к этому узлу представляет собой последовательность действий, которая решает проблему.
Решение
Самое раннее известное решение проблемы ревнивых мужей с использованием 11 поездок в один конец заключается в следующем. Семейные пары представлены как α (мужчина) и а (женский), β и б, и γ и c.[4], п. 291.
| Номер поездки | Стартовый банк | Путешествовать | Конечный банк |
|---|---|---|---|
| (Начните) | αa βb γc | ||
| 1 | βb γc | αa → | |
| 2 | βb γc | ← α | а |
| 3 | α β γ | до н.э. → | а |
| 4 | α β γ | ← а | до н.э |
| 5 | αa | βγ → | до н.э |
| 6 | αa | ← βb | γc |
| 7 | а б | αβ → | γc |
| 8 | а б | ← c | α β γ |
| 9 | б | а в → | α β γ |
| 10 | б | ← β | αa γc |
| 11 | βb → | αa γc | |
| (Конец) | αa βb γc |
Это кратчайшее решение проблемы, но не единственное кратчайшее.[4], п. 291.
Если, однако, только один мужчина может выйти из лодки за раз, и мужья должны находиться на берегу, чтобы считаться с его женой, а не просто находиться в лодке на берегу: переход с 5 на 6 невозможен, поскольку как только в качестве γ вышел б на берегу не будет с мужем, несмотря на то, что он просто в лодке.
Как упоминалось ранее, это решение проблемы ревнивых мужей станет решением проблемы миссионеров и каннибалов после замены мужчин миссионерами и женщин каннибалами. В этом случае мы можем пренебречь индивидуальными идентичностями миссионеров и каннибалов. Приведенное решение все еще является кратчайшим и является одним из четырех кратчайших.[5]
Если женщина в лодке у берега (но не на берег) считается находящейся в одиночестве (то есть без людей на берегу), то эту загадку можно решить за 9 поездок в один конец:
| Номер поездки | Стартовый банк | Путешествовать | Конечный банк |
|---|---|---|---|
| (Начните) | αa βb γc | ||
| 1 | βb γc | αa → | |
| 2 | βb γc | ← а | α |
| 3 | β γc | ab → | α |
| 4 | β γc | ← б | αa |
| 5 | γc | βb → | αa |
| 6 | γc | ← б | αa β |
| 7 | γ | до н.э. → | αa β |
| 8 | γ | ← c | αa βb |
| 9 | γc → | αa βb | |
| (Конец) | αa βb γc |
Вариации
Очевидное обобщение - варьировать количество ревнивых пар (или миссионеров и каннибалов), вместимость лодки или и то, и другое. Если на лодке 2 человека, то на 2 пары потребуется 5 поездок; с 4 и более парами проблема не имеет решения.[6] Если на лодке могут разместиться 3 человека, то могут переправиться до 5 пар; если лодка вмещает 4 человека, пересечь может любое количество пар.[4], п. 300. Простой подход теории графов к анализу и решению этих обобщений был предложен Фрейли, Куком и Детриком в 1966 году.[7]
Если посреди реки добавлен остров, то любое количество пар может пересечь его на двухместной лодке. Если переходы из банка в банк не допускаются, то 8п−6 рейсов в одну сторону требуется для переправы п пары через реку;[1], п. 76 если разрешено, то 4п+1 поездки необходимы, если п превышает 4, хотя минимальное решение требует всего 16 поездок, если п равно 4.[1], п. 79. Если ревнивые пары заменены миссионерами и каннибалами, количество требуемых поездок не изменится, если переходы от берега к берегу запрещены; если они есть, то количество поездок уменьшается до 4п−1, полагая п не меньше 3.[1], п. 81.
История
Первое известное проявление проблемы ревнивых мужей встречается в средневековом тексте. Propositiones ad Acuendos Juvenes, обычно приписывается Алкуин (умер 804 г.). В формулировке Алкуина пары - это братья и сестры, но ограничение остается тем же: ни одна женщина не может находиться в компании другого мужчины, если не присутствует ее брат.[1], п. 74. С 13 по 15 века проблема стала известна по всей Северной Европе, и теперь пары стали мужьями и женами.[4]С. 291–293. Позже проблема была поставлена в форме мастеров и камердинеров; Формулировка с миссионерами и каннибалами появилась только в конце XIX века.[1], п. 81 год Вариант количества пар и размера лодки рассматривался в начале 16 века.[4], п. 296. Кадет де Фонтене задумал разместить остров посреди реки в 1879 году; этот вариант задачи с двухместной лодкой был полностью решен Яном Прессманом и Дэвид Сингмастер в 1989 г.[1]
В 2020 году полемика по поводу расистских тем в мультфильме о проблеме привела к AQA экзаменационная комиссия изымает учебник, содержащий задачу.[8]
Смотрите также
Рекомендации
- ^ а б c d е ж грамм час я Прессман, Ян; Singmaster, Дэвид (июнь 1989). "'Ревнивые мужья и миссионеры и каннибалы'". Математический вестник. 73 (464): 73–81. Дои:10.2307/3619658. JSTOR 3619658.
- ^ Амарель, Саул (1968). Мичи, Дональд (ред.). «О представлениях проблем рассуждений о действиях». Машинный интеллект. Амстердам, Лондон, Нью-Йорк: Эльзевир / Северная Голландия. 3: 131–171. Архивировано из оригинал 8 марта 2008 г.
- ^ Кордески, Роберто (2006). «Поиски в лабиринте в поисках знаний: проблемы раннего искусственного интеллекта». В наличии, Оливьеро; Шаерф, Марко (ред.). Рассуждение, действие и взаимодействие в теориях и системах искусственного интеллекта: эссе, посвященные Луиджи Карлуччи Айелло. Конспект лекций по информатике. 4155. Берлин / Гейдельберг: Springer. С. 1–23. Дои:10.1007/11829263_1. ISBN 978-3-540-37901-0.
- ^ а б c d е Франси, Рафаэлла (2002). «Ревнивые мужья переходят реку: проблема от Алкуина до Тартальи». У Дольд-Самплониуса, Ивонна; Dauben, Joseph W .; Фолкертс, Менсо; ван Дален, Бенно (ред.). Из Китая в Париж: 2000 лет передачи математических идей. Штутгарт: Франц Штайнер Верла. С. 289–306. ISBN 3-515-08223-9.
- ^ Лим, Руби (1992). Shaw, Lynne C .; и другие. (ред.). Каннибалы и миссионеры. APL '92, Международная конференция по APL (Санкт-Петербург, 6–10 июля 1992 г.). Нью-Йорк: Ассоциация вычислительной техники. С. 135–142. Дои:10.1145/144045.144106. ISBN 0-89791-477-5.
- ^ Петерсон, Иварс (13 декабря 2003 г.). «Коварные переходы». Новости науки. 164 (24). Получено 12 марта, 2011.
- ^ Фрейли, Роберт; Кук, Кеннет Л .; Детрик, Питер (май 1966 г.). «Графическое решение сложных головоломок». Математический журнал. 39 (3): 151–157. Дои:10.1080 / 0025570X.1966.11975705. JSTOR 2689307.
- ^ Корреспондент, Никола Вулкок, образование. «Экзаменационная комиссия AQA одобрила книгу GCSE с изображением каннибалов, готовящих белых миссионеров». ISSN 0140-0460. Получено 2020-07-19 - через www.thetimes.co.uk.