DFA의 노드를 저장할 데이터 구조

Question

특정 조건을 만족하는 노드를 찾는 것이 빠른 (로그)이되도록 유한 결정 성 오토 마톤의 노드를 저장하는 데이터 구조가 필요합니다. 문제의 조건은 다음과 같다 :

나는 노드 p를 가지고 있고, 나는 노드 q 같은 것을 찾을 수있다 : (p ∈ F ≡ q ∈ F) & (∀ a : a ∈ Σ : δ(p,a) = δ(q,a))합니다. 즉, p 및 q은 모두 final이거나 둘 다 아니며 동일한 노드로 전환됩니다.

나는 느릴 수 있기 때문에 모든 노드를 통과하고 싶지 않습니다. 분명히, q에 전환이있는 알파벳 문자 집합이 p에 전환이있는 집합과 다른 경우 q은 내가 찾고있는 노드가 아닙니다.

p과 q의 전환 수가 다른 경우 q은 내가 원하는 노드가 아닙니다. 그래서 노드의 최종성과 전환 수에 따라 노드를 정렬하는 데이터 구조를 생각했습니다. 그래서 모든 노드를 살펴볼 필요가 없습니다. 최종 노드가 동일하고 전환 수가 동일해야합니다. 그러나 그것은 여전히 ​​대수적이지 않습니다. 어떤 아이디어.

저는 C++을 사용하고 있습니다.

Answer 1

나는 각 노드에 대해 문자열을 구성했으며이 문자열을 AVL 트리에 넣었습니다. 해시 함수와 정렬되지 않은 맵을 사용하는 솔루션보다 더 빨리 실행되고 훨씬 적은 메모리가 사용되었습니다.

다음 노드를 나타내는 문자열 보인다 :이 노드가 최종인지에 따라, 0 또는 1로 시작 여부 다음 쌍 (a,n) 다음과 같이 코딩된다 : a이 위치에 대응하는 int 인 알파벳 a은 알파벳이고 n은 또 다른 int이며, 심볼이 a 인 것으로 전환 된 노드의 색인입니다.

Answer 2

는 노드 q에서 정보의 두 종류가있다 :

• 부울 정보 (q ∈ F)
• 쌍 목록 (a,n)되도록 캐릭터 δ (Q, a) == N (즉, 목록/목적지 노드 쌍은 q에서 도달 가능)

이 두 가지 정보 (부울 및 쌍 목록)는 단일 시퀀스로 표시 할 수 있으며이 경우 해시 키를 계산할 수 있습니다 기다림.

이렇게하면 관심있는 속성으로 노드를 해시 할 수 있습니다. 주어진 노드 에 대해 후보 노드 q을 검색하면 O (1)에 가까워집니다.

(코멘트에서 언급 한 최소화 알고리즘의 경우 반복 중에 수행 된 작업의 결과로 쌍의 대상 노드 포인터가 변경되므로이 반복을 다시 작성해야합니다.)