Алгоритм порождения подпроблем в глубину (НАЗАД)

Процедура УСТАНОВИТЬ_ФАКТ (ФАКТ)

1. если ФАКТ принадлежит БФ то возврат «успех»

2. возврат УСТАНОВИТЬ_1 (БП)

Процедура УСТАНОВИТЬ_1 (ПРАВИЛА)

1. если ПРАВИЛА пусто то возврат «неуспех»

2. ПРАВИЛО←выбор некоторого элемента из ПРАВИЛА (например первого)

3. ПРАВИЛА←ПРАВИЛА с удаленным ПРАВИЛО

4. если ПРАВИЛО содержит ФАКТ в действии то если УСТАНОВИТЬ_2 (ПРАВИЛО) = «успех» то возврат «успех»

5. возврат УСТАНОВИТЬ_1 (ПРАВИЛА)

Процедура УСТАНОВИТЬ_2 (ПРАВИЛО, ФАКТЫ)

1. ФАКТЫ←все факты составляющие условие ПРАВИЛО

2. возврат УСТАНОВИТЬ_КОНЬЮНКЦИЮ_ФАКТОВ (ФАКТЫ)

Процедура УСТАНОВИТЬ_КОНЬЮНКЦИЮ_ФАКТОВ(ФАКТЫ)

1. если ФАКТЫ пусто то возврат «успех»

2. ФАКТ1←выбор некоторого элемента из ФАКТЫ (например первого)

3. ФАКТЫ←ФАКТЫ с удалением ФАКТ1

4. если УСТАНОВИТЬ_ФАКТ (ФАКТ1) «неуспех» то возврат «неуспех»

5. возврат УСТАНОВИТЬ_КОНЬЮНКЦИЮ_ФАКТОВ(ФАКТЫ)

Запускают этот алгоритм, вызывая одну за другой процедуры УСТАНОВИТЬ_ФАКТ или УСТАНОВИТЬ_КОНЬЮНКЦИЮ_ФАКТОВ.

Пример

Для установления факта Q воспользуемся вызовом УСТАНОВИТЬ_ФАКТ(Q). Алгоритм НАЗАД просматривает правила и находит среди них то, действие которого равно Q, т.е. правило 2. Для установления факта Q требуется установить факты I, L, J, т.е. Q заменяется на I, L, J. Факты I, L, J называются подпроблемами Q, а Q - отцом проблем I, L, J. Заметим, что алгоритм постоянно поддерживает множество проблем, которые нужно установить.

Далее требуется установить факт I, для чего отыскивается правило 1 с действием I, в результате раскрытия которого факт I заменяется на K, L, M. Факт K уже установлен в БФ, в то время как факты L и M отсутствуют в качестве действия в правилах. Таким образом, требуется восстановить факт I, и поскольку не одно из правил не содержит действие I, то нужно восстановить и факт Q. Далее раскрывается правило 4, содержащие действие Q, в результате чего Q заменяется на A и B. Поскольку факт A уже имеется в БФ, то требуется установить факт B. Раскрытие правила 3, которое содержит действие B, заменяет B на C, D, E, которые уже имеются в БФ. Таким образом, факт B а затем факт Q установлены.

Раскрытие правила в алгоритме ведет к замене факта, который нужно установить, несколькими новыми фактами, требующими доказательства их истинности. Например, факт Q заменяется фактами L,N,O,P в правиле 5. Некоторые из новых фактов оказываются установленными в БФ, а другие требуется установить. Таким образом, существуют явные факты (БФ) и неявные, требующие установления путем вызова процедур.

Процесс установления факта Q можно представить в виде графа (рис. 11.4)

На рис. 11.5. представлен граф состояния раскрытия правил с целью установления факта Q с помощью алгоритма НАЗАД. Правая часть каждого состояния соответствует явной части БФ, в то время как левая – неявной части, содержащей факты, которые требуются установить.

По отношению к базовому циклу работы машины вывода этап ОГРАНИЧЕНИЕ в алгоритме НАЗАД состоит, с одной стороны, в указании проблемы, которую нужно рассмотреть в этом цикле, а с другой, в ограничении множества правил, которые требуется обработать (инструкция 3 процедуры УСТАНОВИТЬ_1). Проблема для установления берется среди проблем, порожденных предыдущим циклом (инструкция 2 процедуры УСТАНОВИТЬ_КОНЬЮНКЦИЮ_ФАКТОВ). При этом могут иметь место следующие случаи: все проблемы, появившиеся в предыдущем цикле, установлены (возвращается сообщение «успех» инструкциями 1, а затем 5 процедуры УСТАНОВИТЬ_КОНЬЮНКЦИЮ_ФАКТОВ); проблема, порожденная предыдущим циклом, не может быть установлена (выход из процедуры УСТАНОВИТЬ_ КОНЬЮНКЦИЮ_ФАКТОВ по инструкции 4).

В обоих случаях этап ОГРАНИЧЕНИЕ предлагает проблему, порожденную непосредственно предыдущим циклом.

Алгоритм НАЗАД останавливается либо в том случае, когда все исходные проблемы установлены, либо потому что одна из них не может быть установлена. Заметим, что представленный здесь алгоритм может не остановиться, например, при добавлении в БП правила 10: Q®L. [1]