Мартин Гарднер - Математические головоломки и развлечения
Поэтому можно с уверенностью сказать, что где-то по дороге вы дойдете до цели. Лабиринт в Хэмптон-Корте многосвязный, но две его замкнутые петли не окружают цели. Поэтому, войдя в него и держась за стенку, вы сможете добраться до цели и выбраться наружу, ни разу не побывав при этом в какой-то из двух петель.
Существует ли способ (или, говоря языком математики, алгоритм), позволяющий находить верный путь в любых лабиринтах, в том числе и в многосвязных с замкнутыми петлями вокруг цели?
Оказывается, существует. Лучше всего такой алгоритм сформулировал Э. Люка[46] (правда, честь изобретения алгоритма он приписывает М. Тремо). Суть алгоритма заключается в следующем.
Пробираясь по лабиринту, отметим свой путь, проводя линию по стенке, например справа. Дойдя до разветвления, мы можем выбрать любой из путей. Если, идя по новому пути, мы вернемся к перекрестку, на котором уже побывали, или попадем в тупик, то следует повернуться и идти в обратном направлении по тому же пути, по которому мы только что пришли. Если, идя по старому пути (то есть по пути, помеченному линией слева), мы вернемся к перекрестку, где мы уже были раньше, то, пройдя его, следует выбрать новый путь (если таковой имеется). В противном случае выберем старый путь. Никогда не следует идти по пути, уже пройденному дважды (с отметками по обеим сторонам).
На рис. 137 справа показан многосвязный лабиринт, в котором центр окружен двумя замкнутыми петлями. Воспользовавшись алгоритмом Тремо и отмечая пройденный путь красным карандашом, читатель обнаружит, что ему действительно удастся побывать в центре и вернуться ко входу после того, как он дважды (по одному разу туда и обратно) побывает во всех закоулках лабиринта. Еще лучше, если, дойдя до цели, вы не будете отмечать карандашом свой дальнейший путь: следуя только по тем дорожкам, которые отмечены одной линией, вы автоматически проложите наиболее короткий путь от входа в лабиринт до цели.
Для читателей, которые захотят испробовать предлагаемый метод на более сложном лабиринте, на рис. 138 показан план многосвязного лабиринта, который построил в своем саду английский математик У. У. Роуз Болл. Цель указана точкой внутри лабиринта.
Рис. 138 Лабиринт в саду У. У. Роуза Болла.
В наше время взрослые люди уже не занимаются такими головоломками, однако существуют две области науки, в которых интерес к лабиринтам остается неизменно высоким: это психология и конструирование компьютеров. В самом деле, психологи уже в течение нескольких десятилетий используют лабиринты при изучении обученного поведения людей и животных. Даже простейшего дождевого червя можно научить пробираться по лабиринту, в котором дорожка в одном месте раздваивается. Муравьи способны после обучения преодолеть лабиринт с 10-ю разветвлениями. Конструкторы вычислительных машин рассматривают роботов, умеющих находить дорогу в лабиринтах, как составную часть многообещающей программы создания самообучающихся машин, то есть машин, способных, подобно животным, извлекать ценные для себя сведения из опыта.
Одним из первых устройств столь необычного типа был «Тезей» — мышь-робот, изобретенная Клодом Э. Шенноном, сотрудником Массачусетского технологического института, которая умела «самостоятельно» находить дорогу в лабиринте. Используя один из вариантов алгоритма Тремо, «мышь» сначала систематически обследует незнакомый лабиринт. Дойдя до разветвления и встав перед необходимостью выбора дальнейшего пути, мышь не действует наугад, как поступил бы человек, а, двигаясь в одну определенную сторону, всегда избирает ближайший коридор. «Нарушить работу машины, содержащей случайный элемент, весьма трудно, — объяснял Шеннон. — Ведь если вы не можете предсказать заранее, что она вообще должна делать, то вам трудно определить, делает ли она что-то не так».
После того как мышь нашла дорогу к цели, запоминающие устройства позволяют ей второй раз пройти через лабиринт уже без ошибок. На языке алгоритма Тремо это означает, что мышь будет избегать всех участков пути, пройденных дважды, и будет следовать лишь по тому маршруту, который был пройден ею только один раз. Мы не можем гарантировать, что мышь изберет кратчайший путь к цели. Можно лишь утверждать, что, идя к цели, мышь нигде не будет заходить в тупики. Живая («настоящая») мышь обучается отыскивать дорогу в лабиринте гораздо медленнее, поскольку, обследуя незнакомый лабиринт, она в основном использует метод проб и ошибок (хотя в ее поведении имеются и другие элементы).
Требуется многократный успех, чтобы правильный путь закрепился в ее памяти.
Позднее научились строить и других роботов, умеющих находить дорогу в лабиринте. Одного из самых «хитроумных» из них сконструировал Ярослав А. Дейч из Оксфордского университета.
Если этот робот обучать на одном лабиринте, то он сможет нести свой опыт на любой другой лабиринт, топологически эквивалентный первому, как бы мы ни изменяли длину и форму стенок.
Робот Дейча умеет также находить кратчайшие пути в лабиринте и проделывать другие удивительные вещи.
Все эти устройства, безусловно, лишь первые шаги новой отрасли техники. Весьма вероятно, что будущие обучающиеся машины, обретя огромную мощь, станут выполнять самые неожиданные функции среди автоматов космического века. Лабиринты и космический век — эта комбинация снова возвращает нас к греческому мифу, уже упоминавшемуся в начале этой главы. Лабиринт Минотавра был построен для царя Миноса никем иным, как Дедалом, тем самым Дедалом, который изобрел крылья и чей сын Икар погиб, поднявшись слишком высоко в небо. «Столь хитро придуманного лабиринта еще не видели на свете ни до, ни после, — пишет Н. Хоуторн, пересказывая миф о Дедале. — Ничто не может сравниться с ним по сложности, разве что мозг такого человека, как Дедал, чей разум создал его, или сердце обыкновеннейшего из людей…»
Глава 26. ЗАНИМАТЕЛЬНАЯ ЛОГИКА
Слова Шерлока Холмса: «Сколько раз я говорил вам, отбросьте все невозможное, тогда то, что останется, и будет ответом, каким бы невероятным он ни казался», — могли бы послужить эпиграфом к этой главе.
Если для решения головоломки требуется лишь умение логически мыслить и совсем не нужно производить арифметические выкладки, то такую головоломку обычно называют логической задачей. Логические задачи, разумеется, относятся к числу математических, поскольку логику можно рассматривать как очень общую, фундаментальную математику. Все же логические головоломки удобно выделить и изучать отдельно от их более многочисленных арифметических сестер. В этой главе мы рассмотрим в общих чертах три широко распространенных типа логических задач и постараемся выяснить, как следует подходить к их решению.
Чаще всего встречается тип задачи, который любители головоломок иногда называют «задачей о Смите — Джонсе — Робинсоне» (по аналогии со старой головоломкой, придуманной Г. Дьюдени).
Она состоит из серии посылок, обычно сообщающих те или иные сведения о действующих лицах; на основании этих посылок требуется сделать определенные выводы. Вот, например, как выглядит последняя американская версия задачи Дьюдени:
1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями.
В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р).
2. М-р Робинсон живет в Лос-Анджелесе.
3. Кондуктор живет в Омахе.
4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.
5. Пассажир — однофамилец кондуктора живет в Чикаго.
6. Кондуктор и один из пассажиров, известный специалист по математической физике, ходят в одну церковь.
7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.
Как фамилия машиниста?
Данные задачи можно было бы перевести на язык математической логики, воспользовавшись ее стандартными обозначениями, и искать решение с помощью соответствующих методов, однако такой подход был бы слишком громоздким. С другой стороны, без сокращенных обозначений того или иного рода трудно понять логическую структуру задачи. Удобнее всего воспользоваться таблицей, в пустые клетки которой мы будем вписывать всевозможные комбинации элементов рассматриваемых множеств. В нашем случае таких множеств два, поэтому нам понадобятся две таблицы (рис. 139).
Рис. 139 Две таблицы к задаче о Смите, Джонсе и Робинсоне.
В каждую клетку впишем 1, если соответствующая комбинация допустима, или 0, если комбинация противоречит условиям задачи. Посмотрим, как это делается. Условие 7, очевидно, исключает возможность того, что Смит кочегар, поэтому в клетку, стоящую в правом верхнем углу левой таблицы, мы вписываем 0. Условие 2 сообщает нам, что Робинсон живет в Лос-Анджелесе, поэтому в левый нижний угол таблицы мы вписываем 1, а во все остальные клетки нижней строки и левого столбца — 0, чтобы показать, что м-р Робинсон не живет в Омахе или в Чикаго, а м-р Смит и м-р Джонс не живут в Лос-Анджелесе.
