सुझाव दें कि विभिन्न पूर्णांक लंबाई की सड़कों से जुड़े शहरों का एक नेटवर्क है।एक एल्गोरिदम (ग्राफ - संभवतः एनपी-पूर्ण)
एक यात्री अपनी कार में एक शहर से दूसरे शहर में यात्रा करना चाहता है। हालांकि, वह यात्रा की दूरी को कम नहीं करना चाहता; इसके बजाय वह यात्रा की पेट्रोल लागत को कम करना चाहता है। पेट्रोल किसी भी शहर में खरीदा जा सकता है, हालांकि प्रत्येक शहर विभिन्न (पूर्णांक) कीमतों पर पेट्रोल की आपूर्ति करता है (इसलिए सबसे छोटा रास्ता सबसे सस्ता क्यों नहीं है)। पेट्रोल की 1 इकाई उसे दूरी की एक इकाई के लिए ड्राइव करने में सक्षम बनाता है। उसकी कार टैंक में केवल इतना पेट्रोल रख सकती है, और वह चुन सकता है कि प्रत्येक शहर में पेट्रोल की कितनी इकाइयां खरीदती हैं। न्यूनतम पेट्रोल लागत पाएं।
क्या कोई इस समस्या को हल करने के लिए उपयोग किए जाने वाले कुशल एल्गोरिदम को जानता है? यहां तक कि इस प्रकार की समस्या का नाम उपयोगी होगा ताकि मैं इसे स्वयं खोज सकूं! जाहिर है यह सबसे छोटी पथ समस्या के समान नहीं है। किसी भी अन्य सुझाव की सराहना की!
संपादित करें - वास्तविक समस्या मैंने कहा है कि < 1000 शहरों होंगे; < 10000 सड़कों; और पेट्रोल टैंक क्षमता कहीं और 1 के बीच होगी।
यह मुझे लगता है कि यह एक छोटी सी चीज की तरह दिखता है। चलो देखते हैं कि दूसरों क्या कहते हैं। –
मई मेरा सुझाव है कि आप अपना शीर्षक "ट्रैवलिंग सेल्समैन वेरिएशन" या कुछ में बदल दें। वर्तमान शीर्षक कुछ हद तक नोडस्क्रिप्ट है। – Nicolas78
यह न तो एक नापसंद समस्या है और न ही यात्रा विक्रेता समस्या है: वह ए से बी में जाना चाहता है, हर जगह नहीं। यह एक विशिष्ट ग्राफ समस्या है, जिसका नाम afaik नहीं है। –