Алексей Чачко - Искусственный разум Страница 15

Большую роль в популярности головоломки "Ханойская башня" сыграла ее связь со старинной индийской легендой о храме города Бенареса. Башня этого храма, гласила легенда, особая. Она сложена из 64 золотых колец, надетых на общий стержень. Рядом вкопаны еще два стержня, и монахи неустанно перекладывают кольца со стержня на стержень, соблюдая особый ритуал. Когда все кольца окажутся на дальнем стержне, грянет гром, храм обратится в пыль, а мир исчезнет.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На наших глазах из одной головоломки выросло сразу два дерева: дерево возможностей и дерево целей. Дерево целей кажется более стройным, менее ветвистым, подобным корабельной сосне. Мы и растили его, как корабельную сосну, не давая чересчур ветвиться, обозначая на нем лишь разумные, а не все возможные цели.

Дерево целей - надежная опора и в более сложных случаях, когда башня состоит из восьми или 12 колец. Наши приемы - разделение задачи на подзадачи, освобождение и ссылка колец - не подводят и здесь. Мы не убоимся и главной "Ханойской башни", той, что собрана из 64 золотых колец. Ибо наше оружие - эвристики - не тупится о золото.

Они с самого начала имели дело с золотом. Помните, как Гиерон, царь Сиракуз, попросил Архимеда проверить, из чистого ли золота сделана его новая корона или ювелиры сплутовали. Помните, как мучился Архимед - слишком причудливы были контуры короны, чтобы разбить ее на цилиндры и конусы и геометрически вычислить объем. Помните, как в ояин прекрасный день выскочил он из ванны с ликующим криком "Эврика!", то есть "открыл!".

Он открыл, что корона такое же физическое тело, как и его собственное, и если погрузить ее в доверху наполненный водой сосуд, то объем вылившейся из сосуда воды будет равен объему короны. Архимед подарил нам первую эвристику, эвристику, которая работает до сих пор при измерении объемов тел сложной формы.

Мы не погружали в воду "Ханойскую башню" - и форма у нее простая, и объем башни нам знать ни к чему, Для нее мы нашли другие эвристики. Мы начали дело с конца, с цели, и попытались достичь ее сразу. Когда это не удалось, мы решили хотя бы приблизиться к цели и придумали промежуточную цель - освобождение большого кольца.

Ханойская башня

Это прекрасная эвристика - заменить недостижимую пока конечную цель промежуточной целью, достичь которую гораздо легче. Вся соль тут в том, чтобы почувствовать, что промежуточная цель не уводит в сторону от конечной, а приближает к ней. И еще одну эвристику мы изобрели, имя ей "ссылки лишних колец на запасной стержень". Нам повезло: эта эвристика доставила нас сначала к промежуточной, а потом и к конечной цели.

Вы, конечно, помните, уважаемый читатель, что рассказ о "Ханойской башне" понадобился нам, чтобы разъяснить, какого рода догадки-оценки (теперь мы скажем строже - эвристики) включены в программу САИНТ.

Программа САИНТ, подобно человеку, пытается решить задачу одним махом, заменив данный интеграл элементарным. Если это не получается, она производит алгебраические упрощения и снова пытается решить задачу. Если опять не выходит, САИНТ внимательно смотрит, что за птица-уравнение скрывается под знаком интеграла.

Как живых птиц отличают друг от друга форма клюва, оперение, размер и многие другие черты, так и подинтегральные птицы - алгебраические выражения - имеют каждая свои отличия. Как орнитолог оценивает птенчиков и после оценки надевает на их лапки кольца с перечнем их особенностей, так и САИНТ дотошно оценивает подинтегральное выражение и в памяти ЭВМ приписывает к нему его признаки.

Потом программа САИНТ берется за свой ассортимент эвристик. А он у нее не мал: в программе имеется набор из десяти эвристик, содержится десять драгоценных приемов интегрирования.

САИНТ вдумчиво перебирает эти свои эвристики, оценивает их одну за другой и примеряет каждую из них к подинтегральному выражению: эта не подходит вообще, и эта не подходит, а вот эта срабатывает, и эта годится, и эта тоже.

Программа работает с риском. Может добраться до цели за 3-4 хода, а может закрутиться в череде эвристик: преобразовала, оценила, снова преобразовала, снова оценила... и так без конца. Чтобы проверить успешность работы САИНТа, были взяты 54 задачи, предлагаемые на экзаменах первокурсникам в Массачусетском технологическом институте. Программа решила 52 из них. Две задачи оказались каверзными - память машины перегрузилась промежуточными целями и преобразованиями; САИНТ отпечатал: "Переполнение памяти. Неудача". Но и это неплохо! Ведь КПД САИНТа оказался близким к 96 процентам!

Естественно спросить, быстро ли САИНТ берет интегралы? Примерно с такой же скоростью, что и хороший студент (самый сложный интеграл она штурмовала 18 минут, а самый простой был взят через 1,8 секунды). Вспомним, что САИНТ работала на машине ИБМ-7090, безнадежно устаревшей на сегодняшний взгляд. Сегодня скородействие САИНТа повысилось бы в тысячу раз; чтобы перереши?!? весь задачник, ей понадобилось бы два-три часа. (Поправка: не весь задачник, а 96 процентов входящих в него задач; 4 процента САИНТ не решила бы даже за сутки, ибо САИНТ не строгий алгоритм, гарантирующий решение, а эвристическая программа)

Эвристики - суть этой программы, ее душа, ее радость и печаль.

Эвристики - проблески молнии во тьме проблем. Мрачна, как темная чаща, проблема. Не видно в ней ни зги, ни тропки, ни пути к цели. Но ярко вспыхивает эвристика, освещая все на мгновение; и надо воспользоваться моментом, чтобы увидеть дорогу к цели, пока проблема опять не погрузилась во мрак.