Подстановка переменных при сопоставлении с образцом? - PullRequest
Новая
       14

Подстановка переменных при сопоставлении с образцом?

1 голос
/ 11 июня 2009

Я разрабатываю механизм логического вывода, это означает, что в основном у меня есть определенное количество «фактов», которые в основном представляют мир в определенный момент. Вместе с фактами (которых обычно только два, начальное состояние и целевое состояние) у меня есть много правил (буквально сотни для определенных проблем). Цель механизма логического вывода - с учетом начального состояния и набора правил найти кратчайший путь к одному из приемлемых целевых состояний. Это можно сделать с помощью нескольких алгоритмов, таких как DFS, BFS или A *. Основная структура программы: 

fact factname
  attribute1 = "value";
  attribute2 = [ 1, 2, 3];
  attribute3 = 4;
  attribute4 = 7;
  ...
endFact

rule ruleOne
  equalsto(attribute, "value") or
  greaterthan(attribute, 5)
  >
  remove(attribute);
endRule

rule ruleTwo
  isprimeinteger(attribute)
  >
  add(attribute, 1)
endRule

В правиле LHS (часть перед>) соответствует каждому атрибуту в факте factname, который равен «значению». В этом случае это только один, но может быть много. Это означает, что мне нужно разрешить переменные (часто несколько раз для одного и того же факта), и в LHS правила могут быть введены несколько условий и / или с правильным анализом приоритета.

Проблема в том, есть ли способ разрешить переменные такого типа эффективно ? Что я делаю сейчас, так это перебираю каждый атрибут в факте, и в основном я генерирую довольно большое n-арное дерево, которое даже не сбалансировано, и это ОЧЕНЬ медленно, особенно с учетом вышеуказанных условий.

Я бы хотел, чтобы указатели на документы соответствовали этому шаблону

Ответы [ 3 ]

2 голосов
/ 11 июня 2009

Я заметил, что вы не использовали слово унификация где-либо в вашем сообщении. Это то, что алгоритм, который вы пытаетесь реализовать, обычно называется. Ознакомьтесь со статьей Wikipedia ; внизу есть несколько ссылок, в том числе одна из 70-х, когда пространство и циклы имели значение.

0 голосов
/ 12 июня 2009

у Эдуффи есть это: это называется объединением. Prolog - это язык программирования, предназначенный для выполнения именно того, что вы пытаетесь сделать, в общем случае, и он использует унификацию для выполнения своей грязной работы.

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

0 голосов
/ 11 июня 2009

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

...