अल्पमहिष्ठ/Maximin रास्तों को समझना (फ्लोयड-Warshall)

Question

मैं सभी जोड़े कम से कम पथ समस्या को हल करने फ्लोयड-Warshall-एल्गोरिथ्म क्रियान्वित किया है। अब मुझे पता चला कि मैं आसान संशोधन के साथ मिनीमैक्स या मैक्सिमिन पथ की गणना भी कर सकता हूं। लेकिन मुझे समझ में नहीं आता कि परिणाम क्या है (क्या एक मिनीमैक्स पथ है)। मुझे वेब पर कुछ explanations मिले, लेकिन वे मुझे भ्रमित कर रहे हैं।

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

Maximin - Minimax से दूसरी तरह के आसपास - यहाँ आप समस्याओं जहां पथ एक मार्ग के किनारे कम से कम लागत अधिकतम खोजने की जरूरत है।

किसी को एक अन्य स्पष्टीकरण या एक उदाहरण देने की कोशिश कर सकते हैं?

Answer 1

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

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

अल्पमहिष्ठ पथ विपरीत विचार का प्रतिनिधित्व करता है।

आशा है कि इससे मदद मिलती है!