Главная arrow Логика arrow Избыточный логический вывод
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Избыточный логический вывод Печать

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

path(X,Z) :- link(X,Z).

path(X,Z) :-path(X,Y), link(Y,Z).

На рисунке а) приведен простой граф, состоящий из трех узлов, который описан с помощью фактов link (а, Ь) и link (Ь, с). При использовании этой программы запрос path (а, с) вырабатывает дерево доказательства, показанное на рисунке а). С другой стороны, если эти два выражения расположены в таком порядке:

path(X,Z) :-path(X,Y), link(Y, Z).

path(X,Z) :- link(X, Z).

то система Prolog следует по бесконечному пути, как показано на рисунке б). Поэтому система Prolog является неполной, как и программа автоматического доказательства теоремы для определенных выражений (как показано в этом примере, даже применительно к программам, соответствующим формату языка Datalog), поскольку для некоторых баз знаний эта система оказывается неспособной доказать высказывания, которые из них следуют. Следует отметить, что алгоритм прямого логического вывода не подвержен этой проблеме: сразу после вывода фактов path (а, b), path(b,с) и path (а, с) процесс прямого логического вывода останавливается.

Обратный логический вывод с поиском в глубину сталкивается также с проблемами, обусловленными излишними вычислениями. Например, при поиске пути от узла А1 к узлу J4 на рисунке б) система Prolog выполняет 877 этапов логического вывода, большинство из которых связано с поиском всех возможных путей к узлам, не   позволяющим достичь цели. Такая проблема аналогична проблеме повторяющихся состояний. Общее количество этапов логического вывода может определяться экспоненциальной зависимостью от количества базовых фактов, вырабатываемых в процессе вывода. А если бы вместо этого применялся прямой логический вывод, то можно было бы ограничиться выработкой, самое большее, n2 фактов path (X, Y), связывающих п узлов. При этом для решения задачи, приведенной на рисунке б), потребовалось бы только 62 этапа логического вывода.

Иллюстрация недостатков языка Prolog: поиск пути от А до Сможет привести систему Prolog к созданию бесконечного цикла (а); граф, в котором каждый узел связан с двумя случайно выбираемыми преемниками на следующем уровне; для поиска пути от A1 до J4 требуется 877этапов логического вывода (б)

Image

Иллюстрация того, что работа программы Prolog зависит от расположения взаимосвязанных выражений: успешное доказательство того, что путь от А до С существует (а); бесконечное дерево доказательства, формируемое из-за того, что выражения находятся в "неправильном " порядке (б)

Image

Применение прямого логического вывода при решении задач поиска в графе представляет собой пример динамического программирования, в котором решения подзадач формируются инкрементно из решений меньших подзадач и кэшируются для предотвращения повторного вычисления. Аналогичный эффект в системе обратного логического вывода может быть достигнут с помощью запоминания (memoization), т.е. кэширования решений, найденных для подцелей, по мере их обнаружения, а затем повторного применения этих решений после очередного появления той же подцели, вместо повторения предыдущих вычислений. Этот подход применяется в системах табулированного логического программирования (tabled logic programming), в которых для реализации метода запоминания используются эффективные механизмы сохранения и выборки. В табулированном логическом программировании объединяется целенаправленность обратного логического вывода с эффективностью динамического программирования, присущей прямому логическому выводу. Кроме того, эти системы являются полными применительно к программам в формате Datalog, а это означает, что программисту приходится меньше беспокоиться о бесконечных циклах.