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

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

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в наш список. Все это выражается в виде следующего утверждения:

переход(Х, Y,T,):- Д(Х,Z),not(принадлежит(Z,Т)), переход(Z,Y,[Z|T]).

Словами это может быть выражено так: для того чтобы «перейти» из Xв Y, не проходя через комнаты из списка Т, надо найти дверь из Xкуда-либо (т. е. в Z), убедиться, что Zеще не занесена в список Т, и «перейти» из Zв Y, используя список Тс дописанной в него Z.

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

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

переход(Х,X,T).

переход(X,Y,T):- д(X,Z), not(принадлежит(Z,Т)),переход(Z,Y[Z|T]). переход(Х,Y,T):- д(Z,Х), not(принадлежит(Z,Т)),пeреход(Z,Y,[Z|T]).

Или, используя предикат ';' (обозначающий дизъюнкцию), можно записать:

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

переход(Х,Y,T):- (д(Х,Z); д(Z,Х)), not(принадлежит (Z,T)),пepexод(Z,Y,[Z|T]).

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

?- переход(а,Х,[]), есть_телефон(X).

Это – вопрос типа «создать и проверить», который находит достижимые комнаты и затем проверяет наличие в них телефона. Другой способ – это найти сопоставление сначала для предиката есть_телефон(Х), а затем попробовать перейти из комнаты ав X:

?- есть_телефон(Х), переход(а,Х,[]).

Последний метод более эффективен, однако он подразумевает что мы «знаем», где телефон, еще до того, как начали поиск.