Управление поиском в системе MBASE
Один из распространенных способов управления поиском в применении к доказательству какого-либо утверждения – тщательное упорядочение базы данных. При поиске нужных фактов или правил исполнительная система языка PROLOG просматривает базу данных от начала до конца. Используя это обстоятельство, можно несколько сократить время доказательства.
- Определенные факты (основные атомы – ground atoms) нужно разместить в базе данных раньше, чем правила, которые в качестве цели имеют соответствующие предикаты. Таким образом будут минимизированы издержки обращения к правилам.
Например, утверждение:
beats(achilles, zeno).
Должно стоять раньше правила:
beats(X, Y): – beats(X, Z), beats(Z, Y).
- Исключения из общих правил также должны располагаться в базе данных раньше, чем сами общие правила.
Например, правило, утверждающее, что пингвины не летают:
flies(X): – penguin(X),!, fail.
Должно стоять раньше общего правила, гласящего, что птицы летают:
flies(X): – bird(X).
Литерал fail представляет собой один из способов выражения отрицания в языке PROLOG. Кроме того, в языке PROLOG имеется литерал!, который называется "отсечением". Этот литерал говорит исполнительной системе PROLOG, что не нужно осуществлять возврат из этой точки. Комбинация литералов представляет эффективный механизм управления обратным просмотром, предотвращая выполнение ненужных операций.
- Предположения по умолчанию реализуются включением неосновных атомов в самый конец базы знаний.
Например, если желательно, чтобы по умолчанию квакеры считались пацифистами, то фраза:
pacifist(X): – quaker(X).
Должна появиться после всех фраз вида:
pacifist(nixon):-!, fail.
В случае, если при просмотре базы знаний не будет найдено утверждение об обратном, касающееся конкретного квакера, то на него распространится утверждение, справедливое для всех остальных.
Общее правило гласит, что сначала в базе данных следует располагать данные об особых случаях, т.е. определенные факты и исключения, затем данные об общих случаях, например правила влияния, и последними должны располагаться сведения о свойствах по умолчанию.
Все эти требования соблюдены в системе MBASE, но, кроме того, еще существует и возможность управления глубиной поиска. В этой системе существуют литералы, задающие один из трех имеющихся режимов поиска.
- Обращение к базе данных (DBC – database call). Этот режим ограничивает зону поиска только основными литералами в базе данных и таким образом исключает применение правил. Для настройки этого режима нужно включить основной литерал в предикат ВВС.
Например, факт, что b1 является блоком, будет представлен фразой:
DBC(block(b1)).
Тогда для некоторой фразы Р при обработке подцелей в форме DBC (Р) будет просматриваться только указанная часть базы данных.
Описанная выше комбинация литералов отсечения и неудачи также может использоваться в сочетании с предикатом DBC. Таким образом, формируется своего рода "ловушка", прекращающая поиск цели, которая не может быть найдена. Например, можно таким способом прекратить попытки доказать, что блок одновременно находится в двух местах:
at(Block, Placel):- DEC(at(Block, Place2)), different(Placel, Place2),!, fail.