3

各ノードが状態で表される有向非巡回グラフがあります

public class State{
   List<State> ForwardStates;
   string stateName;
}

ここForwardStatesで、は現在の状態からの次の状態のリストです。

私には2つの特別な状態があります

State initialState (name=initial)
State finalState (name=final)

初期状態から最終状態までのすべてのパスを検索し、

List<List<string>> paths

たとえば、次のようなグラフがあるとします

ここに画像の説明を入力してください

paths値{{"initial"、 "a"、 "final"}、{"initial"、 "b"、"final"}}が含まれている必要があります

再帰なしでC＃でこれを簡単に達成するにはどうすればよいですか（グラフが大きくなる可能性があるため）？

4

2 に答える 2

2

アルゴリズムは次のようになります。

  • のキューを作成しますTuple<State, List<String>>。
  • エンキュー{ InitialState, new List<string> { InitialState.Name } }
  • キューにアイテムがある間、
    • 最初のアイテムをデキューする
    • dequeued 状態のすべての非 final forward 状態について、enqueue { ForwardState, DequeuedList.ToList().Add(ForwardState.Name) }
    • 最終状態が前方状態の場合DequeuedList.ToList().Add(FinalState.Name)、出力リストに追加します。

空のキューと、必要に応じて文字列のリストのリストになるはずです。

于 2013-01-31T17:47:42.413 に答える
1

コメントをありがとう、私もここで提案を使用します https://stackoverflow.com/a/9535898/1497720 （重要なポイントはBFS / DFS中に訪問済み状態を使用していません）

これは、訪問済み状態のないDFSを使用したバージョンです。

 List<List<string>> paths= new List<List<string>>();
            Stack<Tuple<State, List<string>>> working = new Stack<Tuple<State, List<string>>>();
            working.Push(new Tuple<State,
                List<string>>(initialNode,
                new List<string> { initialNode.stateName }));
            do
            {
                Tuple<State, List<string>> curr = working.Pop();


                if (currNexts.stateName == "final")
                {
                    res.Add(curr.Item2);
                }
                else
                {
                    foreach (State currNext in curr.Item1.ForwardStates)
                    {
                        working.Push(new Tuple<State,
                        List<string>>(rnext, curr.Item2.Union(new[] { rnext.stateName }).ToList()));
                    }
                }
            } while (working.Count != 0);
于 2013-02-01T03:12:58.723 に答える