Избыточный логический вывод и бесконечные циклы
Теперь рассмотрим, в чем состоит ахиллесова пята языка Prolog: несогласованность между организацией поиска в глубину и деревьями поиска, которые включают повторяющиеся состояния и бесконечные пути. Рассмотрим следующую логическую программу, позволяющую определить, существует ли путь между двумя точками в ориентированном графе:
path(X,Z) :- link(X,Z).
path(X,Z) :-path(X,Y), link(Y,Z).
На рис. 9.5, а приведен простой граф, состоящий из трех узлов, который описан с помощью фактов link (а, Ь) и link (b, с). При использовании этой программы запрос path (а, с) вырабатывает дерево доказательства, показанное на рис. 9.6, а. С другой стороны, если эти два выражения расположены в таком порядке:
path(X,Z) :-path(X,Y), link(Y,Z). path(X, Z) :- link(X, Z) .
то система Prolog следует по бесконечному пути, как показано на рис. 9.6, б. Поэтому система Prolog является неполной, как и программа автоматического доказательства теоремы для определенных выражений (как показано в этом примере, даже применительно к программам, соответствующим формату языка Datalog), поскольку для некоторых баз знаний эта система оказывается неспособной доказать высказывания, которые из них следуют. Следует отметить, что алгоритм прямого логического вывода не подвержен этой проблеме: сразу после вывода фактов path (а, Ь), path (b, с) и path (а, с) процесс прямого логического вывода останавливается.
Обратный логический вывод с поиском в глубину сталкивается также с проблемами, обусловленными излишними вычислениями. Например, при поиске пути от узла А± к узлу J4 на рис. 9.5, б система Prolog выполняет 877 этапов логического вывода, большинство из которых связано с поиском всех возможных путей к узлам, не позволяющим достичь цели. Такая проблема аналогична проблеме повторяющихся состояний, которая описывалась в главе 3. Общее количество этапов логического вывода может определяться экспоненциальной зависимостью от количества базовых фактов, вырабатываемых в процессе вывода. А если бы вместо этого применялся прямой логический вывод, то можно было бы ограничиться выработкой, самое большее, п2 фактов path (X, Y), связывающих п узлов. При этом для решения задачи, приведенной на рис. 9.5, б, потребовалось бы только 62 этапа логического вывода.
Применение прямого логического вывода при решении задач поиска в графе представляет собой пример динамического программирования, в котором решения подзадач формируются инкрементно из решений меньших подзадач и кэшируются для предотвращения повторного вычисления. Аналогичный эффект в системе обратного логического вывода может быть достигнут с помощью запоминания (memoization), т.е. кэширования решений, найденных для подцелей, по мере их обнаружения, а затем повторного применения этих решений после очередного появления той же подцели, вместо повторения предыдущих вычислений. Этот подход применяется в системах табулированного логического программирования (tabled logic programming), в которых для реализации метода запоминания используются эффективные механизмы сохранения и выборки. В табулированном логическом программировании объединяется целенаправленность обратного логического вывода с эффективностью динамического программирования, присущей прямому логическому выводу. Кроме того, эти системы являются полными применительно к программам в формате Datalog, а это означает, что программисту приходится меньше беспокоиться о бесконечных циклах.