текущем состоянии. Однако абстрактные недетерминированные машины такого типа обладают волшебным свойством: если существует выбор, они всегда избирают "правильный" переход, т.е. переход, ведущий к допущению входной цепочки при наличии такого перехода. Автомат на рис. 4.3, например, допускает цепочки  аb  и  aabaab,   но отвергает цепочки  abb  и  abba.   Легко видеть, что этот автомат допускает любые цепочки, оканчивающиеся на  аb  и отвергает все остальные.

Некоторый автомат можно описать на Прологе при помощи трех отношений:

(1)        Унарного отношения конечное, которое определяет конечное состояние автомата.

(2)        Трехаргументного отношения переход, которое определяет переход из состояния в состояние, при этом

        переход( S1, X, S2)

означает переход из состояния S1 в S2, если считан входной символ X.

(3)        Бинарного отношения

        спонтанный( S1, S2)

означающего, что возможен спонтанный переход из S1 в S2.

Для автомата, изображенного на рис. 4.3, эти отношения будут такими:

        конечное( S3).

        переход( S1, а, S1).
        переход( S1, а, S2).
        переход( S1, b, S1).
        переход( S2, b, S3).
        переход( S3, b, S4).

        спонтанный( S2, S4).
        спонтанный( S3, S1).

Представим входные цепочки в виде списков Пролога. Цепочка  ааb  будет представлена как [а, а, b]. Модель автомата, получив его описание, будет обрабатывать заданную входную цепочку, и решать, допускать ее или нет. По определению, недетерминированный автомат допускает заданную цепочку, если (начав из начального состояния) после ее прочтения он способен оказаться в конечном состоянии. Модель программируется в виде бинарного отношения допускается, которое определяет принятие цепочки из данного состояния. Так

        допускается( Состояние, Цепочка)

истинно, если автомат, начав из состояния Состояние как из начального, допускает цепочку Цепочка. Отношение допускается можно определить при помощи трех предложений. Они соответствуют следующим трем случаям:

(1)        Пустая цепочка [ ] допускается из состояния S, если S - конечное состояние.

(2)        Непустая цепочка допускается из состояния S, если после чтения первого ее символа автомат может перейти в состояние S1, и оставшаяся часть цепочки допускается из S1. Этот случай иллюстрируется на рис. 4.4(а).

(3)        Цепочка допускается из состояния S, если автомат может сделать спонтанный переход из S в S1, а затем допустить (всю) входную цепочку из S1. Такой случай иллюстрируется на рис. 4.4(b).

Эти правила можно перевести на Пролог следующим образом:

        допускается( S, [ ]) :-
                               % Допуск пустой цепочки
              конечное( S).

        допускается( S, [X | Остальные]) :-
                               % Допуск чтением первого символа
              переход( S, X, S1),
              допускается( S1, Остальные).

        допускается( S, Цепочка) :-
                               % Допуск выполнением спонтанного перехода
              спонтанный( S, S1),
              допускается( S1, Цепочка).

Спросить о том, допускается ли цепочка  аааb,   можно так:

        ?-  допускается( S1, [a, a, a, b]).

        yes             (да)

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

        ?-  допускается( S, [a, b]).

        S = s1;
        S = s3

Как ни странно, мы можем спросить также "Каковы все цепочки длины 3, допустимые из состояния s1?"

        ?-  допускается( s1, [XI, Х2, X3]).

        X1 = а
        Х2 = а
        Х3 = b;

        X1 = b
        Х2 = а
        Х3 = b;

        nо               (нет)

Если мы предпочитаем, чтобы допустимые цепочки выдавались в виде списков, тогда наш вопрос следует сформулировать так:

        ?- Цепочка = [ _, _, _ ], допускается( s1, Цепочка).

        Цепочка = [а, а, b];
        Цепочка = [b, а, b];

        nо                (нет)

Можно проделать и еще некоторые эксперименты, например спросить: "Из какого состояния автомат допустит цепочку длиной 7?"

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

        спонтанный( s1, s3)

то получится "спонтанный цикл". Теперь наша модель может столкнуться с неприятностями. Например, вопрос

        ?-  допускается( s1, [а]).

приведет к тому, что модель будет бесконечно переходить в состояние s1, все время надеясь отыскать какой-либо путь в конечное состояние.

Использование структур: примеры

Глава 4. ИСПОЛЬЗОВАНИЕ СТРУКТУР: ПРИМЕРЫ

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

Недетерминированный конечный автомат - это абстрактная машина, которая читает символы из входной цепочки и решает, допустить или отвергнуть эту цепочку. Автомат имеет несколько состояний и всегда находится в одном из них. Он может изменить состояние, перейдя из одного состояния в другое. Внутреннюю структуру такого автомата можно представить графом переходов, как показано на рис. 4.3. В этом примере S1, S2,   S3  и  S4  - состояния автомата. Стартовав из начального состояния (в нашем примере это S1 ), автомат переходит из состояния в состояние по мере чтения входной цепочки. Переход зависит от текущего входного символа, как указывают метки на дугах графа переходов.

Описания объектов по их структурным...

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

        муж( X) :-                           % X - муж
               семья( X, _, _ ).

        жена( X) :-                         % X - жена
               семья( _, X, _ ).

        ребенок( X) :-                     % X - ребенок
               семья( _, _, Дети),
               принадлежит( X, Дети).

        принадлежит( X, [X | L ]).

        принадлежит( X, [Y | L ]) :-
               принадлежит( X, L).

        существует( Членсемьи) :-
                                   % Любой член семьи в базе данных

            муж( Членсемьи);
            жена( Членсемьи);
            ребенок( Членсемьи).

        дата рождения( Членсемьи( _, _, Дата, _ ), Дата).

        доход( Членсемьи( _, _, _, работает( _, S) ), S).
                                                                % Доход работающего

        доход( Членсемьи( _, _, _, неработает), 0).
                                                                % Доход неработающего

Этими процедурами можно воспользоваться, например, в следующих запросах к базе данных: Найти имена всех людей из базы данных:

        ?-  существует( членсемьи( Имя,Фамилия, _, _ )).
Найти всех детей, родившихся в 1981 году:

        ?-  ребенок( X), датарождения( X, дата( _, _, 1981) ).
Найти всех работающих жен:

        ?-  жена( членсемьи( Имя, Фамилия, _, работает( _, _ ))).
Найти имена и фамилии людей, которые не работают и родились до 1963 года:

?-  существует членсемьи( Имя, Фамилия, дата( _, _, Год), неработает) ),
     Год < 1963.
Найти людей, родившихся до 1950 года, чей доход меньше, чем 8000:

        ?-  существует( Членсемьи),
             датарождения( Членсемьи, дата( _, _, Год) ),
             Год < 1950,
             доход( Членсемьи, Доход),
             Доход < 8000.
Найти фамилии людей, имеющих по крайней мере трех детей:

        ?-  семья( членсемьи( _, Фамилия, _, _ ), _, [ _, _, _ | _ ]).

Для подсчета общего дохода семья полезно определить сумму доходов людей из некоторого списка в виде двухаргументного отношения:

        общий( Список_Людей, Сумма_их_доходов)

Это отношение можно запрограммировать так:

        общий( [ ], 0).                     % Пустой список людей

        общий( [ Человек | Список], Сумма) :-
               доход( Человек, S),
                                % S - доход первого человека
               общий( Список, Остальные),
                                % Остальные - сумма доходов остальных
               Сумма is S + Остальные.

Теперь общие доходы всех семей могут быть найдены с помощью вопроса:

        ?-  семья( Муж, Жена, Дети),
             общий( [Муж, Жена | Дети], Доход).

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

        ?-  семья( Муж, Жена, Дети),
             общий( [ Муж, Жена | Дети], Доход),
             длина( [ Муж, Жена | Дети], N),
             Доход/N < 2000.

Планирование поездки

В данном разделе мы создадим программу, которая дает советы по планированию воздушного путешествия. Эта программа будет довольно примитивным советчиком, тем не менее она сможет отвечать на некоторые полезные вопросы, такие как: По каким дням недели есть прямые рейсы из Лондона в Любляну? Как в четверг можно добраться из Любляны в Эдинбург? Мне нужно посетить Милан, Любляну и Цюрих; вылетать нужно из Лондона во вторник и вернуться обратно в Лондон в пятницу. В какой последовательности мне следует посещать эти города, чтобы ни разу на протяжении поездки не пришлось совершать более одного перелета в день.

Центральной частью программы будет база данных, содержащая информацию о рейсах. Эта информация будет представлена в виде трехаргументного отношения:

        расписание( Пункт1, Пункт2, Список_рейсов)

где  Список_рейсов  -  это список, состоящий из структурированных объектов вида:

        Время_отправления / Время_прибытия / Номер_рейса
                                              / Список_дней_вылета

Список_дней_вылета - это либо список дней недели, либо атом "ежедневно". Одно из предложений, входящих в расписание могло бы быть, например, таким:

        расписание( лондон, эдинбург,
                        [ 9:40 / 10:50 / bа4733/ ежедневно,
                        19:40 / 20:50 / bа4833 / [пн, вт, ср, чт, пт, сб]] ).

Время представлено в виде структурированных объектов, состоящих из двух компонент - часов и минут, объединенных оператором ":".

Главная задача состоит в отыскании точных маршрутов между двумя заданными городами в определенные дни недели. Ее решение мы будем программировать в виде четырехаргументного отношения:

        маршрут( Пункт1, Пункт2, День, Маршрут)

Здесь Маршрут - это последовательность перелетов, удовлетворяющих следующим критериям:

(1)        начальная точка маршрута находится в Пункт1;
(2)        конечная точка - в Пункт2;
(3)        все перелеты совершаются в один и тот же день недели - День;
(4)        все перелеты, входящие в Маршрут, содержатся в определении отношения расписание;
(5)        остается достаточно времени для пересадки с рейса на рейс.

Маршрут представляется в виде списка структурированных объектов вида

        Откуда - Куда : Номер_рейса : Время_отправления

Мы еще будем пользоваться следующими вспомогательными предикатами:

(1)        рейс( Пункт1, Пункт2, День, N_рейса, Вр_отпр, Вр_приб)

Здесь сказано, что существует рейс N_рейса между Пункт1 и Пункт2 в день недели День с указанными временами отправления и прибытия.

(2)        вр_отпр( Маршрут, Время)

Время - это время отправления по маршруту Маршрут.

(3)        пересадка( Время1, Время2)

Между Время1 и Время2 должен существовать промежуток не менее 40 минут для пересадки с одного рейса на другой.

Задача нахождения маршрута напоминает моделирование недетерминированного автомата из предыдущего раздела: Состояния автомата соответствуют городам. Переход из состояния в состояние соответствует перелету из одного города в другой. Отношение переход автомата соответствует отношению расписание. Модель автомата находит путь в графе переходов между исходным и конечным состояниями; планировщик поездки находит маршрут между начальным н конечным пунктами поездки.

Неудивительно поэтому, что отношение маршрут можно определить аналогично отношению допускает, с той разницей, что теперь нет "спонтанных переходов". Существуют два случая:

(1)        Прямой рейс: если существует прямой рейс между пунктами Пункт1 и Пункт2, то весь маршрут состоит только из одного перелета:

        маршрут( Пункт1, Пункт2, День, [Пункт1-Пункт2 : Nр : Отпр]):-
              рейс( Пункт1, Пункт2, День, Np, Отпр, Приб).

(2)        Маршрут с пересадками: маршрут между пунктами Р1 и Р2 состоит из первого перелета из P1 в некоторый промежуточный пункт Р3 и маршрута между Р3 и Р2. Кроме того, между окончанием первого перелета и отправлением во второй необходимо оставить достаточно времени для пересадки.

        маршрут( Р1, Р2, День, [Р1-Р3 : Nр1 : Отпр1 | Маршрут]) :-
              маршрут( Р3, Р2, День, Маршрут ),
              рейс( Р1, Р3, День, Npl, Oтпpl, Приб1),
              вр_отпр( Маршрут, Отпр2),
              пересадка( Приб1, Отпр2).

Вспомогательные отношения рейс, пересадка и вр_отпр запрограммировать легко; мы включили их в полный текст программы планировщика поездки на рис. 4.5. Там же приводится и пример базы данных расписания.

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

Вот некоторые примеры вопросов к планировщику: По каким дням недели существуют прямые рейсы из Лондона в Люблину?

        ?- рейс( лондон, любляна, День, _, _, _ ).

        День = пт;
        День = сб;

        no                 (нет) line();

% ПЛАНИРОВЩИК ВОЗДУШНЫХ МАРШРУТОВ

:- ор( 50, xfy, :).

рейс( Пункт1, Пункт2, День, Np, ВрОтпр, ВрПриб) :-
    расписание( Пункт1, Пункт2, СписРейсов),
    принадлежит( ВрОтпр / ВрПриб / Nр / СписДней, СписРейсов),
    день_выл( День, СписДней).

принадлежит( X, [X | L] ).

принадлежит( X, [Y | L] ) :-
      принадлежит( X, L ).

день_выл( День, СписДней) :-
      принадлежит( День, СписДней).

день_выл( День, ежедневно) :-
      принадлежит( День, [пн, вт, ср, чт, пт, сб, вс] ).

маршрут( P1, P2, День, [Р1-Р2 : Np : ВрОтпр] ) :-
                                                % прямой рейс
      рейс( P1, P2, День, Np, ВрОтпр, _ ).

маршрут( Р1, Р2, День, [Pl-P3 : Np1 : Oтпp1 | Маршрут]) :-
                                                % маршрут с пересадками
      маршрут( Р3, P2, День, Маршрут ),
      рейс( Р1, Р3, День, Npl, Oтпp1, Приб1),
      вр_отпр( Маршрут, Отпр2),
      пересадка( Приб1, Отпр2).

вр_отпр( [Р1-Р2 : Np : Отпр | _ ], Отпр).

пересадка( Часы1 : Минуты1, Часы2 : Минуты2) :-
      60 * (Часы2-Часы1) + Минуты2 - Минуты1 >= 40

% БАЗА ДАННЫХ О РЕЙСАХ САМОЛЕТОВ

расписание( эдинбург, лондон,
      [ 9:40 / 10:50 / bа4733 / ежедневно,
      13:40 / 14:50 / ba4773 / ежедневно,
      19:40 / 20:50 / bа4833 / [пн, вт, ср, чт, пт, вс] ] ).

расписание( лондон, эдинбург,
      [ 9:40 / 10:50 / bа4732 / ежедневно,
      11:40 / 12:50 / bа4752 / ежедневно,
      18:40 / 19:50 / bа4822 / [пн, вт, ср, чт, пт] ] ),

расписание( лондон, любляна,
      [13:20 / 16:20 / ju201 / [пт],
       13:20 / 16:20 / ju213 / [вс] ] ).

расписание( лондон, цюрих,
      [ 9:10 / 11:45 / bа614 / ежедневно,
      14:45 / 17:20 / sr805 / ежедневно ] ).

расписание( лондон, милан,
      [ 8:30 / 11:20 / bа510 / ежедневно,
      11:00 / 13:50 / az459 / ежедневно ] ).

расписание( любляна, цюрих,
      [11:30 / 12:40 / ju322 / [вт,чт] ] ).

расписание( любляна, лондон,
      [11:10 / 12:20 / yu200 / [пт],
       11:25 / 12:20 / yu212 / [вс] ] ).

расписание( милан, лондон,
      [ 9:10 / 10:00 / az458 / ежедневно,
      12:20 / 13:10 / bа511 / ежедневно ] ).

расписание( милан, цюрих,
      [ 9:25 / 10:15 / sr621 / ежедневно,
      12:45 / 13:35 / sr623 / ежедневно ] ).

расписание( цюрих, любляна,
      [13:30 / 14:40 / yu323 / [вт, чт] ] ).

расписание( цюрих, лондон,
      9:00 / 9:40 / bа613 /
      [ пн, вт, ср, чт, пт, сб],
      16:10 / 16:55 / sr806 / [пн, вт, ср, чт, пт, сб] ] ).

расписание( цюрих, милан,
      [ 7:55 / 8:45 / sr620 / ежедневно ] ).

Планировщик воздушных маршрутов и база данных о рейсах самолетов.

Получение структурированной информации из базы данных

Это упражнение развивает навыки представления структурных объектов данных и управления ими. Оно показывает также, что Пролог является естественным языком запросов к базе данных.

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

Пример недетерминированного конечного автомата.

Переход выполняется всякий раз при чтении входного символа. Заметим, что переходы могут быть недетерминированными. На рис. 4.3 видно, что если автомат находится в состоянии S1, и текущий входной символ равен  а,  то переход может осуществиться как в S1, так и в  S2.  Некоторые дуги помечены меткой пусто, обозначающей "пустой символ". Эти дуги соответствуют "спонтанным переходам" автомата. Такой переход называется спонтанным, потому что он выполняется без чтения входной цепочки. Наблюдатель, рассматривающий автомат как черный ящик, не сможет обнаружить, что произошел какой-либо переход.

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

(1)        он начинается в начальном состоянии,
(2)        он оканчивается в конечном состоянии, и
(3)        метки дуг, образующих этот путь, соответствуют полной входной цепочке.

Решать, какой из возможных переходов делать в каждый момент времени - исключительно внутреннее дело автомата. В частности, автомат сам решает, делать ли спонтанный переход, если он возможен в

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

Система будет генерировать решения в таком виде:

        S = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1];
        S = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1];
        S = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1].
        . . .

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

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

        небьет( Ферзь, Остальные)

обеспечивает отсутствие нападении ферзя Ферзь на поля списка Остальные в случае, когда расстояние по Х между Ферзь и Остальные равно 1. Остается рассмотреть более общий случай произвольного расстояния. Для этого мы добавим его в отношение небьет в качестве третьего аргумента:

        небьет( Ферзь, Остальные, РасстХ)

Соответственно и цель небьет в отношении безопасный должна быть изменена на

        небьет( Ферзь, Остальные, 1)

Теперь отношение небьет может быть сформулировано в соответствии с двумя случаями, в зависимости от списка Остальные: если он пуст, то бить некого и, естественно, нет нападений; если же он не пуст, то Ферзь не должен бить первого ферзя из списка Остальные (который находится от ферзя Ферзь на расстоянии РасстХ вертикалей), а также ферзей из хвоста списка Остальные, находящихся от него на расстоянии РасстХ + 1. Эти соображения приводят к программе, изображенной на рис. 4.9.

Наша третья программа для задачи о восьми ферзях опирается на следующие соображения. Каждый ферзь должен быть размещен на некотором поле, т. е. на некоторой вертикали, некоторой горизонтали, а также на пересечении каких-нибудь двух диагоналей. Для того, чтобы была обеспечена безопасность каждого ферзя, все они должны располагаться в разных вертикалях, разных горизонталях и в разных диагоналях (как идущих сверху вниз, так и идущих снизу вверх). Естественно поэтому рассмотреть более богатую систему представления с четырьмя координатами:

    x         вертикали
    у         горизонтали
    u         диагонали, идущие снизу вверх
    v         диагонали, идущие сверху вниз

Эти координаты не являются независимыми: при заданных  х  и  у,  u  и   v  определяются однозначно (пример на рис.4.10). Например,

    u = х - у
    v = х + у

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

задачи о восьми ферзях.

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

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

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

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

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

Вот она:

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

        генератор( Nl, N2, [Nl | Список]) :-
                    Nl < N2,
                    М is Nl + 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 наиболее эффективна. Она избегает некоторых арифметических вычислений, результаты которых уже сразу заложены в избыточное представление доски, используемое этой программой.

Решение задачи о восьми ферзях. Эта позиция может

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

Основная часть работы при таком подходе ложится на нахождение правильного обобщения исходной задачи. В нашем случае хорошей является идея обобщать задачу в отношении количества ферзей (количества вертикалей в списке), разрешив количеству ферзей принимать любое значение, включая нуль. Тогда отношение решение можно сформулировать, рассмотрев два случая:

Случай 1.    Список ферзей пуст. Пустой список без сомнения является решением, поскольку нападений в этом случае нет.

Случай 2.    Список ферзей не пуст. Тогда он выглядит так:

        [ X/Y | Остальные ]

В случае 2 первый ферзь находится на поле Х / Y, а остальные - на полях, указанных в списке Остальные. Если мы хотим, чтобы это было решением, то должны выполняться следующие условия:

(1)        Ферзи, перечисленные в списке Остальные, не должны бить друг друга; т. е. список Остальные сам должен быть решением.

(2)        Х и Y должны быть целыми числами от 1 до 8.

(3)        Ферзь, стоящий на поле X / Y, не должен бить ни одного ферзя из списка Остальные.

Чтобы запрограммировать первое условие, можно воспользоваться самим отношением решение. Второе условие можно сформулировать так: Y должен принадлежать списку целых чисел от 1 до 8. т. е. [1, 2, 3, 4, 5, 6, 7, 8]. С другой стороны, о координате Х можно не беспокоиться, поскольку список-решение должен соответствовать шаблону, у которого Х-координаты уже определены. Поэтому Х гарантированно получит правильное значение от 1 до 8. Третье условие можно обеспечить с помощью нового отношения небьет. Все это можно записать на Прологе так:

        решение( [X/Y | Остальные] ) :-
               решение( Остальные),
               принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] ),
               небьет( X/Y, Остальные).

Осталось определить отношение небьет:

        небьет( Ф, Фспис)

И снова его описание можно разбить на два случая:

(1)        Если список Фспис пуст, то отношение, конечно, выполнено, потому что некого бить (нет ферзя, на которого можно было бы напасть).

(2)        Если Фспис не пуст, то он имеет форму

        [Ф1 | Фспис1]

и должны выполняться два условия:

        (а)         ферзь на поле Ф не должен бить ферзя на поле Ф1 и

        (b)         ферзь на поле Ф не должен бить ни одного ферзя из списка Фспис1.

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

На рис. 4.7 приведен полный текст программы. Чтобы облегчить ее использование, необходимо добавить список-шаблон. Это можно сделать в запросе на генерацию решений. Итак:

        ?-  шаблон( S), решение( S).

решение( [ ] ).

решение( [X/Y | Остальные ] ) :-
                        % Первый ферзь на поле X/Y,
                        % остальные ферзи на полях из списка Остальные
        решение( Остальные),
        принадлежит Y, [1, 2, 3, 4, 5, 6, 7, 8] ),
        небьет( X/Y | Остальные).
                        % Первый ферзь не бьет остальных

небьет( _, [ ]).                                 % Некого бить

небьет( X/Y, [X1/Y1 | Остальные] ) :-
            Y =\= Y1,                             % Разные Y-координаты
            Y1-Y =\= X1-X                    % Разные диагонали
            Y1-Y =\= X-X1,
            небьет( X/Y, Остальные).

принадлежит( X, [X | L] ).

принадлежит( X, [Y | L] ) :-
            принадлежит( X, L).

% Шаблон решения

шаблон( [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

в данном разделе, иллюстрируют некоторые

Структурированная информация о семье.

четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе - это либо "не работает", либо указание места работа и оклада (дохода). Информацию о семье, изображенной на рис. 4.1, можно занести в базу данных с помощью предложения:

        семья( членсемьи( том, фокс, дата( 7, май, 1950),
              работает( bbс, 15200) ),
              членсемьи( энн, фокс, дата( 9, май, 1951), неработает),
              [членсемьи( пат, фокс, дата( 5, май, 1973), неработает),
              членсемьи( джим, фокс, дата( 5, май, 1973), неработает) ] ).

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

В действительности Пролог очень удобен для извлечения необходимой информации из такой базы данных. Здесь хорошо то, что можно ссылаться на объекты, не указывая в деталях всех их компонент. Можно задавать только структуру интересующих нас объектов и оставлять конкретные компоненты без точного описания или лишь с частичным описанием. На рис. 4.2 приведено несколько примеров. Так, а запросах к базе данных можно ссылаться на всех Армстронгов с помощью терма

        семья( членсемьи( _, армстронг, _, _ ), _, _ )

Символы подчеркивания обозначают различные анонимные переменные, значения которых нас не заботят. Далее можно сослаться на все семьи с тремя детьми при помощи терма:

        семья( _, _, [ _, _, _ ])

Чтобы найти всех замужних женщин, имеющих по крайней мере троих детей, можно задать вопрос:

        ?-  семья( _, членсемьи( Имя, Фамилия, _, _ ), [ _, _, _ | _ ]).

Главным моментом в этих примерах является то, что указывать интересующие нас объекты можно не только по их содержимому, но и по их структуре. Мы задаем одну структуру и оставляем ее аргументы в виде слотов (пропусков).

Связь между вертикалями, горизонталями и диагоналями.

Области изменения всех четырех координат таковы:

        Dx = [1, 2, 3, 4, 5, 6, 7, 8]
        Dy = [1, 2, 3, 4, 5, 6, 7, 8]

        Du = [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
        Dv = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Задачу о восьми ферзях теперь можно сформулировать следующим образом: выбрать восемь четверок (X, Y, U, V), входящих в области изменения (X в Dx, Y в Dy и т.д.), так, чтобы ни один их элемент не выбирался дважды из одной области. Разумеется, выбор Х и Y определяет выбор U и V. Решение при такой постановке задачи может быть вкратце таким: при заданных 4-х областях изменения выбрать позицию для первого ферзя, вычеркнуть соответствующие элементы из 4-х областей изменения, а затем использовать оставшиеся элементы этих областей для размещения остальных ферзей. Программа, основанная на таком подходе, показана на рис. 4.11. Позиция на доске снова представляется списком Y-координат. Ключевым отношением в этой программе является отношение

        peш( СписY, Dx, Dy, Du, Dv)

которое конкретизирует Y-координаты (в СписY) ферзей, считая, что они размещены в последовательных вертикалях, взятых из Dx. Все Y-координаты и соответствующие координаты U и V берутся из списков Dy, Du и Dv. Главную процедуру решение можно запустить вопросом

        ?-  решение( S)

Это вызовет запуск реш с полными областями изменения координат, что соответствует пространству

решение( СписY) :-
        реш( СписY,                 % Y-координаты ферзей
                    [1, 2, 3, 4, 5, 6, 7, 8],
                                             % Область изменения Y-координат
                    [1, 2, 3, 4, 5, 6, 7, 8],
                                              % Область изменения Х-координат
                    [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7],
                                              % Диагонали, идущие снизу вверх
                    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 14, 15, 16] ).
                                              % Диагонали, идущие сверху вниз
реш([ ], [ ], Dy, Du, Dv).

реш( [Y | СписY], [X | Dx1], Dy, Du, Dv) :-
        удалить( Y, Dy, Dy1),             % Выбор Y-координаты
        U is X-Y                             % Соответствующая диагональ вверх
        удалить( U, Du, Du1),             % Ее удаление
        V is X+Y                            % Соответствующая диагональ вниз
        удалить( V, Dv, Dv1),             % Ее удаление
        реш( СписY, Dх1, Dy1, Du1, Dv1).
                                                  % Выбор из оставшихся значений

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

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

Завершите определение отношения nребенок, определив

При поиске решения программа, приведенная

Пусть поля доски представлены парами

в возрасте родителей которых составляет

Почему не могло возникнуть зацикливание