в(massinga,858,

  в(braermar,385,

    в(adela,588,_,_),

    _),

   в(panorama,158,

     в(nettleweed,579,_,_),

     _).

).

Теперь, располагая такой структурой, мы хотим «просмотреть» ее по кличкам лошадей, чтобы узнать их выигрыши в течение 1938 г. Как и раньше, структура должна иметь формат в(Л,В,М, Б). Условие окончания поиска состоит в том, что кличка искомой лошади должна совпасть с Л. В этом случае поиск удачен и не требуется пробовать другие варианты. В противном случае мы должны использовать предикат меньше, определенный в гл. 3, чтобы определить, какую из «ветвей» дерева, М или Б, нужно рекурсивно просмотреть. Мы используем эти принципы при определении предиката искать, причем искать(Л,Т, Г) означает, что лошадь Л, если она найдена в таблице Т (которая организована в виде структуры формата в), выиграла Г гиней:

искать (Л, в(Л,Г,_,),Г):- !.

искать Л, в(Л1,_,До,_),Г):-меньше(Л,Л1),искать(Л,До,Г).

искать(Л, в(Л1,_,_,После),Г):- not (меньше(Л,Л1)), искать(Л,После,Г).

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

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

?- искать(ruby_vintage,S,X).

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

?- искать(abaris,X,582), искать(maloja,X,356).

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

Понять то, каким образом искать одновременно выполняет и создание и выборку компонент, можно на основе тех знаний о Прологе, которыми вы уже располагаете; мы настоятельно рекомендуем разобраться в этом самостоятельно. Подсказка: если искать(Л,Т, Г) используется в конъюнкции целей, то «изменения» в структуре Т сохраняются только в области определения Т.

Упражнение 7.1. Поэкспериментируйте с предикатом искать, чтобы установить, какие различия будут в словаре, если элементы в него вставлять каждый раз в разном порядке. Например, как будет выглядеть дерево словаря, если вставлять его элементы в таком порядке: massinga, braemar nettleweed, panorama? А если в таком порядке: adela, braemar, nettleweed, massinga?

7.2. Поиск в лабиринте

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

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

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

1. Подойти к двери какой-либо комнаты. Если номер комнаты есть в нашем списке, то перейти к шагу 1.

2. Если в поле зрения нет ни одной комнаты, то «вернуться назад» через ту комнату, через которую мы прошли сюда, и посмотреть, нет ли возле нее каких-либо других комнат.

3. Иначе дописать номер комнаты к нашему списку.

4. Поискать телефон в этой комнате.

5. Если телефона нет, то перейти к шагу 1. Иначе мы останавливаемся, и наш список содержит путь, который мы прошли, чтобы попасть в нужную комнату.

Будем считать, что номера комнат являются константами (безразлично целыми числами или атомами). Сначала мы можем решить, как просматривать номера комнат, записанные на листке бумаги. Для этого можно использовать предикат принадлежит, определенный в разд. 3.3, полагая, что содержимое листка бумаги представлено в виде списка. Теперь мы можем продвинуться в решении задачи поиска в лабиринте. Рассмотрим небольшой пример, где задан план дома, комнаты которого помечены буквами (см. рис. 7.2). Заметим, что просветы в стенах обозначают двери и что комната а – это просто представление пространства вне дома. Имеются двери, ведущие из а в b, из с в d, из f в е, и так далее. Сведения о том, где имеются двери, могут быть представлены в виде фактов Пролога:

д(а,b).

д(b,е).

д(b,с).

д(d,c).

д(c,d).

д(e,f).

д(g,e).

Рис. 7.2.

Заметим, что информация о наличии дверей не избыточна. Например, мы сказали, что имеется дверь, ведущая из комнаты g в комнату е, но не сказали, что имеется дверь, ведущая из комнаты е в комнату g, т. е. мы не зафиксировали утверждение д(e,g). Чтобы обойти эту проблему представления двухсторонних дверей, мы могли бы повторно записать д-факт для каждой двери с перестановкой аргументов. Или мы могли бы устроить программу таким образом, чтобы она понимала, что каждая дверь фактически может рассматриваться как двухсторонняя. Этот вариант мы и выбрали в нижеследующей программе.

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

• мы находимся в той комнате, которая нам нужна, или

• мы должны войти в дверь и распознать эти случаи снова (рекурсивно).

Рассмотрим целевое утверждение переход(X,Y,T), которое доказуемо (согласуется с базой данных), если можно перейти из комнаты X в комнату Y. Третий аргумент Т – это наш листок бумаги, который мы носим с собой и на котором записан перечень номеров комнат, в которых мы побывали до сего момента.

Граничное условие перехода из комнаты X в комнату Y состоит в том, что, возможно, мы уже находимся в комнате Y (т. е., возможно, X есть Y). Это условие представлено в виде утверждения:

переход(Х,Х,Т).

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