2

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

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

ここForwardStatesで、現在の状態からの前方リンクによる状態のリストです。現在のbackStates状態からの逆方向リンクによる状態のリストです。

私は2つの特別な状態を持っています

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

初期状態から最終状態までのすべてのパスを見つけて、

List<List<string>> paths

たとえば、次のようなグラフが与えられた場合

ここに画像の説明を入力

後方リンクが茶色の点線矢印で表され、前方リンクが黒いコンクリート矢印で表される場合、可能なパスは {{initial, b, a, final},{initial, c, final},{initial, b, initial,final }}

ルールとしては、初期状態から1つ以上の後方リンクを経てから前方リンクを通過し、前方リンクに切り替わると前方リンクを使い続ける（つまり、後方リンクを使用できなくなる）というルールです。 ）。

この質問は、この質問 ( DAG のすべてのパスを収集する) の拡張です。

4

1 に答える 1

2

後方リンクのみを使用するグラフを使用して、初期状態からDFSを実行します。このDFS（initialStateを除く）中に検出された各ノードから、ターゲットへのパスが見つかるまで（転送リンクのみを使用して）別のDFSを実行します。

u後方リンクでのDFS中に検出したノードごとに、パスは次のようになります。

path(initialState,u) ; path(u,finalState)

path(u,v)このステップに関連するDFSによって検出されたパスは どこにありますか。
これは、特定のパスで複数回呼び出される可能性があることに注意してください。これは、必要なパスが異なるため、からをu見つけたパスごとに呼び出すことができます。initialStateu

パスの数だけが必要な場合は、トポロジカルソートとDPを使用してより速く解決できますが、ここではそうではありません。

于 2013-02-01T18:36:48.330 に答える