패턴 일치에서 변수 대체?

Question

저는 추론 엔진을 개발하고 있습니다. 이것은 기본적으로 특정 순간에 기본적으로 세계를 대표하는 "사실"을 가지고 있음을 의미합니다. 사실 (보통 2 개, 시작 상태와 목표 상태)과 함께 나는 많은 규칙 (특정 문제에 대해 말 그대로 수백 개가 될 수 있음)이 있습니다. 추론 엔진의 목적은 시작 상태와 일련의 규칙을 고려하여 허용 가능한 목표 상태 중 하나에 대한 최단 경로를 찾는 것입니다. 이것은 DFS, BFS 또는 A *와 같은 여러 알고리즘을 사용하여 수행 할 수 있습니다. 프로그램의 기본 구조이다 : ((가)> 부분 전에) "값"같다 사실 factname에서 모든 속성과 일치

규칙에

 
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. 이 경우에는 하나 뿐이지 만 많은 경우가있을 수 있습니다. 이것은 변수를 분석해야한다는 것을 의미하며 (종종 동일한 사실에 대해 여러 번) 규칙의 LHS에 여러 조건을 넣거나 올바른 우선 순위 구문 분석을 할 수 있습니다.

문제는 다음과 같습니다.이 종류의 변수를 해결할 수있는 방법이 있습니까 ? 제가 지금하고있는 일은 사실에있는 모든 속성을 반복하는 것입니다. 기본적으로 저는 불균형 한 꽤 큰 n-ary tree를 생성하고 있습니다. 이것은 특히 위의 조건에서 보면 매우 느립니다.

나는 간단한 해시 테이블 O 될 경우, 당신은 O (N) 알고리즘을 사용하고

Answer 1

여기 아니 놀랍게도 일치하는 패턴 이런 종류의 논문 사랑 포인터를 거라고 (1). 해시 테이블은 각 속성 값에 대해 해당 속성을 저장합니다.

Answer 2

내가 통일이라는 단어를 게시물에 사용하지 않은 것으로 나타났습니다. 이것이 구현하려는 알고리즘이 일반적으로 호출되는 것입니다. Wikipedia 기사를 확인하십시오. 바닥에 몇 가지 참조 사항이 있습니다. 우주와 사이클이 중요했던 70 년대의 것을 포함하여.

Answer 3

eduffy has it : 통일이라고합니다. Prolog는 일반적인 경우에 수행하려는 작업을 정확하게 수행하도록 설계된 프로그래밍 언어이며 통일을 사용하여 더러운 작업을 수행합니다.

그러나 Prolog에서 Peano axioms를 사용하여 산술 연산을 구현하려는 사람이라면 항상 가능한 가장 빠른 방법이있는 것은 아니라고 말할 수 있습니다. 대략적으로 동일한 작업을 수행하지만 가능한 한 빨리 최적의 솔루션을 찾는 데 도움이되는 휴리스틱을 제공하는 데 중점을 둔 "제약 프로그래밍"언어가 있습니다. 그 중 하나가 Comet입니다.