कुछ ग्राफ परिचालनों के लिए सबसे आसान एल्गोरिदम के सुझाव

Question

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

• सूची ग्राफ नेटवर्क में सभी उपयोगकर्ताओं को एक दूरी एक्स दिया
• सूची ग्राफ नेटवर्क में सभी उपयोगकर्ताओं को एक दूरी एक्स और प्रकार दिया:

  संचालन मैं करने की आवश्यकता होगी इस प्रकार है संबंध के

• संबंध का एक प्रकार
• ग्राफ नेटवर्क
• मो की गणना पर 2 उपयोगकर्ताओं के बीच अधिकतम दूरी की गणना दिए गए ग्राफ नेटवर्क पर 2 उपयोगकर्ताओं के बीच सबसे कम पथ की गणना करें ग्राफ नेटवर्क

मेरी ग्राफ़ कार्यान्वयन बारे में कुछ नोट पर सेंट दूर जुड़े उपयोगकर्ताओं:

• बढ़त नोड, 2 गुण है एक प्रकार char और एक अन्य int की है। वे क्रमशः संबंध और वजन के प्रकार का प्रतिनिधित्व करते हैं।
• ग्राफ़ को लंबवत सूचियों के साथ कार्यान्वित किया गया है, दोनों कोने और किनारों के लिए। मेरा मतलब है, प्रत्येक वर्टेक्स अगले एक को इंगित करता है और प्रत्येक कशेरुक भी एक अलग लिंक्ड सूची के सिर को इंगित करता है, उस विशिष्ट चरम के किनारों पर।

क्या मैं क्या मैं क्या करने की जरूरत के बारे में पता:

• मैं, जैसा कि मैंने ऊपर कहा है कि अगर यह सबसे आसान है पता नहीं है, लेकिन 2 उपयोगकर्ताओं के बीच सबसे कम पथ के लिए, मेरा मानना ​​है कि डिज्कस्ट्रा एल्गोरिदम वह है जो लोग अक्सर अनुशंसा करते हैं, इसलिए मुझे लगता है कि मैं इसके साथ जा रहा हूं।
  • मैं खोज रहा था और खोज और मैं इसे कठिन इस एल्गोरिथ्म लागू करने के लिए की खोज कर रहा हूँ, किसी को भी किसी भी ट्यूटोरियल या कुछ और समझने के लिए तो मैं इस एल्गोरिथ्म अपने आप लागू कर सकते हैं आसान का पता है? यदि संभव हो, सी स्रोत कोड उदाहरणों के साथ, यह बहुत मदद करेगा। मैं गणित नोटेशन के साथ कई उदाहरण देखता हूं लेकिन यह मुझे और भी भ्रमित करता है।
  • क्या आपको लगता है कि यदि मैं लिंक वजन और संबंध प्रकार का प्रतिनिधित्व करने के लिए ग्राफ को एक आसन्न मैट्रिक्स में "रूपांतरित" करता हूं तो इससे मदद मिलेगी? क्या लिंक्ड सूचियों के बजाय उस पर एल्गोरिदम निष्पादित करना आसान होगा? आवश्यकता होने पर रूपांतरण को करने के लिए मैं आसानी से एक फ़ंक्शन को कार्यान्वित कर सकता था। मैं यह कह रहा हूं क्योंकि मुझे लगता है कि विषय के बारे में कुछ पेज पढ़ने के बाद यह आसान होगा, लेकिन मैं गलत हो सकता था।
• मेरे पास अन्य 4 संचालन, सुझावों के बारे में कोई विचार नहीं है?

Answer 1

सूची ग्राफ नेटवर्क में सभी उपयोगकर्ताओं को एक दूरी एक्स

क्या से एक दूरी X दिया? एक शुरुआती नोड या दूरी के बीच X से? क्या आप एक उदाहरण दे सकते हैं? यह एक बीएफ खोज या Dijkstra चलाने के रूप में सरल हो सकता है या नहीं हो सकता है।

मान लें कि आप एक निश्चित नोड से शुरू करते हैं और शुरुआती नोड से X दूरी वाले सभी नोड्स को सूचीबद्ध करना चाहते हैं, बस शुरुआती नोड से BFS चलाएं। जब आप कतार में एक नया नोड डालने वाले होते हैं, तो जांच करें कि शुरुआती नोड से नोड तक की दूरी, जिसे आप नोड से किनारे के वजन से नया नोड डालना चाहते हैं, जिससे आप नया नोड डालना चाहते हैं नया नोड < = X है। यदि यह सख्ती से कम है, तो नया नोड डालें और यदि यह बराबर है तो बस नोड को मुद्रित करें (और केवल तभी डालें यदि आप 0 के किनारे वजन के रूप में भी हो)।

सूची एक दूरी एक्स दिए गए ग्राफ नेटवर्क में सभी उपयोगकर्ताओं और संबंध के प्रकार

ऊपर देखें। बस बीएफएस में संबंध के प्रकार में कारक: यदि माता-पिता का प्रकार नोड के मुकाबले अलग है तो आप कतार में डालने की कोशिश कर रहे हैं, इसे सम्मिलित न करें।

संबंध का एक प्रकार दिए गए ग्राफ नेटवर्क पर 2 उपयोगकर्ताओं के बीच सबसे कम पथ की गणना

एल्गोरिथ्म के लिए कई कारकों पर निर्भर करता है:

• कितनी बार आप की गणना करने की आवश्यकता होगी इस?
• आपके पास कितने नोड्स हैं?

चूंकि आप आसान चाहते हैं, सबसे आसान रॉय-फ्लॉइड और डिजस्ट्रा हैं।

• रॉय फ्लोयड का उपयोग नोड्स की संख्या में घन, तो अक्षम है। केवल इसका उपयोग करें यदि आप इसे एक बार चलाने के लिए बर्दाश्त कर सकते हैं और फिर O (1) में प्रत्येक क्वेरी का उत्तर दे सकते हैं। अगर आप मेमोरी में आसन्न मैट्रिक्स को रखने के लिए बर्दाश्त कर सकते हैं तो इसका इस्तेमाल करें।
• यदि आप इसे सरल रखना चाहते हैं तो डिजस्ट्रा नोड्स की संख्या में वर्गबद्ध है, लेकिन आपको इसे दो बार नोड्स के बीच की दूरी की गणना करना होगा। यदि आप डिजस्ट्रा का उपयोग करना चाहते हैं, तो आसन्न सूची का उपयोग करें। Roy-Floyd और Dijkstra_1, Dijkstra_2:

यहाँ सी कार्यान्वयन हैं। आप "<algorithm name> c implementation" के साथ Google पर बहुत कुछ पा सकते हैं।

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

एक और विकल्प प्रत्येक क्वेरी पर Bellman-Ford एल्गोरिदम का उपयोग करना है, जो आपको O(Nodes*Edges) रनटाइम प्रति क्वेरी देगा। हालांकि, यह एक बड़ा अतिवृद्धि है यदि आप इसे लागू नहीं करते हैं क्योंकि विकिपीडिया आपको बताता है। इसके बजाय, बीएफएस में इस्तेमाल किए गए एक के समान कतार का उपयोग करें। जब भी कोई नोड स्रोत से इसकी दूरी को अद्यतन करता है, तो उस नोड को कतार में वापस डालें। यह अभ्यास में बहुत तेज होगा, और नकारात्मक वजन के लिए भी काम करेगा। मेरा सुझाव है कि आप इस या डिजस्ट्रा को ढेर के साथ उपयोग करें, क्योंकि क्लासिकल डिजस्ट्रा 18 000 नोड्स पर लंबा समय ले सकता है। सभी संभावनाओं कोशिश करते हैं और सबसे लंबे समय तक रास्ता मिल रखें:

ग्राफ नेटवर्क

सबसे आसान तरीका बैक ट्रैकिंग का उपयोग है पर 2 उपयोगकर्ताओं के बीच अधिकतम दूरी की गणना। This is NP-complete, इसलिए बहुपद समाधान मौजूद नहीं हैं।

यदि आपके पास 18 000 नोड्स हैं, तो यह वास्तव में बुरा है, मुझे कोई एल्गोरिदम (सरल या अन्यथा) नहीं पता है जो इतने सारे नोड्स के लिए उचित रूप से काम करेगा। लालची एल्गोरिदम का उपयोग करके इसे अनुमानित करने पर विचार करें।या शायद आपके ग्राफ में कुछ गुण हैं जिनका आप लाभ उठा सकते हैं। उदाहरण के लिए, क्या यह एक डीएजी (निर्देशित एसाइक्लिक ग्राफ) है?

ग्राफ नेटवर्क

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

फिर से, यह आपके नोड्स और किनारों की संख्या के साथ तेजी से करना बहुत मुश्किल है। मुझे डर है कि आप पिछले दो प्रश्नों पर भाग्य से बाहर हैं, जब तक आपके ग्राफ में विशेष गुण नहीं हैं जिनका शोषण किया जा सकता है।

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

नहीं, आसन्न मैट्रिक्स और रॉय-फ्लॉइड एक बहुत ही बुरा विचार है जब तक कि आपका एप्लिकेशन सुपरकंप्यूटर को लक्षित न करे।

Answer 2

यह मानता है कि O(E log V) एक स्वीकार्य चलने का समय है, यदि आप कुछ ऑनलाइन कर रहे हैं, तो यह नहीं हो सकता है, और इसके लिए कुछ उच्च संचालित मशीनरी की आवश्यकता होगी।

• सूची ग्राफ नेटवर्क में सभी उपयोगकर्ताओं को एक दूरी एक्स

Djikstra's algorithm इस के लिए अच्छा है को देखते हुए, एक समय का उपयोग करने के लिए। आप सभी शीर्षकों (या बेहतर अभी तक, सॉर्ट और बाइनरी खोज) के माध्यम से एक रैखिक स्कैन के साथ भविष्य के उपयोग के लिए परिणाम बचा सकते हैं।

• सूची एक दूरी एक्स और संबंध के प्रकार

लगभग एक ही ऊपर के रूप में हो सकता है दिए गए ग्राफ नेटवर्क में सभी उपयोगकर्ताओं - बस कुछ फ़ंक्शन का उपयोग करें जहां वजन अनंत हो सकता है अगर यह है सही संबंध नहीं।

• संबंध का एक प्रकार

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

• ग्राफ नेटवर्क

Longest path पर 2 उपयोगकर्ताओं के बीच अधिकतम दूरी की गणना एक NP-complete problem है।

• ग्राफ नेटवर्क

पर सबसे दूर जुड़ा उपयोगकर्ताओं की गणना यह ग्राफ है, जो आप Math World पर के बारे में पढ़ सकते हैं का व्यास है।

आसन्नता सूची बनाम निकटता मैट्रिक्स प्रश्न के लिए, यह इस बात पर निर्भर करता है कि आपका ग्राफ कितना घनी आबादी वाला है। साथ ही, यदि आप परिणाम कैश करना चाहते हैं, तो मैट्रिक्स जाने का तरीका हो सकता है।

Answer 3

दो नोड्स के बीच सबसे कम पथ की गणना करने के लिए सबसे सरल एल्गोरिदम Floyd-Warshall है। यह सिर्फ लूप के लिए तीन गुना है; बस।

यह सभी -pairs O(N^3) में कम से कम पथ की गणना करता है, तो यह आवश्यकता से अधिक काम कर सकते हैं, और एक समय लगेगा अगर N बहुत बड़ा है।