与えられた: ノードが複数の親を持つことができる、重み付けされたエッジを持つ有向非巡回グラフ。
問題: ルート ノードの各子について、そのような子から到達可能なリーフまでの最小コスト (重みの合計) パスを見つけます。ノードは、そのような最小コスト パスの 1 つにのみ存在できます。
グラフの例:
上記のグラフでは、ノード 2 で使用可能なすべてのパスは次のとおりです。
2 -> 5
2 -> 1 -> 9 -> 6
2 -> 1 -> 10 -> 6
Among which 2 -> 1 -> 10 -> 6 has minimum cost of 3.5
同様に、ノード 4 の場合、使用可能なすべてのパスは次のとおりです。
4 -> 11 -> 8
4 -> 7 -> 10 -> 6
Among which 4 -> 7 -> 10 -> 6 has minimum cost of 3.0
現在の結果は次のとおりです。
For node 2, the path is 2 -> 1 -> 10 -> 6 : Cost 3.5
For node 4, the path is 4 -> 7 -> 10 -> 6 : Cost 3.0
For node 3, there is no such path.
これを行うコードを書きました。ここで、そのような最小コスト パスに共通のノードがない場合、アルゴリズムは停止し、ルート ノードのすべての子の最小コスト パスが返されます。
ただし、共通のノードが存在する場合は、そのうちの 1 つだけに保持する必要があります。その理由は、通常、このような複数の親ノードはノイズの多いデータによるものです。ノードは、1 つの親のみに属すると想定されています。そのようなノードを最小コストのパスに保持しようとしています。したがって、ここでは、ノード 10 は、コストが 3.5 のノード 2 の最小パスと比較して、コストが 3.0 のノード 4 の最小パスに属しています。ノード6でも同じロジック。したがって、コストを比較して、いくつかの複数の親ノードの関連付けを解除します。関連付けを解除しても、エッジが削除されるわけではありません。ノードのデータ構造内の各ノードに最適な親を保存するだけです。たとえば、ノード 10 には「最適な親はノード 7」というエントリがあり、ノード 6 には「最適な親はノード 10」というエントリがあります。
したがって、ロジックは次のようになります。
Do:
For each child node of the root:
Find out min-cost path. Store that path and the cost.
If conflicting paths exist:
Compare the costs of conflicting paths and save "best parent" for each node.
While there were conflicting paths;
質問:
このロジックは理にかなっていますか？競合を排除するこの反復的な方法は、一部のグラフでは収束しないのではないかと心配しています。たとえば、ノード 2 の最小パスを再計算しているときに、現在 2 -> 5 が最小パスであることが判明し、最初の反復中にノード 5 が他のノードの最小パスで使用されていると仮定すると、ノード 5 の「最適な親」をノード 2 として再割り当てし、再度繰り返す必要があります。簡単に言えば、あるノードの最小パスを修正しようとするたびに、他のノードを変更する可能性があります。そのようなアルゴリズムは何らかの解に収束できるでしょうか? はいの場合、その複雑さはどうなりますか?
そもそも最小コスト パスを計算する前に、このような競合を排除する方法はありますか?