गतिशील ग्राफ प्रोग्रामिंग

Error

डायनेमिक प्रोग्रामिंग का उपयोग करने वाले समाधानों में, जिस क्रम में डायनेमिक्स की गणना की जाती है, वह महत्वपूर्ण है (यह आवश्यक है कि जिन मूल्यों पर वर्तमान एक निर्भर करता है, उनकी गणना पहले की जाती है)।
इसलिए, यदि निर्देशित विश्वकोश रेखांकन पर गतिशील प्रोग्रामिंग का उपयोग करना आवश्यक है, तो प्रारंभ में ग्राफ के एक सामयिक छँटाई का निर्माण करना आवश्यक है। फिर निर्मित टोपोलॉजिकल सॉर्ट के क्रम में शीर्षों के माध्यम से छाँटकर गतिकी की गणना करें (समस्या के आधार पर, ट्रैवर्सल ऑर्डर या तो स्रोतों से सिंक या इसके विपरीत हो सकता है)।
 
 

यदि ग्राफ़ में चक्र हैं (कोई टोपोलॉजिकल सॉर्ट नहीं है), तो दो तरकीबें मदद कर सकती हैं:

1) डायनामिक्स n बार परिकलित करें, जहाँ n ग्राफ़ में शीर्षों की संख्या है (Ford-Bellman एल्गोरिथम के अनुरूप)। लेकिन यह स्पर्शोन्मुखता को बढ़ाता है और सामान्य रूप से शायद ही कभी कुशल होता है।

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