Стратегии поиска (перебора) для управления работой интеллектуальной системы.

В соответствии с общей процедурой главная задача стратегии управления – это выбор применимого правила для использования на шаге 3, а для разложимых систем продукции в выборе очередной составляющей базы данных для обработки на шаге 4 и выбор применимого правила на шаге 6.

Другими вспомогательными, но важными задачами стратегии управления являются: проверка применимости правил, проверка соответствия глобальной базы данных к терминальному условию и запоминание результата. Общая «стоимость» вычислений в системе продукций искусственного интеллекта складывается из «стоимости» применения правил с одной стороны и «стоимости» стратегии управления с другой. Кроме того, важной характеристикой системы продукций является объем информации о возможных путях решения задачи.

Умение проектировать эффективные интеллектуальные системы состоит, отчасти, в установлении пропорции между этими двумя «стоимостями». Для любой конкретной задачи оптимальную эффективность можно получить при стратегии управления, полностью не обладающей полной информацией.

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

Стоимость вычислений в системах продукции искусственного интеллекта

стоимость вычислений

Полная стоимость

Стоимость применения правил продукции

Стоимость стратегии управления

0 информированность полная

Рисунок3.1

1. Стратегия управления с возвращением

Основная процедура поиска с возвращением имеет вид:

Recursive procedure

BACKTRACK (DATALIST)

1. DATA FIRST (DATALIST)

2. If MEMBER (DATA, TAIL (DATALIST))

returnFAIL

неудача, если процедура приходит к уже встречавшейся ранее базе данных

3. IfTERM(DATA)

returnNIL

проверка, удовлетворяет ли база данных терминальному условию

4. If DEADEND (DATA)

return FAIL

5. If LENGTH (DATALIST) > BOUND

returnFAIL

если длина списка превышает некоторое ограниченное значение, то процедура сообщает о неудаче

6. RULES APPRULES (DATA)

7. LOOP: if NULL (RULES)

returnFAIL

если нет применимого правила, процедура возвращает неудачу

8. R FIRST(RULES)

выбирается наилучшее из применимых правил

9. RULES TAIL (RULES)

выбранное правило удаляется из списка

9. RDATA R (DATA)

применяем к базе данных правило Rи порождаем новую базу данных

9. RDATALIST CONS (RDATA, DATALIST)

к списку баз данных, встречавшихся ранее, добавляется новая база данных

9. PATH BACKTRACK (RDATALIST)

рекурсивный вызов

9. If PATH = FAIL, goto LOOP

10. return CONS (R, PATH)

возвращается список правил, начинающийся с некоторого правила Rи обеспечивающий верное решение

Применим эту процедуру для игры в «восемь»:

3	7	1
4	2	5
8	0	6

Исходная база данных

1	2	3
8	0	4
7	6	5

База данных, удовлетворяющая терминальному условию.

Список правил: П1

П2

П3

П4

П3П4П1 – RULES(список)

Затем выбираем П3 и исключаем его из списка:

3	7	1
4	2	5
0	8	6

Формируется база данных RDATA

П1П4 – новый список RULES.

Выбираем и применяем новое правило, П1 удаляется из списка.

3	7	1
0	2	5
4	8	6

П4

П2П1П4 – новый список RULES.

Выбираем правило П2 и удаляем его из списка

3	7	1
4	2	5
0	8	6

П1П4 – новый список RULES.

Таким образом, произошел возврат на верхний уровень.

На пятом шаге снова вызывается процедура BACKTRACK.

Описанная выше процедура при неудаче каждый раз возвращается на один уровень, т.е. если рекурсивный вызов BACKTRACKn-го уровня терпит неудачу, управление передается к (n-1) уровню, где пробуется другое правило. Однако, иногда неудача наnуровне связана с выбором правила, сделанном на много уровней выше. Тогда бесполезно выбрать новое правило на (n-1) уровне и требуется найти способ перепрыгнуть на несколько уровней вверх.