Алгоритмы сопоставления с образцом

Во всех алгоритмах поиска ключевую роль играет проверка применимости правила, т. е. того, что выполнено условие р проверяемого правила при данном состоянии базы фактов D. Из соображений здравого смысла разумно предположить, что имеют место два обстоятельства.

• • Во-первых, в типичной системе продукций в каждом отдельном состоянии d большая часть правил не применима. Действительно, если бы это было не так, например, если бы в любом состоянии любое правило было бы применимо, то система продукций просто наудачу применяла бы действия для изменения базы фактов в надежде случайно наткнуться на решение^[1][2]. Заметим, что из этого обстоятельства следует вывод, что большую часть усилий система продукций тратит на проверку условий, которые не ведут к цели.
• • Во-вторых, в типичной системе продукций в условиях различных правил часто используются одни и те же факты, возможно, связанные разными логическими связками. Действительно, если бы эго было не гак, например, если бы все условия всех правил были бы независимы, то это была бы не система продукций, а тривиальная программа, составленная из длинного условного оператора:

if p₁ then f_l else if p₂ then f₂ else if … fi.

В таком случае никакого поиска решения и не нужно, поскольку есть готовый алгоритм. Заметим, что из этого обстоятельства следует вывод, что при проверке условий одни и те же факты проверяются многократно.

С учетом этих наблюдений были разработаны эффективные алгоритмы реализации функции Select, которые позволяют выбирать правило намного быстрее, чем это делается в изложенном выше алгоритме А*. Эти алгоритмы опираются на применение специальных структур данных для представления продукционных правил.

• [1] Конечно, при игре в восемь правила не могут меняться при движении шашек. Но приуправлении войсками противник вполне может изменить свою тактику и стратегию по ходубоевых действий, например, введя в сражение новый вид оружия.
• [2] Такое поведение, увы, не редкость в жизни, но его нельзя квалифицировать как искусственно или ествественно интеллектуальное.