5.12.4. Другие задачи, которые можно решить с помощью GPS

Последняя версия программы GPS, разработанная Эрнстом и Ньюэллом (1967), была рассчитана на одиннадцать различных типов задач. Ей требовалось с на каждую порожденную цель. Таким образом, для решения задачи об обезьяне и бананах, порождающей 13 целей, требовалось мин на ЭВМ типа Унивеситета Карнеги — Меллона, США.

Формальное интегрирование. Первая задача в этом новом цикле состояла в том, чтобы проинтегрировать функцию Результат получался за 3 мин после порождения 11 целей. Выражение интегрируется с результатом

Рис. 5.31. (см. скан) Дерево поиска программы GPS для решения логической задачи.

за время приблизительно вдвое большее с порождением примерно в два раза большего числа целей.

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

случаям интегрирования, а также четыре оператора дифференцирования. Еще один оператор отмечает, что интеграл суммы равен сумме интегралов. Классические алгебраические действия — сложение и умножение, а также свойства ассоциативности и коммутативности программируются отдельно и включаются в GPS.

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

В данном случае объекты состоят из двух частей, каждая из которых соответствует тому, что находится на каждом из берегов реки. Каждая часть содержит описание числа миссионеров, числа людоедов и указание на наличие или отсутствие лодки. Итак, для каждого из двух направлений передвижения мы располагаем пятью операторами преобразования, поскольку на лодке может находиться либо один людоед, либо один миссионер, либо людоед с миссионером, либо два людоеда, либо, наконец, два миссионера.

Программа GPS, используя характерный для нее подход “цели — средства” и легко имитируемая вручную, строит 57 целей и приходит к следующему решению:

На этой схеме берег, с которого началось перемещение, описывается в следующем виде: число миссионеров, число людоедов, наличие (1) или отсутствие (0) лодки. Отметим, что данное решение является симметричным по отношению к шестому пересечению реки. В действительности это свойство имеет объяснение и сохраняется в других примерах той же задачи, как показано Саулом Амарелем (1968).

Ханойская башня. Эта задача, придуманная французским математиком Эдуардом Люка, представляет собой головоломку, в которой нужно перекладывать кольцо с одного стержня на другой. В начальный момент времени имеются три стержня А, В и С и четыре кольца, каждое из которых по внешнему диаметру строго меньше предыдущего; все кольца надеты на стержень А так, что самое маленькое находится наверху. За один

ход мы можем переместить одно верхнее кольцо с одного стержня на другой; при этом класть большие диски на меньшие запрещено. Как переложить все кольца с А на С?

Как и в предыдущих задачах для использования одного из шести допустимых операторов должны быть выполнены некоторые условия. В этом примитивном пространстве GPS решает задачу за 46 этапов, не порождая ни одной бесполезной цели,

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

Рис. 5.32. Семь мостов через Преголю.

В описание объектов включен счетчик, который учитывает это ограничение. Для полного решения данной задачи программе GPS достаточно породить 10 целей.

Семь мостов через Преголю. Река Преголя в Калининграде отделяет от берегов два острова, которые соединены друг с другом и с остальной частью города семью мостами (рис. 5.32).

В данной задаче операторы соответствуют четырнадцати возможным перемещениям. Задача состоит в том, чтобы выйти из произвольной точки и вернуться в нее, пройдя по каждому мосту только один раз.

Как доказал Леонард Эцлер в 1736 г. - решить эту задачу невозможно. Поскольку особых способов решения наша программа не знает, в данном случае она терпит поражение. Единственное, что может программа, — перебрать все возможности, но уже после перебора различных способов прохождения по шести мостам объем памяти компьютера оказался исчерпанным.

Два кувшина. Имеется неограниченный запас воды и два кувшина на 5 и 8 л. Как налить в маленький кувшин 2 л воды?

После нескольких попыток, обусловленных существенной разницей между двумя крайними ситуациями, GPS решает задачу, выделив при этом 24 цели.

Отец и сыновья. Отец, два его сына и лодка находятся по одну сторону реки. Отец весит 80 кг, сыновья — по 40 кг каждый. Как переправить эту семью на другую сторону, если лодка выдерживает только 80 кг?

Программа дает ответ, обработав 33 цели.

Продолжение последовательности букв. Требуется к последовательности букв добавить 2 следующие буквы.

Подобно другим тестам такого типа, эта задача ставит фундаментальный вопрос о мере простоты результата. В данном случае мы можем допустить, что равным образом подойдут продолжения и . В случае ответа последовательность будет повторяться с самого начала. Что касается ответа (в принципе более предпочтительного), в общем случае он не является однозначным. Итак, здесь особенно важен тот способ, которым задача записывается для GPS. Эта запись менее очевидна, чем в рассмотренных выше случаях. Объекты задаются не в виде последовательностей букв, а в виде частичных последовательностей с определенными отношениями между буквами. Две буквы могут быть связаны либо отношением тождества, которое указывает на их идентичность, либо отношением следования, указывающим на то, что вторая буква стоит в алфавите после первой.

Что касается конечного объекта, то на него накладываются три ограничения, которые должны быть выполнены, как только мы преобразуем исходный объект. Первое состоит в том, что должны быть заполнены пробелы (в нашем случае два имеющихся пробела заменяются двумя буквами — Второе ограничение требует, чтобы множество отношений, позволяющих описать конечную цепочку, было как можно более простым: если одна и та же цепочка описывается с помощью одного и того же набора отношений двумя различными способами, то более простым считается то описание, в котором операнды отделяются друг от друга минимальным числом букв. Третье ограничение состоит в том, что каждая буква должна участвовать по крайней мере в одном отношении. В основном можно применять два оператора: один приписывает двум буквам в последовательности некоторое отношение, а другой — букве определенное значение. Кроме того, возможен третий оператор,

который задает порядок прохождения последовательности слева направо. Таким образом, программа GPS постепенно обнаруживает и отмечает присущие последовательности свойства. Приписывая заранее значения буквам х и у, GPS не вслепую, а логически выводит те значения, которые она должна выбрать, чтобы эти буквы вступали в те же отношения, что и буквы, которым они соответствуют. Следовательно, для программы GPS изучение исходного объекта приводит к схеме, показанной на рис. 5.33.

Пробегая заданную последовательность слева направо, GPS отмечает отношение тождества между первой и третьей и третьей и пятой буквами.

Рис. 5.33. Последовательность букв, которую требуется продолжить.

Поэтому, чтобы это отношение было опять подтверждено, GPS должна принять значение В. Оставшаяся часть последовательности обрабатывается параллельно. В целом для получения правильной последовательности с помощью такого индуктивного метода программа порождает 27 целей.

Грамматический анализ. Проанализируем фразу естественного языка в соответствии с заданной грамматикой. В число грамматических правил, введенных в нашу программу, входят следующие правила: Фраза содержит именную группу, за которой следует глагольная группа, а за ней вновь следует именная группа. Именная группа может состоять из группы прилагательного, за которой следует слово, выполняющее функции существительного.

Именная группа может состоять из слова, выполняющего функции существительного. Группа прилагательного может состоять из слова, выполняющего функции прилагательного.

Еще одно правило уточняет, что, например, слово («дверь» или «несет») может быть либо именем существительным, либо глаголом, («форт» или «сильный») может быть либо существительным, либо прилагательным..

Итак, пусть основная цель состоит в том, чтобы квалифицировать последовательность символов une epaisse porte ferme le fort (исходный объект) как фразу (конечный объект). Поскольку epaisse (толстый) может относиться только к классу прилагательных, наша программа делает вывод, что porte используется здесь как существительное, а также делает предположение о том, что ferme является глаголом (закрывает), следовательно, fort — существительное.

Исходная английская фраза — free variables cause confusion (свободные переменные причиняют неудобства) - анализируется с помощью 19 целей. Эта задача демонстрирует преимущества эвристического метода для некоторых типов алгоритмов (например, таких, которые используются в синтаксическом анализе).

Доказательство теорем. Кроме задачи исчисления высказываний программа GPS может доказывать некоторые теоремы из области исчисления предикатов первого порядка, используя особый метод, получивший название резолюции (он был предложен в 1931 г. Жаком Эрбраном и запрограммирован в 1965 г. Дж. А. Робинсоном — см. гл. 3).

Классическая теорема Черча (1965), в которой утверждается, что

после упрощения, сколемизации и приведения к требуемому для метода резолюции виду (все предикаты приведены к нормальной конъюнктивной форме, а кванторы исключены), может быть доказана с помощью GPS. Доказательство завершается после того, как порождение 59-й цели позволяет обнаружить противоречие.