ग्राफ और पेड़ों का उपयोग करके, क्या समस्याएं हल की जा सकती हैं, या अधिक आसानी से निपटाई जा सकती हैं?

जब मैं इस प्रश्न को पढ़ता हूं तो पहली बात यह है कि: किस प्रकार की चीजें ग्राफ़ / पेड़ का उपयोग करती हैं? और फिर मुझे लगता है कि मैं उनका उपयोग कैसे कर सकता हूं।

उदाहरण के लिए, पेड़ के दो सामान्य उपयोग करें:

• डोम
• फाइल सिस्टम

The DOM, and xml for that matter, resemble tree structures.

यह भी समझ में आता है। यह समझ में आता है कि इस डेटा को व्यवस्थित करने की आवश्यकता है । एक फाइल सिस्टम भी। यूनिक्स सिस्टम पर रूट नोड है, और नीचे शाखाबद्ध है। जब आप एक नया डिवाइस माउंट करते हैं, तो आप इसे पेड़ पर जोड़ रहे हैं।

आपको खुद से पूछना चाहिए: क्या डेटा इस प्रकार की संरचना में पड़ता है? डेटा संरचनाएं बनाएं जो समस्या को समझ में आती हैं और बाकी का पालन करेंगे।

जहां तक ​​आसान हो, मुझे लगता है कि यह रिश्तेदार है। क्या आप पेड़ / ग्राफ को पार करने के लिए रिकर्सिव फ़ंक्शंस के साथ अच्छे हैं? अगर आपको पेड़ को संतुलित करने की ज़रूरत है तो क्या होगा?

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

मुझे उम्मीद है कि इन संरचनाओं के बारे में आपको सोचने में मदद मिलेगी। एक पुस्तक की सिफारिश के लिए, मुझे एल्गोरिदम का परिचय के साथ जाना होगा ।

गेम और मल्टीमीडिया अनुप्रयोगों में ग्राफिक्स ड्राइंग के लिए दृश्य ग्राफ भारी पेड़ और ग्राफ का उपयोग करते हैं। नोड्स वस्तुओं को प्रस्तुत करने, परिवर्तन, नियंत्रण, समूह, ...

दृश्य ग्राफ में आमतौर पर एकाधिक परतें और विशेषताओं का अर्थ होता है जिसका अर्थ है कि आप एक निर्दिष्ट क्रम (परत) में केवल ग्राफ (विशेषताओं) के कुछ नोड को आकर्षित कर सकते हैं। आपके पास दृश्य ग्राफ के प्रकार के आधार पर इसमें दो पैरारल संरचनाएं हो सकती हैं: घोषणाएं और तत्कालता। गु

मेरे विश्वविद्यालय में ऐसी चीजों के लिए एक कोर्स है: सीएसई 326 । मुझे नहीं लगता था कि पुस्तक बहुत उपयोगी थी, लेकिन परियोजनाएं मजेदार हैं और आपको कुछ सरल संरचनाओं को लागू करने के बारे में काफी कुछ सिखाती हैं।

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

The Algorithm Design Manual contains some interesting case studies with creative use of graphs. Despite its name, the book is very readable and even entertaining at times.

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

पेड़ का उपयोग उनके पुनरावर्ती प्रकृति की वजह से कार्यात्मक प्रोग्रामिंग भाषाओं में बहुत अधिक होता है।

इसके अलावा, कई एआई समस्याओं का मॉडल करने के लिए ग्राफ और पेड़ एक अच्छा तरीका है।

खेल अक्सर दुनिया भर में पथ खोजने में सुविधा के लिए ग्राफ का उपयोग करते हैं। दुनिया भर के ग्राफ प्रतिनिधित्व में एल्गोरिदम हो सकते हैं जैसे कि चौड़ाई-पहली खोज या ए * इसमें एक मार्ग खोजने के लिए।

वे अक्सर दुनिया के भीतर इकाइयों का प्रतिनिधित्व करने के लिए पेड़ों का उपयोग करते हैं। यदि आपके पास हजारों इकाइयां हैं और किसी निश्चित स्थिति में एक को खोजने की आवश्यकता है तो सूची के माध्यम से रैखिक रूप से पुनरावृत्ति अक्षम हो सकती है, खासकर अगर आपको इसे अक्सर करने की आवश्यकता होती है। इसलिए क्षेत्र को एक पेड़ में विभाजित किया जा सकता है जिससे इसे और अधिक तेज़ी से खोजा जा सके। जैसे एक रैखिक स्थान को बाइनरी खोज (और इस प्रकार एक बाइनरी पेड़ में विभाजित) के साथ कुशलता से खोजा जा सकता है, 2 डी स्पेस को quadtree और 3 डी स्पेस एक octree में।

सर्किट आरेख।

संकलन (निर्देशित विश्वकोश ग्राफ)

मैप्स। ग्राफ के रूप में बहुत कॉम्पैक्ट।

नेटवर्क प्रवाह की समस्याएं।

विशेषज्ञ प्रणालियों (एसआईसी) के लिए निर्णय पेड़

गलती खोजने, प्रक्रिया में सुधार, सुरक्षा विश्लेषण के लिए फिशबोन आरेख। बोनस प्वाइंट्स के लिए, अपने त्रुटि पुनर्प्राप्ति कोड को ऑब्जेक्ट्स के रूप में कार्यान्वित करें जो हैं फिशबोन आरेख।

@ डेविड जॉइनर / सब:

एफडब्ल्यूआईडब्लू: एल्गोरिदम डिज़ाइन मैनुअल का एक नया संस्करण किसी भी दिन बाहर है।

प्रोफेसर स्कीनिया ने इस पुस्तक को विकसित करने के लिए पूरे पाठ्यक्रम को वेब पर भी उपलब्ध कराया है:

http://www.cs.sunysb.edu/~ algorith / वीडियो-व्याख्यान / 2007-1.html