एल्गोरिदम समस्या वर्गीकरण

Question

अलगो प्रतियोगिता साइटों में से एक में बड़ी समस्या है। मैं इसे 5 दिनों के लिए हल करने की कोशिश कर रहा हूं। मैं आपको यह मेरे लिए हल करने के लिए नहीं कह रहा हूं, क्योंकि मैं एल्गोरिदम के लिए नया हूं, मैं आपको इस प्रकार की समस्या के वर्गीकरण के साथ मेरी मदद करने के लिए कहूंगा, क्या किसी ने इस तरह की समस्याओं को हल किया है, एनपी की समस्या क्या है या नहीं। कृपया नहीं लगता कि यह है कि मैं मेरे लिए यह हल करने के लिए आप पूछ रहे हैं, मेरा उद्देश्य एल्गोरिदम जानने के लिए बस है और इस समस्या को जो मेरे लिए काफी मुश्किल है:

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

इनपुट विशिष्टता आपके प्रोग्राम को एक और केवल एक कमांड लेना चाहिए लाइन तर्क: इनपुट फ़ाइल (argv में उत्तीर्ण, तर्क, तर्क भाषा के आधार पर)। इनपुट फ़ाइल को इस तरह फ़ॉर्मेट है: n हवाई अड्डों की संख्या n निम्नलिखित लाइनों प्रत्येक 2 चल बिन्दु मान xi यी ith हवाई अड्डे के निर्देशांक निम्न पंक्ति शामिल प्रतिनिधित्व करने होते हैं:

पहली पंक्ति एक पूर्णांक शामिल मामलों की संख्या पी का विश्लेषण करने के निम्नलिखित पी लाइनों हर एक पूर्णांक गी आवश्यक गैस स्टेशनों

आउटपुट निर्दिष्टीकरण की संख्या देने होते हैं (पी हमेशा कम से कम 5 है): आप प्रोग्राम चाहिए उत्पादन लिए परिणाम मानक आउटपुट (printf, प्रिंट, गूंज, लिखें): आपका आउटपुट में पी लाइनें होनी चाहिए, प्रत्येक लाइन जीजे निर्देशांक गैस स्टेशनों के xj, yj को प्रदान करती है। आपके समाधान स्कोर को समाधान की गुणवत्ता से मापा जाएगा। समाधान की गुणवत्ता कुल दूरी से मापा जाता है, कुल दूरी डी प्रत्येक हवाई अड्डे से अपने निकटतम गैस स्टेशन तक वर्ग दूरी के की वर्ग रूट है। कुल दूरी डी को कम करें, आपका स्कोर जितना अधिक होगा।

Answer 1

मामले gi = 1 के लिए। यह आसान है - आप केवल गुरुत्वाकर्षण/द्रव्यमान के केंद्र (सभी हवाई अड्डों से, हेक भी आप प्रत्येक हवाई अड्डे को ईंधन की मात्रा के साथ वजन कम कर सकते हैं, इसलिए यह ईंधन स्टेशन को भारी उपभोग करने वाले हवाई अड्डों के करीब रखेगा, लेकिन इस तरह आवश्यक नहीं है कि आप सभी वही वज़न दें)। इससे एक इष्टतम समाधान मिलेगा (यह भी एक अच्छा उदाहरण है कि नॉनलाइनर, ग्लोबल ऑप्टिमाइज़ेशन एनपी हार्ड को जरूरी नहीं है)।

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

Answer 2

यह समस्या कैनोनिकल असुरक्षित के-साधन वर्गीकरण समस्या है। पूर्ण विवरण के लिए यहां देखें: http://en.wikipedia.org/wiki/K-means_clustering

त्वरित संकेत के लिए (यदि आप पूर्ण spoilers से बचना चाहते हैं) के-साधन बस आपके गैस स्टेशनों के लिए यादृच्छिक स्थानों को चुनकर शुरू होता है। यह एक ही समय में प्रत्येक व्यक्तिगत गैस स्टेशन की लागत को कम करके उसके बाद प्रत्येक पुनरावृत्ति समाधान को बेहतर बनाता है। यह हवाई अड्डे के सेट के लिए अपनी लागत को कम करने के लक्ष्य के साथ एक गैस स्टेशन को स्थानांतरित करके करता है जो वर्तमान में ईंधन है।

Answer 3

यह Facility location problem का एक संस्करण है। इष्टतम स्थानों को ढूँढना एनपी-हार्ड है, लेकिन इष्टतम की निश्चित गारंटीकृत दूरी के भीतर समाधान खोजने के लिए कई सन्निकटन विधियों को लागू किया जा सकता है। वैकल्पिक रूप से, क्लस्टरिंग जैसी मुलायम विधियों का उपयोग अन्य उत्तरों में प्रस्तावित किया जा सकता है।