रैंडम सर्च हेयूरिस्टिक्स और मोटर जहाज

एक बार मैंने प्रोग्रामिंग में heuristics के उपयोग पर एक बड़ा लेख लिखा था, लेकिन आज मैं एक छोटा व्यावहारिक उदाहरण देना चाहता हूं। इस गर्मियों में मैं मास्को - रोस्तोव-ऑन-डॉन - मास्को मार्ग पर एक जहाज पर रवाना हुआ , और देखा कि हर शाम क्रूज़ निर्देशक बस द्वारा पर्यटक समूहों के लिए सबसे अच्छी बैठने की व्यवस्था खोजने की कोशिश करता है। यह कार्य इतना कठिन नहीं है, लेकिन इसके समाधान पर दिन में कम से कम 15 मिनट का समय लगता है। बेशक, मैंने इस प्रक्रिया को स्वचालित करने की कोशिश की।
लेकिन, मेरे समाधान का वर्णन करने से पहले, समस्या को अधिक सटीक रूप से तैयार करना आवश्यक है। क्रूज की शुरुआत में, सभी पर्यटकों को कई भ्रमण समूहों में विभाजित किया गया था (इस मामले में 15 समूह थे), जबकि प्रत्येक समूह में 10 से अधिक लोग नहीं थे। सभी समूहों को क्रम में क्रमांकित किया गया था, और समूह की परिणामी सूची क्रूज के बहुत अंत तक नहीं बदली थी। यह सूची कुछ इस तरह दिखी:
हर दिन, पर्यटक क्रूज निदेशक को इस बारे में सूचित करते हैं कि वे किस भ्रमण पर जाने की योजना बना रहे हैं। हर कोई जो मुख्य दौरे पर जाने की योजना नहीं बनाता है, उसे इस सूची से हटा दिया जाता है। यह एक संशोधित सूची के साथ है जिसे हमें काम करना है। क्रूज़ डायरेक्टर मानता है कि कितने लोग भ्रमण पर जाते हैं (आमतौर पर 100-120 लोग) और बसों के लिए एक उपयुक्त क्रम बनाते हैं। किनारे पर यात्रा करने वाली एजेंसियां ​​इस आदेश को स्वीकार करती हैं और निम्नलिखित जानकारी देती हैं: "घाट पर आपको 48, 48 और 50 सीटों वाली तीन बसें मिलेंगी।" परिणामस्वरूप, कार्य निम्नानुसार है: बसों पर पर्यटकों को बैठाना आवश्यक है, निम्नलिखित आवश्यकताओं को देखते हुए (महत्व के क्रम में):
1. समूहों को विभाजित न करें;
2. बसों को यथासंभव भरें;
3. यह सलाह दी जाती है कि एक ही बस में बैठे समूह एक पंक्ति में जाएं। यानी पहली बस - समूह 1-5, दूसरी बस 6-10, आदि।
स्वचालन की ओर पहला कदम एक्सेल और ऐड-ऑन "समाधान खोज" का उपयोग करके बनाया गया था (मेरे आश्चर्य के लिए, बहुत कम लोग इस सेटिंग के बारे में जानते हैं, हालांकि यह बात अविश्वसनीय रूप से उपयोगी है)।
पहली आवश्यकता, बेशक, पूरी हो गई थी, लेकिन दूसरी और तीसरी आवश्यकताओं को भूलना पड़ा। यह देखते हुए कि एक पुराने लैपटॉप पर एक समाधान की खोज में लगभग 15 सेकंड लगे, यह आपकी बाइक लिखने का फैसला किया गया था। लेकिन यहां फिर से सवाल उठे, यह सब कैसे करना है: सिंप्लेक्स विधि, गतिशील प्रोग्रामिंग, शाखा और बाध्य विधि, हेयुरिस्टिक? निश्चित रूप से कुछ प्रकार के जटिल एल्गोरिथ्म हैं जो इस समस्या को हल करने में मदद करेंगे, लेकिन छुट्टी पर कुछ कठिन लिखने के लिए, और फिर इसे एक छोटे स्क्रीन के साथ लैपटॉप पर डिबग करें? मैंने किसी तरह का अनुमान लगाने की कोशिश की। मैंने तुरंत थोड़े से विचार के बाद पहाड़ी पर चढ़ाई को स्थगित कर दिया, साथ ही न्यूनतम लागत और संतुलित लाभ के उत्तराधिकार भी।
और फिर मुझे यादृच्छिक खोज हेयुरिस्टिक याद आया। सच कहूं, तो मैंने पहले कभी इसका इस्तेमाल नहीं किया था, और बहुत यकीन था कि एक यादृच्छिक खोज एक प्रभावी समाधान का नेतृत्व नहीं करेगी। लेकिन जिज्ञासा प्रबल रही। परिणामस्वरूप, निम्नलिखित सीटिंग एल्गोरिथ्म प्राप्त किया गया था:
1. एक यादृच्छिक समूह और एक यादृच्छिक बस चुनें
2. जांचें कि क्या हम चयनित समूह को चयनित बस में रख सकते हैं (देखें कि क्या यह समूह किसी अन्य बस में बैठा है, और यदि पर्याप्त सीटें हैं)
2.1। यदि हम नहीं कर सकते, तो हम एक के बाद एक असफल प्रयासों के काउंटर को बढ़ाते हैं
2.2। यदि हम कर सकते हैं, तो असफल प्रयासों के काउंटर को रीसेट करें
3. यदि असफल प्रयासों की संख्या 50 से अधिक हो गई, तो हम लूप से बाहर निकल जाते हैं, अन्यथा चरण 1 पर जाएं
4. जांचें कि क्या सभी समूह बैठे हैं
4.1। यदि यह सब है, तो बसों में खाली सीटों की संख्या के बीच अधिकतम अंतर की गणना करें (यह वह संख्या है जिसे अनुमान माना जाएगा)
4.2। यदि सभी नहीं, तो असफल बैठने की व्यवस्था की रिपोर्ट करें।
इस प्रक्रिया को सैकड़ों बार करते हुए, हम सबसे अच्छी श्रेणी के बैठने की योजना चुन सकते हैं। इस एल्गोरिथ्म ने आश्चर्यजनक रूप से अच्छी तरह से काम किया। आवश्यकताओं के कम से कम पहले और दूसरे पैराग्राफ पूरी तरह से मिले थे।
तीसरे बिंदु को पूरा करने के लिए, एल्गोरिथ्म में एक छोटा बदलाव आवश्यक है। बैठने की एल्गोरिथ्म की शुरुआत से पहले ही, हम प्रत्येक बस (1-5,6-10,11-15) में 5 समूह लगाएंगे, और बैठने का प्रदर्शन करेंगे। यदि वह सफल हुई, तो हमें सबसे अच्छा स्कोर याद है, और परिणाम प्रदर्शित होता है। फिर हम प्रत्येक बस में 4 समूह रखने की कोशिश करते हैं (1-4, 5-8, ...), और फिर से हम बैठने का प्रदर्शन करते हैं। यदि प्राप्त अनुमान पिछले चरण की तुलना में बेहतर निकला, तो इसे याद रखें और फिर से परिणाम प्रदर्शित करें। फिर हम शुरुआत में 3 समूहों, 2, 1 प्रत्येक में बस रखने की कोशिश करते हैं, और अंत में, हम बिना किसी प्रारंभिक जानकारी के बैठने की प्रक्रिया करते हैं। यदि किसी स्तर पर, मूल्यांकन में सुधार हुआ है, तो परिणामस्वरूप समाधान प्रदर्शित होता है।
कार्रवाई, ज़ाहिर है, अधिक किया जाता है, लेकिन प्राप्त परिणामों का मूल्य बहुत अधिक है। अंत में मैं कार्यक्रम का एक छोटा सा उदाहरण दूंगा:

यह स्पष्ट है कि आप में से अधिकांश पहले से ही यादृच्छिक खोज के बारे में जानते हैं, लेकिन अचानक इस पोस्ट को उन लोगों द्वारा पढ़ा गया, जो इसके बारे में नहीं जानते हैं, या किसी कारण से इसका उपयोग करने से डरते थे। मुझे उम्मीद है कि अब, इस अनुमान को थोड़ा बेहतर सीखा जा सकता है, आप कम से कम अपनी कुछ समस्याओं के समाधान को थोड़ा सरल कर सकते हैं।