एक ग्राफ में सबसे छोटा सर्किट ढूंढना जो कम से कम एक बार

Question

पर जाता है, भले ही मैं अभी भी एक नौसिखिया हूं, मुझे ग्राफ से संबंधित समस्याओं (सबसे कम पथ, खोज आदि) को हल करना अच्छा लगता है। हाल ही में मैं इस तरह एक समस्या का सामना करना पड़ा:

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

:

सीमा 1 < = एन < = 40 000/1 < = एक्स < = 15/1 < = ई < = 50 000

यहाँ एक उदाहरण है कर रहे हैं लाल नोड (0) पथ की शुरुआत और खत्म होना चाहिए। आपको सभी ब्लू नोड्स (1,2,3,4) पर जाना होगा और वापस जाना होगा। कम से कम पथ यहाँ होगा:

0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 30

की कुल लागत के साथ मैं करने के लिए डिज्कस्ट्रा का उपयोग कर के बारे में सोचा सभी एक्स (नीले) नोड्स के बीच सबसे छोटा रास्ता ढूंढें और फिर निकटतम अनजान एक्स (नीला) नोड चुनने के लालची को ढूंढें, लेकिन यह काम नहीं करता है (कागज पर 30 के बजाय 32 के साथ आता है)। इसके अलावा मैंने बाद में देखा कि एक्स नोड्स के सभी जोड़े के बीच सबसे छोटा रास्ता ढूंढने से ओ (एक्स * एन^2) समय लगेगा जो बहुत सारे नोड्स के साथ बहुत बड़ा है।

सर्किट के लिए मुझे केवल एक चीज मिल सकती है जो यूलेरियन सर्किट था जो केवल एक बार प्रत्येक नोड पर जाने की अनुमति देता है (और मुझे इसकी आवश्यकता नहीं है)। क्या यह डिजस्ट्रा के साथ सुलझाने योग्य है या क्या कोई अन्य एल्गोरिदम है जो इसे हल कर सकता है?
1) भागो हर नीले नोड से कम से कम पथ खोज एल्गोरिथ्म) जोड़ो में दूरी की गणना करने के लिए (यह हे (एक्स * (ई लॉग एन) में किया जा सकता):

Answer 1

यहाँ एक समाधान है जो होने की संभावना काफी तेजी से हो रहा है।
2) शून्य वर्टेक्स और नीले रंग के अक्षरों के साथ केवल एक नया ग्राफ बनाएं (एक्स + 1 शिखर)। पहले चरण के दौरान गणना की गई जोड़ों की दूरी का उपयोग करके किनारों को जोड़ें।
3) नया ग्राफ टीएसपी के लिए गतिशील प्रोग्रामिंग समाधान का उपयोग करने के लिए काफी छोटा है (इसमें ओ (एक्स^2 * 2^एक्स) समय जटिलता है)।