यात्रा की योजना

Question

यदि आपके पास देश के लिए पूर्ण बस शेड्यूल है, तो आप अधिकतम संख्या में लोगों को कैसे पता लगा सकते हैं जो दो निर्दिष्ट स्टॉप के बीच 1 दिन में किए जा सकते हैं?

मुझे लगता है कि एक बस अनुसूची आपको हर बस स्टॉप के लिए छोड़ने और आने वाले समय की पूरी सूची देता है और प्रत्येक बस की क्षमता भी देता है। आपको प्रश्न में शुरुआत और अंतराल दिया जाता है।

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

इस समस्या को हल करने में सबसे तेज़ क्या है? उदाहरण के लिए, मान लीजिए कि एम शहरों के लिए मुझे कुल एन रिकॉर्ड दिए गए हैं; मार्ग रिकॉर्ड आरᵢ में ​​एक संख्या Kᵢ, एक क्षमता सीᵢ, और केᵢ शहर संख्या, Kᵢ आगमन के समय, और Kᵢ प्रस्थान के समय शामिल हैं। (आर आगमन में पहला आगमन समय और अंतिम प्रस्थान समय अप्रासंगिक है।) क्या एक चौथाई खोज कार्यक्रम ओ (एम * एन) समय में प्रश्न हल कर सकता है?

Answer 1

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

आपका स्रोत नोड आपके प्रारंभ स्थान पर शून्य समय पर आगमन नोड होना चाहिए, आपके सिंक नोड को आपके अंतिम स्थान पर समाप्ति समय पर प्रस्थान नोड होना चाहिए।