Проблема миссионеров и каннибалов
Проблема миссионеров и каннибалов и тесно связанная с ней проблема ревнивых мужей — это классические о переправе через реку логические головоломки . [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 поездок в один конец заключается в следующем. Супружеские пары представлены как α (мужчина) и a (женщина), β и b , а также γ и c . [4] , с. 291.
Сплошная красная линия дополнительно обозначает каннибала, неспособного грести.
На рисунке справа, если жена или каннибал, остающиеся на лодке, считаются одинокими (обведены), возможно более короткое решение.
| Номер поездки | Стартовый банк | Путешествовать | Конечный банк |
|---|---|---|---|
| (начинать) | аа бб cc | ||
| 1 | бб с | αа → | |
| 2 | бб с | ←α | а |
| 3 | а б в | до нашей эры → | а |
| 4 | а б в | ← а | до нашей эры |
| 5 | αа | выход → | до нашей эры |
| 6 | αа | ← βб | γc |
| 7 | аб | аб → | γc |
| 8 | аб | ← с | а б в |
| 9 | б | переменный ток → | а б в |
| 10 | б | ← б | αa γc |
| 11 | βб → | αa γc | |
| (заканчивать) | аа бб cc |
Это кратчайшее решение проблемы, но не единственное кратчайшее решение. [4] , с. 291.
Однако если одновременно из лодки может выйти только один мужчина, а мужья должны находиться на берегу, чтобы считаться со своей женой, а не просто находиться в лодке на берегу: ход с 5 по 6 невозможен, поскольку как только как γ вышла на берег, ее не будет с мужем, несмотря на то, что он только что был в лодке.
Как упоминалось ранее, это решение проблемы ревнивых мужей станет решением проблемы миссионеров и каннибалов при замене мужчин миссионерами, а женщин каннибалами. В этом случае мы можем пренебречь индивидуальными личностями миссионеров и каннибалов. Только что данное решение по-прежнему является самым коротким и входит в число четырех кратчайших решений. [5]
Если женщина в лодке у берега (но не на берегу) считается одна (т.е. в отсутствие мужчин на берегу), то эту головоломку можно решить за 9 поездок в один конец:
| Номер поездки | Стартовый банк | Путешествовать | Конечный банк |
|---|---|---|---|
| (начинать) | аа бб cc | ||
| 1 | бб с | αа → | |
| 2 | бб с | ← а | а |
| 3 | б в | аб → | а |
| 4 | б в | ← б | αа |
| 5 | γc | βб → | αа |
| 6 | γc | ← б | аа б |
| 7 | с | до нашей эры → | аа б |
| 8 | с | ← с | αа βb |
| 9 | γc → | αа βb | |
| (заканчивать) | аа бб cc |
Вариации
[ редактировать ]Очевидным обобщением является изменение количества ревнивых пар (или миссионеров и каннибалов), вместимости лодки или того и другого. Если в лодке 2 человека, то 2 парам потребуется 5 поездок; при наличии 4 и более пар задача не имеет решения. [6] Если в лодке могут разместиться 3 человека, то переправиться смогут до 5 пар; если лодка вмещает 4 человека, переправиться может любое количество пар. [4] , с. 300. Простой подход теории графов к анализу и решению этих обобщений был предложен Фрейли, Куком и Детриком в 1966 году. [7]
Если посередине реки добавить остров, то любое количество пар сможет переправиться на двухместной лодке. Если переправы с берега на берег запрещены, то 8 n −6 рейсов в одну сторону; потребуется для переправы n пар через реку [1] , с. 76 если они разрешены, то 4 n требуется +1 поездок, если n превышает 4, хотя минимальное решение требует только 16 поездок, если n равно 4. [1] , с. 79. Если ревнивые пары заменить миссионерами и каннибалами, то количество необходимых поездок не изменится, если переправы с берега на берег не разрешены; однако если это так, количество поездок уменьшается до 4 n −1, если предположить, что n равно не менее 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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д и ж г час я Прессман, Ян; Сингмастер, Дэвид (июнь 1989 г.). « Ревнивые мужья» и «Миссионеры и каннибалы» . Математический вестник . 73 (464): 73–81. дои : 10.2307/3619658 . JSTOR 3619658 .
- ^ Амарель, Саул (1968). Мичи, Дональд (ред.). «О представлениях проблем рассуждений о действиях» . Машинный интеллект . 3 . Амстердам, Лондон, Нью-Йорк: Эльзевир/Северная Голландия: 131–171. Архивировано из оригинала 8 марта 2008 года.
- ^ Кордески, Роберто (2006). «Поиск в лабиринте, в поисках знаний: проблемы раннего искусственного интеллекта». В наличии, Оливьеро; Шерф, Марко (ред.). Рассуждение, действие и взаимодействие в теориях и системах искусственного интеллекта: эссе, посвященные Луиджи Карлуччи Айелло . Конспекты лекций по информатике. Том. 4155. Берлин/Гейдельберг: Шпрингер. стр. 1–23. дои : 10.1007/11829263_1 . ISBN 978-3-540-37901-0 .
- ^ Перейти обратно: а б с д и Франси, Рафаэлла (2002). «Ревнивые мужья переходят реку: проблема от Алкуина до Тартальи». В Дольд-Самплониусе, Ивонн; Добен, Джозеф В.; Фолкертс, Менсо; Ван Вэлли, Бенно (ред.). От Китая до Парижа: 2000 лет передачи математических идей . Штутгарт: Франц Штайнер Верла. стр. 100-1 289–306. ISBN 3-515-08223-9 .
- ^ Лим, Руби (1992). Шоу, Линн С.; и др. (ред.). Каннибалы и миссионеры . 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 .
- ^ Вулкок, Никола (18 июля 2020 г.). «Экзаменационная комиссия AQA одобрила книгу выпускных экзаменов с изображением каннибалов, готовящих белого миссионера» . Таймс . ISSN 0140-0460 . Проверено 19 июля 2020 г.