特別な条件の下で最短経路コストを見つけるには？

Question

ソース頂点s、デスティネーション頂点tおよびサブセットv 'が与えられた場合、グラフ内のsから頂点tまでの最短の非ループ経路をどのように見つけるか？サブセット内の頂点をパスに含める必要があります。

Answer 1

Traveling Salesman Problem (TSP)の亜種です。

あなたはグラフ（Floyd Warshall Algorithm）における全対全最短経路を実行することにより、TSPの正確なインスタンスにあなたの問題を変換し、新しいグラフ作成することができます。今すぐ

G'={V' U {s,t}, E'} 
V' - the "must go through" subset 
E' = { (s,v), (v,t), (u,v) | u,v in V'} (In words: all edges between two nodes in the new graphs) 

を見つけますG'にあるすべてのノード（TSP）を通過する擬似パスは、（2つのペアの間の各パスを拡張した後に）基準を満たす最小パスです。

残念ながら、TSPはNP-Complete問題がある（そこにそれを解決するための既知の多項式時間アルゴリズムはなく、ほとんどは1つが存在すらしていないと考えている）、およびV'「ノードを経由しなければならない」のあなたのセットは比較的小さくなければ（そしてあなたはアルゴリズムの指数関数時間を稼ぐことができます）、最適ではないかもしれない「十分に良い」アルゴリズムで解決する必要があります。

---

「無ループ」に関するない追記 - 例えば、それは実行不可能であるかもしれない点に注意してください。この例では

 --------- 
    |   | 
    v   | 
s -> a -> b -> c 
    | 
    | 
    t 

、基準を満たすための唯一の道は、あなたの答えのためのs->a->b->c->t