Проблема миссионеров и каннибалов , а также тесно связанная с ней проблема ревнивых мужей - классические логические головоломки, связанные с переходом через реку . [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.
Номер поездки | Стартовый банк | Путешествовать | Конечный банк |
---|---|---|---|
(Начало) | αa βb γc | ||
1 | βb γc | αa → | |
2 | βb γc | ← α | а |
3 | α β γ | до н.э. → | а |
4 | α β γ | ← а | до н.э |
5 | αa | βγ → | до н.э |
6 | αa | ← βb | γc |
7 | ab | αβ → | γc |
8 | ab | ← c | α β γ |
9 | б | ac → | α β γ |
10 | б | ← β | αa γc |
11 | βb → | αa γc | |
(финиш) | αa βb γc |
Это кратчайшее решение проблемы, но не единственное кратчайшее. [4] , с. 291.
Если, однако, только один мужчина может выйти из лодки за раз и мужья должны находиться на берегу, чтобы считаться с его женой, а не просто находиться в лодке на берегу: перемещение с 5 на 6 невозможно, так как как только поскольку γ вышла на берег , b на берегу не будет с мужем, несмотря на то, что он только что был в лодке.
Как упоминалось ранее, это решение проблемы ревнивых мужей станет решением проблемы миссионеров и каннибалов после замены мужчин миссионерами и женщин каннибалами. В этом случае мы можем пренебречь личностями миссионеров и каннибалов. Приведенное решение все еще является кратчайшим и является одним из четырех кратчайших. [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 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]
Смотрите также
Рекомендации
- ^ Б с д е е г ч я Прессман, Ian; Певец, Дэвид (июнь 1989 г.). « „ Ревнивая Мужья“и„Миссионеры и каннибалы “ ». Математический вестник . 73 (464): 73–81. DOI : 10.2307 / 3619658 . JSTOR 3619658 .
- ^ Амарель, Саул (1968). Мичи, Дональд (ред.). «О представлениях задач рассуждения о действиях» . Машинный интеллект . Амстердам, Лондон, Нью-Йорк: Эльзевир / Северная Голландия. 3 : 131–171. Архивировано из оригинала 8 марта 2008 года.
- ^ Кордески, Роберто (2006). «Поиск в лабиринте, в поисках знаний: проблемы раннего искусственного интеллекта». В наличии, Оливьеро; Шаерф, Марко (ред.). Рассуждение, действие и взаимодействие в теориях и системах искусственного интеллекта: очерки, посвященные Луиджи Карлуччи Айелло . Конспект лекций по информатике. 4155 . Берлин / Гейдельберг: Springer. С. 1–23. DOI : 10.1007 / 11829263_1 . ISBN 978-3-540-37901-0.
- ^ а б в г д Фрэнси, Рафаэлла (2002). «Ревнивые мужья переходят реку: проблема от Алкуина до Тартальи». В Долд-Самплониусе, Ивонне; Dauben, Joseph W .; Фолкертс, Менсо; ван Дален, Бенно (ред.). От Китая до Парижа: 2000 лет передачи математических идей . Штутгарт: Франц Штайнер Верла. С. 289–306. ISBN 3-515-08223-9.
- ^ Лим, Руби (1992). Shaw, Lynne C .; и другие. (ред.). Каннибалы и миссионеры . APL '92, Международная конференция по APL (Санкт-Петербург, 6–10 июля 1992 г.). Нью-Йорк: Ассоциация вычислительной техники. С. 135–142. DOI : 10.1145 / 144045.144106 . ISBN 0-89791-477-5.
- ^ Петерсон, Иварс (13 декабря 2003 г.). «Коварные переходы» . Новости науки . 164 (24) . Проверено 12 марта 2011 года .
- ^ Фрейли, Роберт; Кук, Кеннет Л .; Детрик, Питер (май 1966 г.). «Графическое решение сложных головоломок». Математический журнал . 39 (3): 151–157. DOI : 10.1080 / 0025570X.1966.11975705 . JSTOR 2689307 .
- ^ Корреспондент, Никола Вулкок, образование. «Экзаменационная комиссия AQA одобрила книгу GCSE с изображением каннибалов, готовящих белых миссионеров» . ISSN 0140-0460 . Проверено 19 июля 2020 г. - через www.thetimes.co.uk.