Search Space को समझदारी से छोटा करें

कभी-कभी पूर्ण खोज बस थोड़ी-सी बहुत धीमी होती है। उपाय है कि बिना कोई सही उत्तर खोए, जिस हिस्से को आप खोजते हैं उसे छोटा करें। 🙂

एक शक्तिशाली उपाय है कि एक चर को लूप में लेकर तय करें और फिर बाकी समस्या को तेज़ी से हल करें। इससे पूरी खोज की जगह कई छोटी खोजें करनी पड़ती हैं।

पहला तत्व तय करें, फिर उसके साथी को द्विआधारी खोज या हैश के माध्यम से खोजें। इससे O(n²) की स्कैनिंग लगभग O(n log n) में बदल जाती है।

खोज के दौरान ऐसे किसी भी मार्ग पर तुरंत रुक जाएँ जो अब तक के सर्वोत्तम उत्तर को नहीं पछाड़ सकता। जिस शाखा को छोड़ दिया जाए, उसे खोजने में कोई समय नहीं लगता।

पहले क्रमबद्ध करने से अक्सर लूप को जल्दी रोकना संभव हो जाता है। जब values किसी सीमा से आगे निकल जाएँ, तो आप जान जाते हैं कि बाकी values उपयोगी नहीं हो सकतीं।

यदि दो तत्वों की अदला-बदली से वही परिणाम मिलता है, तो केवल एक क्रम खोजें। हर स्थिति को एक बार गिनने से आपका काम आधा या उससे भी कम हो सकता है।

तत्वों को दो हिस्सों में बाँटें, दोनों की गणना करें और फिर उन्हें मिलाएँ। इससे 2^n की खोज घटकर लगभग 2^(n/2) काम रह जाती है।

यदि वही छोटी समस्या फिर दिखाई दे, तो उसका परिणाम सहेजकर फिर इस्तेमाल करें। परिणाम याद रखने की यह तकनीक खोज से दोहराई जाने वाली पूरी शाखाएँ हटा देती है।

किसी शाखा के लिए एक आशावादी सीमा निकालें। यदि वहाँ का सबसे अच्छा संभावित परिणाम भी हारता है, तो उस शाखा को पूरी तरह छोड़ दें और समय बचाएँ।

हर कटौती सुरक्षित होनी चाहिए: केवल उन्हीं मार्गों को हटाएँ जो वास्तव में जीत नहीं सकते। यह सुनिश्चित करने के लिए साधारण पूर्ण खोज से परीक्षण करें कि कोई उत्तर छूटा नहीं है।

इन उपायों का सहारा तब लें जब पूर्ण खोज सीमा के करीब हो, लेकिन धीमी हो। कोई चर तय करें, शाखाएँ हटाएँ या समस्या बाँटें; खोज अक्सर समय-सीमा में आ जाती है।

किसी चर को तय करके, निराशाजनक शाखाएँ हटाकर, सममिति का लाभ उठाकर या बीच से मिलान करके खोज को छोटा करें। हर कटौती सुरक्षित रखें। 🚀