लर्निंग ग्राफ एल्गोरिदम

Question

एल्गोरिदम में, मैं ज्यादातर आत्म-सिखाया गया हूं और यह काफी हद तक ठीक है। हालांकि, मुझे ग्राफ एल्गोरिदम को समझने में परेशानी हो रही है। मैं किसी प्रकार के संदर्भ की तलाश में हूं जिसमें अवधारणाएं और वास्तविक कोड हैं, इसलिए मैं न केवल सिद्धांत (जिसे मैं आमतौर पर ठीक करता हूं) सीख सकता हूं, बल्कि यह भी महसूस कर सकता हूं कि ग्राफ का प्रतिनिधित्व कैसे किया जाता है और अभ्यास में छेड़छाड़ की जाती है (जो मेरे पास आमतौर पर है एक कठिन समय grasping)। क्या एसओ वितरित कर सकते हैं? किताबों, लिंक से लेकर मौजूदा परियोजनाओं तक कुछ भी तब तक बढ़िया होगा जब तक उनके पास अवधारणा और कार्यान्वयन दोनों ही हों।

यह भाषा अज्ञेयवादी है, लेकिन मैं अजगर से सबसे परिचित हूं और एफपी के साथ अधिक अनुभव नहीं है।

Answer 1

इन दोनों बहुत अच्छे हैं:

• The Algorithm Design Manual

• Algorithms in C++ Part 5: Graph Algorithms (सी ++ बिट के बारे में चिंता न करें, छद्म कोड भी है)

नि: शुल्क सामग्री:

• Chapter 5. Graphs and graph algorithms

Answer 2

स्टीव येगे कहते हैं this एल्गोरिदम पर एक भयानक पुस्तक है जो व्यापक रूप से ग्राफ का उपयोग करती है।

Answer 3

मैं किताब नीचे लिंक से रेखांकन के बारे में बहुत कुछ सीखा है ... यह मेरी पसंदीदा पुस्तकों में से एक है: http://books.google.com/books?id=5l5ps2JkyT0C&printsec=frontcover&dq=a+course+in+combinatorics&source=bl&ots=wSYYY6KPuI&sig=mZLrdj0xo2mTxW4MxYt4tW_E-10&hl=en&ei=PoHHTOaROIHGlQegn8ibAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCkQ6AEwAQ#v=onepage&q&f=false

A Course in Combinatorics 
J. H. van Lint, R. M. Wilson 
Cambridge University Press 
ISBN 0 521 00601 5

Answer 4

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

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

Answer 5

Bellman- फोर्ड एल्गोरिथ्म: यहां तक ​​कि -eve बढ़त वजन (नहीं चक्र) के साथ भारित निर्देशित ग्राफ में अन्य सभी नोड्स के लिए स्रोत से सबसे छोटा रास्ता। धीमे लेकिन डिज्स्क्रा से बहुमुखी। जटिलता: ओ (| वी | | E |।)

BFS: ढूँढें पथ एक दिया शिखर से संयुक्त राष्ट्र भारित अन-निर्देशित ग्राफ में अन्य नोड के लिए। जटिलता: ओ (| वी | + | ई |)। जब आप आगे की ओरिएंट जानते हैं और उचित डेटा संरचना का उपयोग करते हैं तो यह तेज़ होता है I।(| वी |) ई फीफो Que पता लगाना के लिए जो शिखर पहले से ही जटिलता से संसाधित हे को कम किया जा सकता

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

Floyed Warshal एल्गोरिथ्म: + पूर्व संध्या, -eve (नहीं चक्र) बढ़त वजन के साथ निर्देशित अनिर्धारित ग्राफ के सभी जोड़ी कम से कम पथ का पता लगाएं। लेकिन यह पथ के विवरण वापस नहीं लौटाता है। इसका उपयोग ग्राफ़ में वजन चक्र का पता लगाने के लिए किया जा सकता है। जब यह एक को समाप्त करता है तो यह समाप्त हो जाता है। यह प्रत्येक जोड़ी के जोड़ों के बीच ग्राफ के माध्यम से सभी संभावित पथ की तुलना करता है। इसलिए यह गतिशील दृष्टिकोण का उपयोग लालची दृष्टिकोण नहीं करता है। जटिलता: ओ (| वी^3 |)

जॉनसन एल्गोरिथ्म: निर्देशित भारित विरल ग्राफ में सभी जोड़ी सबसे छोटा रास्ता ढूंढने में जब किनारे वजन पूर्व संध्या, -eve नहीं बल्कि -eve चक्र + है। यह मूल ग्राफ से परिवर्तित ग्राफ की गणना करने के लिए पहले बेलमैन-फोर्ड एल्गोरिदम का उपयोग करता है। यह वजन घटाने के किनारों को हटा देता है। तो पथ खोजने के लिए डिजस्ट्रा लागू किया जाता है। जटिलता: हे (वी^2 लॉग V + VE)

डिज्कस्ट्रा एल्गोरिथ्म: इस एल्गोरिथ्म नहीं के मूल संस्करण प्राथमिकता क्यू उपयोग करता है ताकि जटिलता हे है (| वी^2 |) लेकिन एक नया संस्करण इस डेटा संरचना का उपयोग करता है इसलिए जटिलता ओ (ई + वी लॉग वी) बन जाती है। और यह तेज़ एकल स्रोत सबसे छोटा पथ एल्गोरिदम है। यह नजदीक नोड और अनन्तता के लिए अनगिनत नोड्स को अन्तर्निहित नोड्स के लिए एक टिकाऊ वजन निर्दिष्ट करके काम करता है, इसके सभी नजदीक किनारों के लिए नजदीक नोड देखो के लिए और न्यूनतम वजन के साथ चयन करें। और इसे पथ सेट में जोड़ें।

कृष्काल का एल्गोरिदम: एमएसटी खोजने के लिए जहां यह कम से कम संभव वजन का किनारा पाता है जो बिना निर्देशित, भारित ग्राफ पर वन में किसी भी दो पेड़ को जोड़ता है। यह लालची एल्गोरिदम है। यह न्यूनतम स्पैनिंग वन भी पाता है। जटिलता: हे (ई लॉग वी)

रस्मी के एल्गोरिथ्म: यह किनारों कि संयुक्त राष्ट्र निर्देशित, भारित ग्राफ पर एक पेड़ के रूप में के सबसेट पाता है। लेकिन कृष्णाल के एल्गोरिदम की तरह एमएस वन नहीं मिल सकता है।

ब्रौवका का एल्गोरिदम: इस एल्गोरिदम के साथ समस्या यह है कि वजन ग्राफ में अद्वितीय होना चाहिए। यह प्रत्येक कशेरुक की जांच करके एमएसटी पाता है और फिर छोटे वजन के साथ डालता है। यह एल्गोरिदम प्रकृति में समानांतर है लेकिन प्राइम के एल्गोरिदम से तेज़ नहीं है।

क्रशकल के एल्गोरिदम के समान ही जटिलता।