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