क्या डिजस्ट्रा की तुलना में तेज़ एल्गोरिदम हैं?

केवल पॉजिटिव एज वजन के साथ एक निर्देशित, जुड़े ग्राफ को देखते हुए, एक फाइबोनैकी ढेर का उपयोग करते हुए डिजस्ट्रा की तुलना में दो शीर्षकों के बीच सबसे छोटा रास्ता खोजने के लिए तेज़ एल्गोरिदम हैं?क्या डिजस्ट्रा की तुलना में तेज़ एल्गोरिदम हैं?

विकिपीडिया कहता है कि डिजस्ट्रा ओ (| ई | + | वी | * लॉग (| वी |)) में है (एक फाइबोनैकी ढेर का उपयोग करके)।

मैं ऑप्टिमाइज़ेशन की तलाश नहीं कर रहा हूं, उदाहरण के लिए, निष्पादन समय का आधा, बल्कि अलग-अलग समय जटिलता (जैसे ओ (एन * लॉग एन) से ओ (एन) में जाने वाले एल्गोरिदम)।

इसके अलावा, मैं निम्नलिखित दृष्टिकोण पर आपकी राय जानना चाहते हैं:

सब बढ़त वजन के GCD निर्धारित करें।
ग्राफ को वर्दी एज वजन वाले ग्राफ में बदलें।
दो दिए गए शीर्षकों के बीच सबसे छोटा रास्ता खोजने के लिए बीएफएस का उपयोग करें। बिंदु 2 के लिए

उदाहरण:
GCD कल्पना होने के लिए 1. तब मैं किनारे
एक ---> बी परिणत हो गया (धार वजन 3)

में A-> एक '-> ए' '-> बी (3 गुना बढ़त वजन 1)
यह परिवर्तन निरंतर समय खर्च करता है और प्रत्येक किनारे के लिए एक बार किया जाना होगा। तो मैं उम्मीद करता हूं कि यह एल्गोरिदम ओ (| ई |) (परिवर्तन) + ओ (| ई | + | वी |) (बीएफएस) = ओ (2 * | ई | + | वी |) = ओ (| ई | + | वी |)

मेरे प्रश्न को पढ़ने के लिए समय निकालने के लिए धन्यवाद और मुझे आशा है कि आपका समय ^^ कम नहीं होगा। आपका दिन शुभ हो।

स्रोत

2009-11-09 Dave O.

मुझे लगता है कि आप जीसीडी की लागत को ध्यान में रखना भूल रहे हैं। –

परिवर्तन निरंतर समय में नहीं चलता है। आपको नए चरमों की एक चर संख्या बनाना होगा। –

जीसीडी उपयोग करने का सबसे अच्छा मूल्य होगा, लेकिन कोई हमेशा वापस आ सकता है और केवल 1 का उपयोग कर सकता है, ताकि चरण 1 के लिए कोई समय व्यतीत न हो। –

आपके एल्गोरिदम के लिए आपके द्वारा किए गए बड़े ओह विश्लेषण गहराई से त्रुटिपूर्ण हैं। मान लें कि सभी किनारों की प्रमुख संख्याएं हैं। नए ग्राफ में किनारों की संख्या सभी भारों के योग के बराबर होगी। इस प्रकार नए ग्राफ मूल ग्राफ में O(W x |E| + |V|) है जो O(|E| + |V| log |V|) से बहुत बड़ा हो सकता है।

स्रोत

2009-11-09 14:22:11

आप सही हैं। सबसे बुरी स्थिति परिदृश्य में, सभी किनारे के वजन प्रमुख संख्याएं हैं और ग्राफ पूर्ण है। इस प्रकार डब्ल्यू कम से कम है | वी |^2 (| वी |^वजन के साथ 2 किनारों> = 1)। तो मेरा एल्गोरिदम चलता है | वी |^2 * | वी |^2 + | ई | = | वी |^4 + | ई | कम से कम। हालांकि, मेरा मूल प्रश्न अनुत्तरित रहता है। –

श्री, मेरा मतलब था | वी |^4 + | वी | - मैं अपनी पोस्ट या मेरी टिप्पणियां क्यों संपादित नहीं कर सकता? –

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

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

एक नोड से दूसरी नल में टॉट चेन का पालन करें। यह सबसे छोटा रास्ता है।

एक कंप्यूटर प्रोग्राम के रूप में इसे लागू करने के लिए, आप दो औद्योगिक रोबोट :)

की आवश्यकता होगी एक वास्तविक दुनिया उदाहरण के लिए Ant colony optimization जो कम समय में बहुत अच्छा परिणाम देता है का उपयोग करें। चूंकि आप इस एल्गोरिदम में रनों की संख्या निर्दिष्ट कर सकते हैं, आप तय कर सकते हैं कि यह कितना समय बिताया (यानी रनटाइम केवल नोड्स की संख्या पर निर्भर करता है) जो आपको ओ (एन) देता है लेकिन गारंटीकृत सही परिणाम नहीं देता है।

स्रोत

2009-11-09 14:35:41

वह ओ (1) कैसा है? –

मैं वास्तव में ओ (एल) एल्गोरिदम के बारे में सोच सकता हूं, जहां एल सही समाधान में नोड्स की संख्या है: क्वांटम-बोगो-शॉर्ट-पथ (http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort) –

ओ (1) है यदि आप ग्राफ बिल्डिंग चरण पर विचार नहीं करते हैं। – mouviciel

क्या डिजस्ट्रा से तेज एल्गोरिदम हैं?

हां। सवाल योग्य नहीं है ताकि सभी मामलों में या यहां तक कि ज्यादातर मामलों में बेहतर प्रदर्शन की आवश्यकता हो। एक मामले में बेहतर प्रदर्शन के साथ एक एल्गोरिदम एक सकारात्मक उत्तर स्थापित करने के लिए पर्याप्त है।

डिज्कस्ट्रा की पद्धति पर Bellman- फोर्ड विधि द्वारा अपेक्षित पुनरावृत्तियों की आम तौर पर बड़ी संख्या के बावजूद, व्यवहार में Bellman- फोर्ड विधि यात्रा प्रति छोटे भूमि के ऊपर की वजह से बेहतर हो सकता है [स्वर्ण, बी, 1976 "शॉर्ट-पाथ एल्गोरिदम: ए तुलना," ऑपरेशंस रिसर्च, वॉल्यूम। 44, पीपी 1164-1168]।

ऊपर उद्धरण दिमित्री पी। बर्त्सेकस (मार्च 1 99 2) से है। "सबसे सरल पथों के लिए एल्गोरिदम सुधारने वाला एक सरल और तेज़ लेबल" (पीडीएफ)। नेटवर्क, वॉल्यूम। 23, पीपी 703-70 9, 1 99 3। http://www.mit.edu/people/dimitrib/SLF.pdf। 2008-10-01 को पुनःप्राप्त।

संक्षेप में, मेरा दावा बेर्त्सेकस की गोल्डन की व्याख्या पर आधारित है। चाहे मेरा निष्कर्ष खड़ा हो या नहीं, आप लेबल सेटिंग विधि के रूप में डिजस्ट्रा एल्गोरिदम के वर्गीकरण के लिए बर्टसेकस को दिलचस्प पाते हैं, लेबल विधियों को ठीक करने के लेबल के विपरीत।

स्रोत

2009-11-09 14:52:33

उन्होंने विशेष रूप से कम एसिम्पटोटिक रनटाइम के समाधान के बारे में पूछा। –

ठीक है, तो अंतिम परिणाम के रास्ते पर एक लेम्मा की तरह इसका इलाज करें। –

सबसे पहले, "प्रैक्टिस में" तेजी से क्या होता है इसके बारे में परिणाम * एसिम्प्टोटिकली * बेहतर वृद्धि के लिए प्रासंगिक नहीं हैं, क्योंकि अभ्यास में आने वाले ग्राफ सीमित और आमतौर पर छोटे होते हैं। इसके अलावा, 1 9 76 में तेजी से अनुवाद 200 9 में तेजी से अनुवाद नहीं किया जाता है। एक बात के लिए, "इन-प्रैक्टिस" ग्राफ आज बड़े हैं - एक अतिरंजित उदाहरण लेने के लिए, '200x^2' 'n^3' से चार गुना तेज है एन = 50 के लिए, लेकिन एन = 1000 के लिए धीमी गति के रूप में एक-पांचवां। – ShreevatsaR

हमेशा ए * होता है, और यह पदानुक्रमित ए * और ए * जेपीएस की तरह व्युत्पन्न होता है।

स्रोत

2012-07-01 01:48:37 Puppy

मुझे लगता है कि ए * यह कहने के लिए कुछ प्रकार का सार्थक ह्युरिस्टिक है कि यह सबसे अच्छा मार्ग हो सकता है। – mwfearnley

क्या डिजस्ट्रा की तुलना में तेज़ एल्गोरिदम हैं?

उत्तर

संबंधित मुद्दे