Программирование на языке Пролог для искусственного интеллекта
Шрифт:
В качестве иллюстрации, рассмотрим элементарное упражнение по программированию — вычисление наибольшего общего делителя D двух целых чисел А и В. Рассмотрим классический алгоритм Евклида:
Для того, чтобы вычислить наибольший общий делитель D чисел А и В, необходимо:
Повторять циклически, пока А и В не совпадут:
если А > В,
иначе заменить В на В - А.
После выхода из цикла А и В совпадают; наибольший общий делитель D равен А (или В).
Тот же самый процесс можно описать при помощи двух модулей, управляемых образцами:
Модуль 1
Условие В базе данных существуют такие два числа X и Y, что X > Y.
Действие Заменить X на разность X - Y.
Модуль 2
Условие В базе данных имеется число X.
Действие Выдать результат X и остановиться.
Очевидно, что всегда, когда условие Модуля 1 удовлетворяется, удовлетворяется также и условие Модуля 2, и мы имеем конфликт. В нашем случае конфликт можно разрешить при помощи простого управляющего правила: всегда отдавать предпочтение Модулю 1. База данных первоначально содержит числа А и В.
Здесь нас ждет приятный сюрприз: оказывается, что наша программа способна решать более общую задачу, а именно, она может вычислять наибольший общий делитель для любого количества чисел. Если в базу данных загрузить несколько целых чисел, то программа выведет их наибольший общий делитель. На рис. 16.3 показана возможная последовательность изменений, которые претерпевает база данных прежде, чем будет получен результат. Обратите внимание на то, что предварительные условия модулей могут удовлетворяться одновременно в нескольких местах базы данных.
Рис. 16.3. Процесс вычисления наибольшего общего делителя множества чисел. Первоначально база данных содержит числа 25, 10, 15 и 30. Вертикальная стрелка соединяет число с его "заменителем". Конечное состояние базы данных: 5, 5, 5, 5.
В данной главе мы реализуем интерпретатор простого языка для описания систем, управляемых образцами, и проиллюстрируем на примерах дух программирования в терминах образцов.
16.2. Простой интерпретатор программ, управляемых образцами
Для описания модулей, управляемых образцами, мы применим следующую синтаксическую конструкцию:
Часть условия представляет собой список условий:
где
Каждое отдельное действие — это, как и раньше, прологовская цель. Для того, чтобы выполнить список действий, нужно выполнить все действия из списка. Другими словами, все соответствующие цели должны быть удовлетворены. Среди допустимых действий будут действия, соответствующие манипулированию базой данных:
На рис. 16.4 показано, как выглядит наша программа вычисления наибольшего общего делителя, записанная в соответствии с введенным нами синтаксисом.
Рис. 16.4. Программа, управляемая образцами, для получения наибольшего общего делителя множества чисел.
Самый простой способ реализации этого языка — использовать механизмы управления базой данных, встроенные в Пролог. Добавить объект в базу данных или удалить объект из базы данных можно, применяя встроенные процедуры
Заменить один объект на другой также просто:
Здесь задача оператора отсечения — не допустить, чтобы оператор