Построение суперпозиции правил логического вывода/Решение — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «Матричный метод логического вывода предложен [http://scholar.google.ru/citations?user=kDy5GlMAAAAJ&hl=ru О.О. Варла…»)
 
 
Строка 6: Строка 6:
  
 
Если есть совпадение для $i$-го правила, то выходные значение этого правила $X_{out}^k$ полагаются известными и добавляются в маску:
 
Если есть совпадение для $i$-го правила, то выходные значение этого правила $X_{out}^k$ полагаются известными и добавляются в маску:
$Z' = Z \cup X_{out}^k$. Проход необходимо повторить, поскольку могли появиться правила, активируемые с помощью $Z'$.
+
$Z' = Z \cup X_{out}^k$, а номер правила заносится в список.  
 +
Проход необходимо повторить, поскольку могли появиться правила, активируемые с помощью $Z'$.
 
Проходы повторяются до тех пор, пока $Z'$ не перестанет изменяться или не будет получено $Z' \supset W$, что означает существование решения.
 
Проходы повторяются до тех пор, пока $Z'$ не перестанет изменяться или не будет получено $Z' \supset W$, что означает существование решения.
  
 
Поскольку количество проходов не превосходит количество параметров $n$, а на каждом проходе происходит не более $m$ операций сравнения, время работы алгоритма не превосходит $O(mn)$.
 
Поскольку количество проходов не превосходит количество параметров $n$, а на каждом проходе происходит не более $m$ операций сравнения, время работы алгоритма не превосходит $O(mn)$.
 +
Объём памяти, необходимый для хранения маски и списка применяемых правил не превосходит $O(m + n)$.
  
 
В книге описан способ улучшения алгоритма, который при выполнении предобработки за время $O(m \log m)$ работает не дольше $O(n+m)$.
 
В книге описан способ улучшения алгоритма, который при выполнении предобработки за время $O(m \log m)$ работает не дольше $O(n+m)$.
  
 
<\latex>
 
<\latex>

Текущая версия на 20:21, 28 декабря 2014

Матричный метод логического вывода предложен О.О. Варламовым. Алгоритм с иллюстрацией подробно описан в монографии "Эволюционные базы данных и знаний для адаптивного синтеза интеллектуальных систем. Миварное информационное пространство", стр. 180-186.