Özel şartlar altında en kısa yol masrafı nasıl bulunur?

Question

G = (V, E) ağırlıklı bir grafik verilmişse, bir kaynak köşe, bir hedef köşe ve bir altküme v ’, grafikte vertex t'den s'ye en kısa döngü dışı yolu nasıl buluruz? Alt kümedeki köşe noktaları yoluna dahil edilmelidir.

Answer 1

Bu, Traveling Salesman Problem (TSP)'un bir çeşididir.

Grafiğin ( Floyd Warshall Algorithm) tüm-tüm en kısa yolu çalıştırarak TSP tam örneğine sorununuzu dönüşümü ve sonra yeni bir grafik oluşturmak için

: bulma, Şimdi

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''daki tüm düğümlerden (TSP) geçen miminal yol, ölçütleri karşılayan en az yoldur (her iki yol arasında geçen her yolun arkasından).

Maalesef TSP NP-Complete sorundur (orada bunu çözmek için bilinen hiçbir polinom zaman algoritması olduğunu ve en fazla bir bile yok inanmak) ve V' "düğümler geçmesi gerekiyor" nin set nispeten küçük olduğu sürece (ve Algoritmanın üstel zaman çalışma süresini karşılayabiliyorsunuz), optimal olmayabilecek bir "yeterince iyi" algoritmasına yer vermeniz gerekecek. Bu örnekte

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

, kriterlerini karşılamak için tek yol Cevabınız için s->a->b->c->t