Читать «Искусственный разум» онлайн - страница 41

Оценим работу, которую предстоит проделать монахам до рокового мига. Наименьшее число перекладываний составит здесь 18 446 744 073 703 551 615. Если монахи станут переносить по одному кольцу в секунду и будут работать день и ночь, они окончат свой труд приблизительно через 585 биллионов лет.

Значит, пугаться скорой гибели мира нет причин. Зато есть причины поражаться огромности дерева, выросшего на почве несложной головоломки. Зато становится понятным, почему людям трудно справиться с этой забавой, когда число колец восемь или, того хуже, 12. Слишком много вариантов - и не попробуешь их все, и не запомнишь, какие пробовал.

Грузинский кибернетик В. Чавчанидзе назвал возникающую ситуацию "кошмаром перебора". Склонный к ярким и парадоксальным высказываниям, ученый заявил, что "кошмаром перебора" мир мстит за его непонимание. Чтобы решить задачу, нужно избежать полного перебора ветвей дерева возможностей и придумать что-нибудь более остроумное. Если бы снять сразу всю стопку колец и плавно перенести ее с ближнего стержня на дальний, то цель была бы достигнута одним махом...

Хорошая идея, жаль, правила игры не позволяют.

Ладно, не получается решить задачу сразу, будем делать это по частям. Станем собирать нашу пирамиду из колец на дальнем стержне колечко за колечком. Значит, первым там должно оказаться самое большое кольцо.

Но оно задавлено, находится под гнетом других колец. Освободить его от гнета - вот первоочередная цель. Затем не составит труда перебросить его с ближнего на дальний стержень. А потом как-нибудь пристроим к большому кольцу другие кольца.

Итак, наша задача разделяется на три подзадачи, как симфония делится на три части. Мы и назовем свои подзадачи музыкально: АНДАНТЕ, СКЕРЦО и ФИНАЛ.

АНДАНТЕ. Цель: освободить большое кольцо. Для этого надо предварительно освободить среднее. И - как удачно! - здесь опять работает наша идея: сослать угнетателей среднего кольца на запасной, в данном случае дальний стержень.

А чтобы изгнать эту пару колец, нужно сначала очистить малое кольцо, отправив маленькое колечко на запасной, теперь средний, стержень.

А маленькое колечко?.. Оно готово к ссылке. А средний стержень?.. Он свободен. Значит, ссылка маленького колечка осуществима сразу. Значит, можно сделать и все остальное!

Мы решили задачу АНДАНТЕ. Задача СКЕРЦО, как и положено, решается мгновенно: переносим большое кольцо с ближнего стержня на дальний; основание пирамиды заложено.

Теперь задача ФИНАЛ. Легко можно убедиться, что она поддается той же уловке - ссылке угнетателей на запасной стержень.

Выходит, дело сделано, мы знаем, как построить "Халойскую башню" с четырьмя кольцами, хотя и не занимались утомительным перебором возможностей. Мы не обследовали дерево возможностей; мы предпочли вырастить иное дерево - дерево целей. Корень дерева - общая цель головоломки - перенести все кольца. От этого корня ответвляются три ствола, три частные цели - наши АНДАНТЕ, СКЕРЦО и ФИНАЛ.