बीच में मिलें
बीच में मिलें - अनुकूलित करने का एक तरीका समाधान, जिसमें मूल समस्या को दो हिस्सों में तोड़ना, प्रत्येक को स्वतंत्र रूप से हल करना और फिर आधे हिस्सों के समाधानों को मिलाकर मूल समस्या का समाधान प्राप्त करना शामिल है।
तदनुसार, अगर दो शर्तें पूरी होती हैं, तो
meet-in-the-middle का उपयोग करना समझ में आता है।
1) समस्या के आधे हिस्से को हल करने के लिए आवश्यक समय पूरी समस्या को हल करने के समय की तुलना में विषम रूप से कम है।
2) आधी-अधूरी समस्याओं को हल करके, कोई भी मूल पूरी समस्या का समाधान प्राप्त कर सकता है, और साथ ही, पूरी समस्या को हल करने की तुलना में विषम रूप से तेजी से।
उदाहरण
मान लीजिए पूर्णांक
A,
B,
C और
D की चार सरणियाँ हैं। प्रत्येक सरणी से ठीक एक संख्या का चयन करना आवश्यक है ताकि इन संख्याओं का योग शून्य के बराबर हो। आप सरल समाधान का उपयोग कर सकते हैं, अर्थात्, बस सभी संभावित विकल्पों की गणना करें। यह
O(n4) के लिए काम करेगा।
हालांकि, हम
meet-in-the-middle का उपयोग कर सकते हैं।
ध्यान दें कि
a + b + c + d = 0 (a + b) = -(c + d) के बराबर है।
आइए कार्य को दो हिस्सों में विभाजित करें, अर्थात्, पहली छमाही में हम केवल
A और
B का उपयोग करेंगे, और दूसरी छमाही में केवल
C > और <कोड>डी।
आइए पहली छमाही में सभी संभावित
(a + b) विकल्पों पर पुनरावृति करें और सभी मानों को एक हैश तालिका (
unordered_map,
HashMap या पसंद है।) यह O(n2) में काम करता है।
अब हम दूसरी छमाही में (c + d) सभी संभावित विकल्पों पर पुनरावृति करेंगे। एक निश्चित विकल्प पर विचार करते समय, हम जाँच करेंगे कि क्या हैश तालिका में विपरीत चिह्न के वर्तमान योग से जुड़ा कोई मान है (तब हमें दो पारस्परिक मिले जो शून्य तक जुड़ते हैं)। यह भाग O(n2) में भी काम करता है।
हमारे यहाँ एक अलग "उत्तर मर्ज" चरण नहीं है; एक में, हमने प्रत्येक भाग को हल करने के क्रम में ऐसा किया। अधिकांश कार्यों में एक जैसी स्थिति होगी।
हमें O(n2) में meet-in-the-middle का उपयोग करके एक समाधान मिला।
यह ध्यान देने योग्य है कि एक्सपोनेंशियल सॉल्यूशंस को ऑप्टिमाइज़ करते समय meet-in-the-middle का उपयोग अक्सर किया जाता है, जो रनिंग टाइम को महत्वपूर्ण रूप से प्रभावित करता है।