बिन पैकिंग समस्या

घर बदलते समय आप एक के बाद एक डिब्बे भरते हैं और सोचते हैं कि क्या किसी समझदारी भरे क्रम से कम डिब्बे लगते। यही बिन पैकिंग समस्या है, और यह अपनी कठिनाई के लिए मशहूर है: कंप्यूटर भी बड़े इनपुट के लिए सबसे कम बिन केवल चतुर खोज से ही ढूँढ़ पाते हैं। फिर भी, सरल नियम हैरानी की हद तक क़रीब पहुँचते हैं।

बराबर ऊँचाई के बिन, जिनमें अलग-अलग आकार की रंगीन वस्तुएँ एक के ऊपर एक रखी हैं, और उनके ऊपर और वस्तुएँ इंतज़ार कर रही हैं
बराबर ऊँचाई के बिन, जिनमें अलग-अलग आकार की रंगीन वस्तुएँ एक के ऊपर एक रखी हैं, और उनके ऊपर और वस्तुएँ इंतज़ार कर रही हैं

समस्या

आकार वाली वस्तुएँ और ऐसे बिन दिए गए हैं जिनमें से हर एक में बराबर मात्रा समाती है; हर वस्तु को किसी बिन में ऐसे रखें कि कोई बिन छलके नहीं, और जितने हो सकें उतने कम बिन लगें। आकार वज़न, लंबाई, अवधि या फ़ाइल के आकार को दर्शा सकते हैं। यह बारिश वाली दोपहर की पहेली जैसी लगती है, पर यह NP-हार्ड है: ऐसी कोई विधि ज्ञात नहीं जो हर इनपुट के लिए सबसे कम बिन जल्दी ढूँढ़ ले।

तेज़ नियम

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

पहले छाँटें

मुश्किल बड़ी वस्तुएँ होती हैं, क्योंकि उन्हें बहुत खाली जगह चाहिए। वस्तुओं को सबसे बड़ी से सबसे छोटी तक छाँटकर फिर फ़र्स्ट फ़िट या बेस्ट फ़िट लगाने से बड़ी वस्तुएँ तब रखी जाती हैं जब बिन अभी खाली हों, और बची जगहें छोटी वस्तुओं से भरती हैं। फ़र्स्ट फ़िट डिक्रीज़िंग कभी भी सबसे कम बिनों के 11/9 गुना और एक स्थिरांक से ज़्यादा बिन नहीं लगाता, जबकि बिना छँटी वस्तुओं पर फ़र्स्ट फ़िट के लिए यह 1.7 गुना है।

एक उदाहरण

आकार 10 के बिन और वस्तुएँ 2, 3, 2, 1, 3, 4, 5, 6, 7 और 7 लें, जिनका जोड़ 40 है। फ़र्स्ट फ़िट 2, 3, 2 और 1 को पहले बिन में और 3 और 4 को दूसरे में रखता है, और फिर 5, 6, 7 और 7 में से हर एक को अपना अलग बिन चाहिए: 6 बिन। सबसे बड़ी से शुरू करके छाँटने पर, फ़र्स्ट फ़िट डिक्रीज़िंग 7 + 3, 7 + 3, 6 + 4 और 5 + 2 + 2 + 1 बनाता है: 4 भरे बिन, जो निचली सीमा 40 / 10 = 4 के बराबर है।

सबसे कम बिन ढूँढ़ना

कम वस्तुओं के लिए सटीक उत्तर उपसमुच्चयों पर गतिशील प्रोग्रामिंग से निकाला जा सकता है: वस्तुओं के हर समुच्चय के लिए उसे रखने वाले सबसे कम बिन और सबसे खाली आख़िरी बिन, एक वस्तु कम वाले समुच्चयों से बनाए जाते हैं। इसमें n वस्तुओं के लिए लगभग 2ⁿ·n चरण लगते हैं। बड़े उदाहरण ब्रांच एंड बाउंड या पूर्णांक प्रोग्रामिंग से हल किए जाते हैं, और निचली सीमा बताती है कि कोई पैकिंग सबसे अच्छी से कितनी दूर हो सकती है।

यह कहाँ इस्तेमाल होती है

ट्रक और कंटेनर लादना, मानक लंबाई के पाइप या कागज़ के रोल से कम से कम बर्बादी के साथ टुकड़े काटना (कटिंग स्टॉक समस्या), वर्चुअल मशीनों को सर्वरों पर रखना, और फ़ाइलों को डिस्क पर रखना, ये सब बिन पैकिंग समस्याएँ हैं। दो और तीन आयामों में, संख्याओं की जगह डिब्बों के साथ, समस्या और भी कठिन है।

अक्सर पूछे जाने वाले प्रश्न

ऑनलाइन और ऑफ़लाइन बिन पैकिंग में क्या अंतर है?

ऑनलाइन में हर वस्तु को आते ही रखना होता है, बाक़ी वस्तुओं को जाने बिना; नेक्स्ट फ़िट, फ़र्स्ट फ़िट और बेस्ट फ़िट ऐसे ही काम करते हैं। ऑफ़लाइन में सभी वस्तुएँ पहले से पता होती हैं, इसलिए उन्हें पहले छाँटा जा सकता है, जैसा फ़र्स्ट फ़िट डिक्रीज़िंग करता है।

फ़र्स्ट फ़िट डिक्रीज़िंग कितना क़रीब पहुँचता है?

यह ज़्यादा से ज़्यादा सबसे कम बिनों के 11/9 गुना और एक बिन का 6/9 हिस्सा लगाता है; 2007 में György Dósa ने साबित किया कि यह सीमा बिल्कुल सटीक है। सामान्य इनपुट पर यह आमतौर पर इष्टतम होता है या बस एक बिन ज़्यादा लगाता है।

क्या बिन पैकिंग और नैपसैक समस्या एक ही हैं?

ये जुड़ी हुई हैं पर अलग हैं। नैपसैक एक थैले को सबसे क़ीमती वस्तुओं से भरता है; बिन पैकिंग हर वस्तु को जितने हो सकें उतने कम थैलों में रखती है। सटीक बिन पैकिंग सॉल्वर अक्सर नैपसैक जैसी समस्याएँ बार-बार हल करके काम करते हैं।

ऐप सिर्फ़ 12 वस्तुएँ ही क्यों लेने देता है?

क्योंकि सटीक उत्तर वस्तुओं का हर समुच्चय देखता है, और 12 वस्तुओं से ही 4,096 समुच्चय बन जाते हैं। तेज़ नियम हज़ारों वस्तुएँ संभाल लेते, पर चित्र और सटीक उत्तर से तुलना नहीं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

बिन पैकिंग आज़माएँ