この分野の「先行技術」についてはよくわかりませんが、「簡単な解決策」を思いつくことができると思います。
- 「図の例」に示すように、グラフ 1 (最初のグラフ) で最適なパスを個別に見つけます。このパス、たとえば CF1 のコスト関数を計算します。
- グラフ 1 の最適パスで色付きのノードの数を見つけます。
- グラフ 1 のすべての色付きノードについて、グラフ 2 からすべての代替接続を削除します。つまり、グラフ 2 のパスがグラフ 1 で使用されている色付きノードを通過する必要があることを確認します。
- グラフ 2 で最適なパスを見つけ、そのコスト関数を計算します (CF2 とします)。
- CF1 + CF2 を計算する
- 手順 1 ～ 5 を繰り返しますが、今回はグラフ 2 から開始し、グラフ 1 の色付きノードをグラフ 2 の初期最適パスと一致させます。
CF1+CF2 の最小値は、実行可能なパスのセットを提供します。
基本的に、グラフの 1 つのパスを計画し、リンクされたノードのセットに準拠するように他のグラフを取得し、結合されたコスト関数をチェックします。次に、他のグラフについて繰り返します。最適な組み合わせを見つけてください。
一般に、n グラフの場合、n^2 の最短経路計算を実行する必要がありますが、これは明らかに非常に悪いことです。しかし、素朴なアイデアとしてはうまくいくはずです。
++++++++++++++++++++
加重グラフの以前のアルゴリズムの修正版は次のとおりです。
仮定：「n」個のグラフを使用しています。それらはすべて重み付けされており、すべてに等しい固定数の「ステージ」が含まれています。
すべての開始ノードは、S1、S2、S3… と記述されます。スン。すべての端末ノードは、e1、e2、e3….. en として記述されます。
パス (ノードのコレクション) を含む空の優先度キュー (PQ) [できればバイナリ/フィボナッチ最小ヒープを使用] を開始し、対応する優先度はパスの重みの累積合計によって示されます]
すべての開始ノード (S1、S2、S3…) を挿入します。PQ に Sn を挿入し、個々のノードの優先度を 0 に設定します。
最小の重みを持つパス (グラフ番号 'k' に属しているとします) をポップし、その子を展開します。「p」個の子ノードがあるとします。[展開するステージがなくなったら、そのパスを優先キューから削除します。このように、キューの合計サイズがゼロになると、S と e の間に実行可能なパスはありません]
k に等しくないすべての i に対して i = 1 から n の場合、次の手順を繰り返します。
4a. 残りの (n-1) グラフでp 個のパスのどれが実行可能かを確認します。
4b. PQ への実行可能なすべてのパスを挿入します (優先順位を計算した後)。
4c。実行可能なパスの 1 つがek で終わる場合: そのパスを「PathOptimal」としてマークし、5 に進みます。それ以外の場合: 3 に進みます。
k に等しくないすべての i に対して i = 1 から n の場合: 'PathOptimal' に対して各グラフで対応するパスを見つけ、それらを出力として報告します。
ここでは、パスの重みの概念を正しく実装する必要があります。パスの重みは次のようになります: そのパスに含まれるエッジの重みの合計 + 残りの (n-1) グラフのすべての兄弟パスに含まれるエッジの重みの合計。
実現可能性の概念がビジネス ルールになります。つまり、子が色付きのノードである場合、他のすべての (n-1) グラフの前のパスの対応する子は同じ色でなければなりません。色付きのノードでない場合、兄弟の子は色なしにする必要があります。
[私が作ったばかりなので、アルゴリズムに明らかな欠陥がある場合はお知らせください。また、これは Dijkstra から大量に借りてきたので、これを高速化する方法を見つけられるかどうか教えてください。]
PS:- ただし、問題の範囲を考えると、決定論的な方法ではなく、遺伝的アルゴリズムを使用してこれを解決したいと思います。
