एपस्टीन के एल्गोरिदम और केन सबसे कम पथ के लिए येन का एल्गोरिदम

Question

मैं यह समझने की कोशिश कर रहा हूं कि ये एल्गोरिदम कैसे काम करते हैं, लेकिन मैं एक सरल स्पष्टीकरण खोजने में असमर्थ हूं। यदि कोई मुझे मूल पत्रों में विवरण की तुलना में समझने में आसान है, तो इन एल्गोरिदम के वर्णन के लिए मुझे प्रदान या इंगित कर सकता है, तो मैं इसकी बहुत सराहना करता हूं। धन्यवाद।

Answer 1

सबसे पहले मैं आपको उन कागजात के लिंक प्रदान करने देता हूं जिनके बारे में आप बात कर रहे थे।

Eppstein के कागज: D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput., vol. 28, no. 2, pp.652–673, Feb. 1999

येन के कागज: J. Y. Yen, “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.

यहाँ येन एल्गोरिथ्म की मेरी व्याख्या है:

येन एल्गोरिथ्म दो सूचियों का उपयोग करता है, यानी सूची ए (गंतव्य के लिए स्रोत से स्थायी कम से कम पथ - कालक्रम से आदेश दिया गया) और सूची बी (टेंटेटिव/उम्मीदवार सबसे कम पथ)। सबसे पहले आपको किसी भी सुसंगत सबसे कम पथ एल्गोरिदम (उदा। डिजस्ट्रा) का उपयोग करके स्रोत से गंतव्य तक पहला सबसे छोटा रास्ता खोजना होगा। फिर येन इस विचार का शोषण करते हैं कि के-वें सबसे छोटे पथ किनारों और उप-पथ (मार्ग से मार्ग के किसी भी मध्यस्थ नोड्स तक पथ) को साझा कर सकते हैं (के -1) - सबसे छोटा रास्ता। फिर आपको (के -1) सबसे छोटा रास्ता लेना होगा और मार्ग में प्रत्येक नोड को बदले में पहुंचने योग्य नहीं होगा, यानी मार्ग के भीतर नोड पर जाने वाले विशेष किनारे को बंद कर दें। एक बार नोड पहुंच योग्य नहीं है, तो पिछले नोड से गंतव्य तक सबसे छोटा रास्ता पाएं। फिर आपके पास एक नया मार्ग है जो आम उप-पथ (स्रोत से पहुंचने योग्य नोड के पूर्ववर्ती नोड) को जोड़कर बनाया गया है और नोड से गंतव्य तक नया सबसे छोटा रास्ता जोड़ता है। यह मार्ग तब सूची बी में जोड़ा जाता है, बशर्ते कि यह सूची ए या सूची बी में पहले दिखाई नहीं दे रहा है। मार्ग में सभी नोड्स के लिए इसे दोहराने के बाद, आपको सूची बी में सबसे छोटा रास्ता ढूंढना होगा और उसे सूची में ले जाना होगा। आपको बस इस प्रक्रिया को दोहराने के लिए दोहराना होगा।

इस एल्गोरिदम में ओ (एन^3) की कम्प्यूटेशनल जटिलता है। अधिक जानकारी के लिए कृपया पेपर पढ़ें।

एल्गोरिथ्म इस प्रकार है:

G = Adjacent Matrix of the Network 
Initialize: 
A_1 = shortest-path from source to destination 
Glocal ← Local copy of G 
for k = 2 → K do 
for i = 1 → [len(A_(k−1)) − 1] do 
    Current Node ← A_(k−1) [i] 
    Ri ← Sub-path (root) from source till current node in A_(k−1) 
    for j = 1 → k − 1 do 
    Rj ← Sub-path (root) from source till current node in A_j 
    if Ri == Rj then 
    Next Node ← Aj [i+1] 
    Glocal(Current Node, Next Node) ← infinity 
    Current Node ← unreachable 
    end if 
    end for 
    Si ← Shortest-path from current node till destination 
    Bi ← Ri + Si 
end for 
A_k ← Shortest-path amongst all paths in B 
Restore original graph: Glocal ← Local copy of G 
end for 

दुर्भाग्य से, मैं Eppstein के एक उपयोग नहीं किया है के रूप में येन एल्गोरिथ्म मेरी समस्या के लिए इष्टतम था।

उम्मीद है कि इससे मदद मिलती है। चीयर्स।

=====

संपादित करें:

कृपया wikipedia entry पर एक नज़र भी है। यह एक अच्छा उदाहरण है।

=====

संपादित करें:

इस प्रकार मैं सी में कुछ कार्यान्वयन लिंक हैं पाया है:

Eppstein implementation और Loading Graph for Eppstein।

यदि आप रुचि रखते हैं, तो एपस्टीन के lazy version हैं।लिंक इस प्रकार है:

Lazy Eppstein by Jimenez and Marzal

=====

संपादित करें:

बस एक और link। इसमें कई कार्यान्वयन (सी/सी ++) शामिल हैं।

=====

संपादित करें:

मैं Eppstein के एल्गोरिथ्म के एक good explanation मिल गया है।