Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Rete

эффективный алгоритм сопоставления с образцом для продукционных систем, экспертных систем и баз знаний, созданный Чарльзом Форги из Университета Карнеги Меллона. Впервые был описан в рабочем документе 1974 года, затем в докторской диссертации 1979 и в статье 1982 года. Rete стал основой многих популярных экспертных систем, включая CLIPS, Jess, Drools, BizTalk Rules Engine and Soar. Слово 'rete' на латыни означает 'сеть', а в современном итальянском 'связи'. Произносится как 'рити', в академической среде 'рейти', что ближе к современному итальянскому произношению. Другие варианты 'рит' и, редко, 'ретэ'.

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

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