Чтение онлайн

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

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

Возникает естественный вопрос: " Какая из трех программ наиболее эффективна?" В этом отношение программа 2 значительно хуже двух других, а эти последние - одинаковы. Причина в том, что основанная на перестановках программа 2 строит все перестановки, тогда как две другие программы способны отбросить плохую перестановку не дожидаясь, пока она будет полностью построена. Программа 3 наиболее эффективна. Она избегает некоторых арифметических вычислений, результаты которых уже сразу заложены в избыточное представление доски, используемое этой программой.

Упражнение

4. 7. Пусть поля доски представлены парами своих координат в виде X/Y, где как X, так и Y принимают значения от 1 до 8.

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

?- ходконя( 1/1, S).

S = 3/2;

S = 2/3;

no (нет)

(b) Определите отношение путьконя( Путь), где Путь– список полей, представляющих соответствующую правилам игры последовательность ходов коня по пустой доске.

(с) Используя отношение путьконя, напишите вопрос для нахождения любого пути, состоящего из 4-х ходов, и начинающегося с поля 2/1, а заканчивающегося на противоположном крае доски (Y= 8). Этот путь должен еще проходить после второго хода через поле 5/4.

Посмотреть ответ

Резюме

Примеры, рассмотренные в данном разделе, иллюстрируют некоторые достоинства и характерные черты программирования на Прологе:

Базу данных можно естественным образом представить в виде множества прологовских фактов.

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

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

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

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

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

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

Глава 5

УПРАВЛЕНИЕ ПЕРЕБОРОМ

Мы уже видели, что программист может управлять процессом вычислений по программе, располагая ее предложения и цели в том или ином порядке. В данной главе мы рассмотрим еще одно средство управления, получившее название "отсечение" (cut) и предназначенное для ограничения автоматического перебора.

5. 1. Ограничение перебора

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

Рис. 5. 1. Двухступенчатая функция

неэффективности программы. Поэтому иногда требуется его ограничить или исключить вовсе. Для этого в Прологе предусмотрена конструкция "отсечение".

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

Рассмотрим двухступенчатую функцию, изображенную на рис. 5.1. Связь между Х и Y можно определить с помощью следующих трех правил:

Правило 1: если Х < 3, то Y = 0

Правило 2: если 3 <= X и Х < 6, то Y = 2

Правило 3: если 6 <= X, то Y = 4

На Прологе это можно выразите с помощью бинарного отношения

f( X, Y)

так:

f( X, 0) :- X < 3. % Правило 1

f( X, 2) :- 3 =< X, X < 6. % Правило 2

f( X, 4) :- 6 =< X. % Правило 3

В этой программе предполагается, конечно, что к моменту начала вычисления f( X, Y) Х уже конкретизирован каким-либо числом; это необходимо для выполнения операторов сравнения.

Мы проделаем с этой программой два эксперимента. Каждый из них обнаружит в ней свой источник неэффективности, и мы устраним оба этих источника по очереди, применив оператор отсечения.

5. 1. 1. Эксперимент 1

Проанализируем, что произойдет, если задать следующий вопрос:

?- f( 1, Y), 2 < Y.

Рис. 5. 2. В точке, помеченной словом "ОТСЕЧЕНИЕ", уже известно,