क्यों अधिकांश ग्राफ एल्गोरिदम नकारात्मक संख्याओं को इतनी आसानी से अनुकूलित नहीं करते हैं?

Question

Algorithm Design Manual का कहना है:

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

लेकिन क्यों? जब हम मूल वजन के सामने नकारात्मक - जोड़ते हैं, तो मुझे लगता है कि वजन से जुड़े अधिकांश ग्राफ समस्याओं को समान रूप से निपटाया जा सकता है, है ना?

Answer 1

क्योंकि जब आप पथ की न्यूनतम या अधिकतम लागत पर विचार कर रहे हैं तो आप हमेशा सभी चरणों के योग पर विचार करते हैं।

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

ऋणात्मक वजन होने का तात्पर्य है कि भविष्य में पथ की लागत कम हो सकती है, यही कारण है कि यह समस्याएं पैदा करता है: आप किसी भी बिंदु तक पहुंचने के बाद भी संभावित अच्छे पथों की सूची से पथ को बाहर नहीं कर सकते अब दूसरे की तुलना में अधिक महंगा है क्योंकि आप नकारात्मक वजन वाले किनारों को ढूंढ सकते हैं जो स्थिति को बदलते हैं।

बस एक उदाहरण के रूप

: यदि आप -2 दो वजन 1 के किनारों और से परस्पर जुड़े हुए दो नोड्स है आप मनमाने ढंग से कम लागत (-∞ भी) के साथ एक मार्ग का निर्धारण करने के लिए उन दोनों के बीच एक चक्र बना सकते हैं।

Answer 2

दरअसल, कम से कम पथ एल्गोरिदम ऋणात्मक संख्याओं के साथ परेशानी है,

यह Dijkstra's Algorithm के लिए सच है, लेकिन सामान्य रूप में कम से कम पथ एल्गोरिदम के लिए नहीं है। Bellman-Ford Algorithm नकारात्मक किनारे के वजन से निपट सकता है, बशर्ते ग्राफ में नकारात्मक चक्र न हों। हालांकि:

Bellman- फोर्ड नकारात्मक चक्र का पता लगाने और अपने अस्तित्व, रिपोर्ट लेकिन यह एक सही जवाब नहीं दे सकता है, तो एक नकारात्मक चक्र स्रोत से पहुंच योग्य नहीं है सकते हैं।

Answer 3

मैं विशेष रूप से सबसे छोटी पथ समस्या के लिए एक उत्तर जोड़ूंगा। नकारात्मक किनारों के साथ सामान्य समस्या Jack’s answer में अच्छी तरह से वर्णित है।

प्रत्येक किनारे e ∈ E के लिए लंबाई l(e) ≤ 0 के किनारों के साथ G = (V, E) ग्राफ़ पर विचार करें। G में सबसे छोटा रास्ता G' में l'(e) = - l(e) ≥ 0 ∀e ∈ E के साथ सबसे लंबा पथ जैसा ही है। Longest path problem सामान्य ग्राफ में एनपी-हार्ड होने के लिए जाना जाता है। हालांकि इसे डीएजी और ग्राफ के अन्य वर्गों में रैखिक समय में हल किया जा सकता है।

cls answered के रूप में, समस्या केवल नकारात्मक चक्रों के साथ है और Bellman-Ford algorithm कुछ किनारों को नकारात्मक होने का सामना कर सकती है। लेकिन सबसे लंबे पथ एल्गोरिदम को ग्राफ में चक्रों का सामना करना पड़ता है और बेलमैन-फोर्ड नकारात्मक चक्रों के साथ ग्राफ पर सही उत्तर नहीं दे सकता है। इसलिए बेलमैन-फोर्ड एल्गोरिदम का उपयोग केवल सकारात्मक चक्र वाले ग्राफ़ों में सबसे लंबे पथ की गणना करने के लिए किया जा सकता है। उल्लेख, क्योंकि यह विचार obviously not uncommon है।