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.Özel şartlar altında en kısa yol masrafı nasıl bulunur?
1
A
cevap
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
Teşekkür şudur: örneğin, mümkün olmayan olabileceğini unutmayın - "hayır döngüler" ile ilgili
Sidenote .Bu yöntemle ilgileniyorum. Ama biraz şüphem var. 1.Tüm all to all all kısa yolunu ** aradığımda, her yolun nasıl garanti edileceği diğerlerinden farklıdır (her köşe geçişi sadece bir kez geçer). 2.TSP problemi, tüm problemleri içeren bir döngü yolunu bulmaktır, bu soruna göre, tipik algoritmaları değiştirmek için neye ihtiyaç vardır? – bigboxxx
@bigboxxx Hiçbir döngü olmadığını garanti edemezsiniz, çünkü yukarıda bahsettiğim gibi durumlar var - döngü olmayan bir yol yoktur. – amit
Kitle, min ağırlıklarla yolu bulmaktır, bu arada her bir talep köşe noktası sadece bir kez ziyaret edilmelidir. – bigboxxx