無向で正の重み付きグラフGが与えられた場合、 Gの一部のエッジの重みは不明です。例えば、
ここで、edge(B, C) の重みは不明です。
AからBへの移動には7のコストがかかります。BからCへ、またはその逆にトラバースすることで未知の重みe = weight(B,C)を導き出すことができ、 eのコストがかかり、最終的に既知の重みになります。そして、 AからCからBを通って歩くと、合計でe+7のコストがかかります。
私の質問は、開始点が与えられたときに、どのくらいの速さですべての未知の重量を取得できるでしょうか? つまり、開始点 (たとえばA ) からすべての未知の重みエッジを可能な限り小さいコストでトラバースします。
未知数が1個の場合は単純です。最初に、開始点から目的のエッジの頂点までの最短パスを見つけ、未知の重みエッジをトラバースできます。しかし、未知の重みエッジの数が 1 より大きくなった場合の解決方法がわかりません。
誰でもこれを行う方法を理解できますか?
完全な解決策を提供することはできませんが、未知のエッジが訪問するノードである巡回セールスマンの問題に関連しているようです。
しかし、アプリオリに最適解を見つけることはできないと思います。この例を考えてみましょう
a-b = 1
b-c = ?
b-d = ?
a-d = 10
重みが小さい場合b-c(たとえば 1)、から始まる最短パスaは、 2 回a-b-c-b-dトラバースします。b-c重みが大きい (たとえば 100)場合b-c、最短パスは になり、 2 回トラバースするa-d-b-cよりも安価な接続が優先されます。a-db-c
2 番目のグラフ を作成できますがG'、これは同じですが、「未知のエッジ」はありません1。次に、すべての最短経路アルゴリズムを使用し、アルゴリズムからのデータを使用して空白を埋めることができます。
Floyd Warshall アルゴリズムは、すべての最短パスへのすべてを提供します。O(n3)
(1) 正式には:G'=(V,E',w')ここで:
E' = { e | e is in E and w(e) != ? }
w'(e) = w(e) if w(e) != ?