Иван Братко - Программирование на языке Пролог для искусственного интеллекта

U is X-Y, % Соответствующая диагональ вверх

удалить( U, Du, Du1), % Ее удаление

V is X+Y, % Соответствующая диагональ вниз

удалить( V, Dv, Dv1), % Ее удаление

реш( СписY, Dх1, Dy1, Du1, Dv1).

% Выбор из оставшихся значений

удалить( А, [А | Список], Список).

удалить(A, [В | Список ], [В | Список1 ] ) :-

удалить( А, Список, Список1).

Рис. 4.11. Программа 3 для задачи о восьми ферзях.

Процедура реш универсальна в том смысле, что ее можно использовать для решения задачи об N ферзях (на доске размером N×N). Нужно только правильно задеть области Dx, Dy и т.д.

Удобно автоматизировать получение этих областей. Для этого нам потребуется процедура

генератор( N1, N2, Список)

которая для двух заданных целых чисел N1 и N2 порождает список

Список = [N1, N1 + 1, N1 + 2, ..., N2 - 1, N2]

Вот она:

генератор( N, N, [N]).

генератор( Nl, N2, [Nl | Список]) :-

N1 < N2,

М is N1 + 1,

генератор( М, N2, Список).

Главную процедуру решение нужно соответствующим образом обобщить:

решение( N, S)

где N — это размер доски, а S — решение, представляемое в виде списка Y-координат N ферзей. Вот обобщенное отношение решение:

решение( N, S) :-

генератор( 1, N, Dxy),

Nu1 is 1 - N, Nu2 is N - 1,

генератор( Nu1, Nu2, Du),

Nv2 is N + N,

генератор( 2, Nv2, Dv),

реш( S, Dxy, Dxy, Du, Dv).

Например, решение задачи о 12 ферзях будет получено с помощью:

?- решение( 12, S).

S = [1, 3, 5, 8, 10, 12, 6, 11, 2, 7, 9, 4]

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

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

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

Возникает естественный вопрос: " Какая из трех программ наиболее эффективна?" В этом отношение программа 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-x ходов, и начинающегося с поля 2/1, а заканчивающегося на противоположном крае доски (Y = 8). Этот путь должен еще проходить после второго хода через поле 5/4.

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

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

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