動的グラフ プログラミング

Error

動的計画法を使用したソリューションでは、ダイナミクスを計算する順序が重要です (現在の値が依存する値が前に計算されている必要があります)。
したがって、有向非巡回グラフで動的プログラミングを使用する必要がある場合は、最初にグラフのトポロジカル ソートを構築する必要があります。次に、構築されたトポロジー ソートの順序で頂点をソートしてダイナミクスを計算します (問題に応じて、走査順序はソースからシンクへ、またはその逆になります)。
 
 

グラフにサイクルが含まれている場合 (トポロジカルな並べ替えがない場合)、次の 2 つのトリックが役に立ちます。

1) ダイナミクスを n 回計算します。ここで、n はグラフ内の頂点の数です (Ford-Bellman アルゴリズムとの類推による)。しかし、これでは漸近線が大きくなり、一般に効率的になることはほとんどありません。

2) グラフの圧縮を構築します。元のグラフの強連結成分ごとに、問題を個別に解決します。凝縮されたグラフは非巡回であり、その場合、頂点値として、強く接続されたコンポーネントの計算値を使用しながら、トポロジカル ソートによる標準的なアプローチを使用できます。この方法が主に使われます。