मार्ग समस्या: कम से कम कुल लागत

Question

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

उदाहरण एक से जम्मू तक जाने के लिए तो के लिए हो सकता है डिज्कस्ट्रा इस पथ (कोष्ठक के बीच वजन)

A (4) D (6) J -> total cost: 10 

और कलन विधि मैं की जरूरत है, की स्थापना कश्मीर = 10,

की तरह कुछ मिलेगा मिलेगा

A (1) B (2) C (2) D (1) E (3) F (2) G (1) H (3) J -> total cost: 15 

इस समस्या के लिए किसी भी अच्छी तरह से ज्ञात एल्गोरिथ्म है?

अग्रिम धन्यवाद।

यूगेनियो

templatetypedef के जवाब के रूप में संपादित करें। कुछ प्रश्न:

1) तथ्य यह है कि औसत को चलाने के लिए चक्र को कई बार लेना मेरे समस्या के लिए अच्छा नहीं है: शायद मुझे इसका उल्लेख करना चाहिए था लेकिन मैं उसी नोड पर जाना चाहता हूं एक से अधिक बार

2) यह सच है कि मैं नकारात्मक वजन की जरूरत नहीं है फायदा उठाने के लिए संभव है?

3) जब आप ने कहा कि ओ (KE) आप पूरे एल्गोरिथ्म के लिए या सिर्फ अतिरिक्त भाग के लिए मतलब था?

चलिए इस सरल कार्यान्वयन को सी में लेते हैं जहां n = nodes की संख्या ई = किनारों की संख्या, डी दूरी के साथ एक वेक्टर है, पूर्ववर्ती के साथ पी वेक्टर और एक संरचना किनारों (यू, वी, डब्ल्यू) किनारों को याद करते हैं रेखांकन में

for (i = 0; i < n; ++i) 
    d[i] = INFINITY; 

    d[s] = 0; 

    for (i = 0; i < n - 1; ++i) 
     for (j = 0; j < e; ++j) 
      if (d[edges[j].u] + edges[j].w < d[edges[j].v]){ 
       d[edges[j].v] = d[edges[j].u] + edges[j].w; 
       p[edges[j].v] = u; 
       } 

मुझे यकीन है कि कैसे मैं अपने जवाब के अनुसार कोड को संशोधित करना चाहिए नहीं कर रहा हूँ; कुल लागत के बजाय औसत को ध्यान में रखना चाहिए यह पर्याप्त होना चाहिए?

for (i = 0; i < n; ++i) 
     d[i] = INFINITY; 

    d[s] = 0; 

    for (i = 0; i < n - 1; ++i) 
     steps = 0; 
     for (j = 0; j < e; ++j) 
      if ((d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){ 
       d[edges[j].v] = d[edges[j].u] + edges[j].w; 
       p[edges[j].v] = u; 
       steps++; 
      } 

लेकिन वैसे भी मुझे नहीं पता कि एक ही समय में के सीमा को कैसे ध्यान में रखा जाए ... आपकी मदद के लिए अग्रिम धन्यवाद।

संपादित जब से मैं कुछ त्रुटियाँ मैं इस नैफ समाधान के बारे में सोच रहा हूँ बर्दाश्त कर सकते हैं:

• precompute सभी कम से कम रास्तों और एक संशोधित ग्राफ़ के सभी कम से कम पथ एक
• precompute में याद , जहां मैंने एक निश्चित वजन पर किनारों को काट दिया और उन्हें बी

जब मुझे पथ की आवश्यकता है, तो मैं ए में देखता हूं, उदाहरण के लिए से एक्स y को यह मार्ग है x-> Z-> y तो हर कदम मैं बी में लग रहे हैं, के लिए इतना x> z मैं अगर वहाँ बी में एक कनेक्शन है, अगर नहीं मैं अन्यथा रखने x> जेड देखने के लिए मैं पथ x> z को बी द्वारा प्रदान किए गए उपपथ के साथ भरता हूं, जो x-> j-> h-> z जैसे कुछ हो सकता है; तो मैं z-> y के लिए वही करता हूं। प्रत्येक बार मैं यह भी जांचूंगा कि क्या मैं चक्रीय पथ जोड़ रहा हूं।

शायद मुझे कुछ अजीब पथ मिलेंगे लेकिन यह ज्यादातर मामलों में काम कर सकता है। यदि मैं विभिन्न "कट थ्रेसहोल्ड" के साथ प्रयास करने का समाधान बढ़ाता हूं तो शायद मैं के बाधा का सम्मान करने के करीब भी हो सकता हूं।

Answer 1

आप अधिकांश के किनारों/नोड्स का उपयोग करके न्यूनतम पथ खोजने के लिए बेलमैन-फोर्ड एल्गोरिदम को थोड़ा संशोधित कर सकते हैं। यदि किनारों की संख्या तय की गई है तो आपको कुल लागत को कम करना होगा, क्योंकि औसत लागत कुलकोस्ट/संख्याऑफजेज होगी।

समाधानों में से एक समाधान 1 से के के नंबरऑफेज को फिर से शुरू करना होगा, न्यूनतम कुल लागत पाएं और न्यूनतम कुलकोस्ट/नंबरऑफेज चुनें।

Answer 2

मेरा मानना ​​है कि आप बेलमैन-फोर्ड एल्गोरिदम के एक संशोधित संस्करण का उपयोग करके इसे हल कर सकते हैं।

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

BF(s, t, 0) = infinity 
BF(s, s, 0) = 0 

कर रहे हैं, अगर हम लंबाई मीटर के रास्ते के लिए मान पता है, हम इसके लिए मिल सकता है ध्यान देने योग्य बात है कि पुराने का रास्ता अब भी मान्य हो सकता है, या हम लंबाई एक के बाद कुछ पथ का विस्तार करना चाहते द्वारा लंबाई मीटर + 1 के पथ:

BF(s, t, m + 1) = min { 
        BF(s, t, m), 
        BF(s, u, m) + d(u, t) for any node u connected to t 
        } 

एक पूरे के रूप एल्गोरिथ्म ध्यान देने योग्य बात है कि किसी भी कम से कम पथ की लंबाई होना आवश्यक है से काम करता है एन से अधिक नहीं और फिर उपरोक्त पुनरावृत्ति और गतिशील प्रोग्रामिंग का उपयोग सभी टी के लिए बीएफ (एस, टी, एन) के मूल्य की गणना करने के लिए करें। इसका कुल रनटाइम ओ (ईवी) है, क्योंकि प्रत्येक चरण और वी कुल शीर्षकों पर विचार करने के लिए ई किनारे हैं।

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

गणितीय रूप से, समाधान इस तरह दिखता है।

BF(s, t, 0).edges = 1 
BF(s, t, 0).cost = infinity 

BF(s, s, 0).edges = 0 
BF(s, s, 0).cost = 0 

BF(s, t, m + 1).cost = min { 
    BF(s, t, m).cost, 
    (BF(s, u, m).cost * BF(s, u, m).edges + d(u, t))/(BF(s, u, m).edges + 1) 
} 

BF(s, t, m + 1).edges = { 
    BF(s, t, m).edges   if you chose the first option above. 
    BF(s, u, m).edges + 1  else, where u is as above 
} 

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

संपादित: अपने नए सवाल के जवाब में, यदि आप एक पथ पर नोड्स नकल नहीं करना चाहती इस दृष्टिकोण काम नहीं करेगा। जैसा कि @ कॉमेस्टिबल्स ने इंगित किया है, समस्या का यह संस्करण एनपी-हार्ड है, इसलिए जब तक पी = एनपी आपको इस समस्या के लिए कोई अच्छा बहुपद-समय एल्गोरिदम नहीं मिलना चाहिए।

रनटाइम के लिए, ऊपर वर्णित एल्गोरिदम मैंने कुल समय ओ (केई) में चलाया है। ऐसा इसलिए है क्योंकि पुनरावृत्ति की गणना करने के प्रत्येक पुनरावृत्ति ओ (ई) समय लेता है और कुल के पुनरावृत्तियों के होते हैं।

अंत में, आइए आपके प्रस्तावित कोड को देखें। मैंने इसे यहां दोबारा मुद्रित किया है:

for (i = 0; i < n - 1; ++i) { 
    steps = 0; 
    for (j = 0; j < e; ++j) { 
     if ((d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){ 
      d[edges[j].v] = d[edges[j].u] + edges[j].w; 
      p[edges[j].v] = u; 
      steps++; 
     } 
    } 
} 

आपका पहला प्रश्न यह था कि खाते को कैसे ध्यान में रखना है। इस k अप करने के लिए गिनती करने के लिए बाहरी पाश दोबारा लिख ​​कर आसानी से किया जा सकता है, नहीं n - 1. हमें इस कोड को देता है कि:

for (i = 0; i < k; ++i) { 
    steps = 0; 
    for (j = 0; j < e; ++j) { 
     if ((d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){ 
      d[edges[j].v] = d[edges[j].u] + edges[j].w; 
      p[edges[j].v] = u; 
      steps++; 
     } 
    } 
} 

एक समस्या यह है कि मैं देख रहा हूँ कि संशोधित Bellman- फोर्ड एल्गोरिथ्म की जरूरत है प्रत्येक उम्मीदवार को सबसे अच्छा पथ अपने किनारों की स्वतंत्रता को स्वतंत्र रूप से स्टोर करने के लिए, क्योंकि प्रत्येक नोड का इष्टतम पथ किनारों की एक अलग संख्या तक पहुंचा जा सकता है। इसे ठीक करने के लिए, मैं सुझाव दूंगा कि d सरणी स्टोर दो मानों को रखें - नोड तक पहुंचने के लिए आवश्यक किनारों की संख्या और उस पथ के साथ नोड की औसत लागत। फिर आप कैश किए गए पथ की लंबाई के साथ इन समीकरणों में steps चर को प्रतिस्थापित करके अपना कोड अपडेट करेंगे।

आशा है कि इससे मदद मिलती है!

Answer 3

आपकी समस्या के नए संस्करण के लिए, हैमिल्टन पथ से कमी (आपकी समस्या को अव्यवस्थित करने योग्य)। हैमिल्टन पथ का एक उदाहरण लें (यानी, एक ग्राफ जिसका किनारों को यूनिट वजन माना जाता है), स्रोत से स्रोत और सिंक शिखर और वजन 2 के किनारों को अन्य सभी और सिंक से अन्य सभी में जोड़ें। सेट करें = = वी | + 2 और स्रोत से सिंक तक पथ का अनुरोध करें। एक हैमिल्टन पथ मौजूद है यदि केवल और इष्टतम औसत किनारों की लंबाई (| वी | + 3)/(| वी | + 2) है।

हमें यह बताने की देखभाल करें कि आप इन पथों को क्यों चाहते हैं ताकि हम आपको उचित अनुमान रणनीति की सलाह दे सकें?