BFSを使用する場合、サイクルは関係ありません。アイデアは、現在の状態と先行ノードへのポインタを含む検索ノードを定義することです。したがって、受け入れ状態のノードにアクセスしたときに、前のポインタを逆方向にトレースして、受け入れられた文字列を逆順に判定することができます。検索ノードに前のノードの状態から現在のノードへの遷移を引き起こした文字も含まれているならば、エレガントであることが分かります。
ここでは、Javaのアプローチがあります：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
class Experimental {
// DFA state with its transitions, possibly accepting.
static class State {
final Map<Character, State> transitions = new HashMap<>();
final boolean accept;
State(boolean accept) {
this.accept = accept;
}
}
// A little DFA.
static final State s0 = new State(false);
static final State s1 = new State(false);
static final State s2 = new State(true);
static final State s3 = new State(true);
static {
s0.transitions.put('a', s1);
s0.transitions.put('b', s2);
s0.transitions.put('c', s3);
s1.transitions.put('d', s3);
s2.transitions.put('e', s0);
s2.transitions.put('f', s1);
}
// An enumerator of strings accepted by the DFA in order of length.
static class Enumerator {
static class Node {
final Node prev;
final char prevCh;
final State state;
Node(State start) {
this(null, Character.MIN_VALUE, start);
}
Node(Node prev, char ch, State state) {
this.prev = prev;
this.prevCh = ch;
this.state = state;
}
}
final Deque<Node> queue = new ArrayDeque<>();
final List<String> output = new ArrayList<>();
final State start;
Enumerator(State start) {
this.start = start;
}
Enumerator enumerate(int outputLimit) {
queue.clear();
output.clear();
// Enqueue a search node for the start state.
queue.add(new Node(start));
while (!queue.isEmpty() && output.size() < outputLimit) {
Node current = queue.pollFirst();
if (current.state.accept) {
// Follow prev pointers to build the accepted string.
StringBuilder sb = new StringBuilder();
for (Node p = current; p.prev != null; p = p.prev) {
sb.append(p.prevCh);
}
output.add(sb.reverse().toString());
}
// Enqueue nodes for the successors of current state.
for (Entry<Character, State> transition : current.state.transitions.entrySet()) {
queue.addLast(new Node(current, transition.getKey(), transition.getValue()));
}
}
return this;
}
}
public static void main(String[] args) {
System.out.println(new Enumerator(s0).enumerate(20).output);
}
}
出力：
[b, c, ad, beb, bec, bfd, bead, bebeb, bebec, bebfd, bebead, bebebeb, bebebec, bebebfd, bebebead, bebebebeb, bebebebec, bebebebfd, bebebebead, bebebebebeb]
は、あなたが任意のグラフアルゴリズムに精通していますか？グラフ検索/接続algoはここで便利です。 – djechlin
アルゴリズムは次のようなものですか？DFAの開始状態と受け入れ状態の間のすべてのパスを見つけるか？ –
@djechlin私はそうではありませんが、私が幸せになるような特定のアルゴリズムについて詳しく説明できれば、 –