First-fit bin packing
ফার্স্ট-ফিট (এফএফ) হল বিন প্যাকিংয়ের জন্য একটি অনলাইন অ্যালগরিদম। এর ইনপুট হল বিভিন্ন আকারের আইটেমের একটি তালিকা। এর আউটপুট হল একটি প্যাকিং-নির্দিষ্ট ক্ষমতার বিনগুলিতে আইটেমগুলির একটি বিভাজন, যাতে প্রতিটি বিন-এ আইটেমগুলির আকারের যোগফল সর্বাধিক ক্ষমতা হয়। আদর্শভাবে, আমরা যতটা সম্ভব কম বিন ব্যবহার করতে চাই, তবে বিনগুলির সংখ্যা হ্রাস করা একটি এনপি-হার্ড সমস্যা। ফার্স্ট-ফিট অ্যালগরিদম নিম্নলিখিত অনুসন্ধানমূলক ব্যবহার করেঃ এটি খোলা বিনগুলির একটি তালিকা রাখে, যা প্রাথমিকভাবে খালি থাকে। যখন কোনও জিনিস আসে, তখন প্রথম বিনটি খুঁজে বের করুন যেখানে জিনিসটি ফিট করতে পারে, যদি থাকে। যদি এই ধরনের একটি বিন পাওয়া যায়, তাহলে নতুন জিনিসটি তার ভিতরে রাখা হয়। অন্যথায়, একটি নতুন বিন খোলা হয় এবং আগত জিনিসটি তার ভিতরে রাখা হয়। আনুমানিক অনুপাত এফএফ (এল) দ্বারা ফার্স্ট-ফিট দ্বারা ব্যবহৃত বিনগুলির সংখ্যা এবং ওপিটি (এল) দ্বারা তালিকা এল-এর জন্য সম্ভাব্য বিনগুলির সর্বোত্তম সংখ্যা নির্দেশ করে। এফএফ (এল)-এর বিশ্লেষণ বেশ কয়েকটি ধাপে করা হয়েছিল। 1971 সালে উলম্যান এফ. এফ-এর প্রথম ঊর্ধ্বসীমা প্রমাণ করেন। 1972 সালে গ্যারি, গ্রাহাম এবং উলম্যান, জনসন এবং ডেমার্স এই ঊর্ধ্বসীমার উন্নতি ঘটান। 1976 সালে, গ্যারি, গ্রাহাম, জনসন, ইয়াও এবং চি-চিহ দ্বারা এটি উন্নত করা হয়েছিল, যা এবং এর অবিচ্ছেদ্যতার কারণে সমতুল্য। পরবর্তী উন্নতি, 2010 সালে জিয়া এবং ট্যান দ্বারা, এর সীমা কমিয়ে আনা হয়। অবশেষে, 2013 সালে, এই সীমাটি ডাসা এবং সিগাল দ্বারা উন্নত করা হয়েছিল। তারা একটি উদাহরণ ইনপুট তালিকাও উপস্থাপন করে, যার জন্য এই সীমার সাথে মেলে। নীচে আমরা প্রমাণ ধারণাটি ব্যাখ্যা করছি। অ্যাসিম্পটোটিক অনুপাত সর্বাধিক 2 এখানে একটি প্রমাণ যে অ্যাসিম্পটোটিক অনুপাত সর্বাধিক 2। যদি একটি এফ. এফ বিন থাকে যার যোগফল এক-তৃতীয়াংশের কম হয়, তাহলে অবশিষ্ট সমস্ত জিনিসের আকার এক-তৃতীয়াংশের বেশি হয়, তাই নিম্নলিখিত সমস্ত বিনগুলির যোগফল এক-তৃতীয়াংশের বেশি হয়। অতএব, সর্বাধিক একটি ব্যতীত সমস্ত এফ. এফ বিনগুলির যোগফল কমপক্ষে এক-তৃতীয়াংশ। সমস্ত সর্বোত্তম বিনগুলির যোগফল সর্বাধিক 1, তাই সমস্ত আকারের যোগফল সর্বাধিক ওপিটি। অতএব, এফএফ বিনের সংখ্যা সর্বাধিক 1 + ওপিটি/(1/2) = 2 * ওপিটি + 1 উপসর্গহীন অনুপাত সর্বাধিক 1.75 প্রথমে একটি বিশেষ ক্ষেত্রে বিবেচনা করুন যেখানে সমস্ত আইটেমের আকার সর্বাধিক 1/2 হয়। যদি একটি এফ. এফ বিন থাকে যার সমষ্টি 2/3-এর কম হয়, তাহলে বাকি সমস্ত জিনিসের আকার 1/3-এর বেশি হবে। যেহেতু আকারগুলি সর্বাধিক এক-তৃতীয়াংশ, তাই নিম্নলিখিত সমস্ত বিনগুলিতে (সম্ভবত শেষটি বাদে) কমপক্ষে দুটি আইটেম থাকে এবং যোগফল দুই-তৃতীয়াংশের চেয়ে বড় হয়। অতএব, সর্বাধিক একটি ব্যতীত সমস্ত এফএফ বিনগুলির যোগফল কমপক্ষে 2/3, এবং এফএফ বিনগুলির সংখ্যা সর্বাধিক 2 + ওপিটি/(2/3) = 3/2 * ওপিটি + 1। "সমস্যাযুক্ত" জিনিসগুলি হল সেগুলি যেগুলির আকার এক-তৃতীয়াংশের চেয়ে বড়। সুতরাং, বিশ্লেষণের উন্নতির জন্য, আসুন প্রতিটি আইটেমকে অর্ধেকের চেয়ে বড় আর বোনাস দেওয়া যাক। একটি আইটেমের ওজনকে তার আকার এবং তার বোনাস হিসাবে সংজ্ঞায়িত করুন। একটি বস্তুর ওজনকে তার সামগ্রীর ওজনের সমষ্টি হিসাবে সংজ্ঞায়িত করুন। এখন, একটি আইটেম সহ প্রতিটি এফএফ বিনের ওজন (সর্বাধিক একটি ব্যতীত) কমপক্ষে 1/2 + আর, এবং দুটি বা ততোধিক আইটেম সহ প্রতিটি এফএফ বিনের ওজন (সর্বাধিক একটি ব্যতীত) 2/3। আর = 1/6 নেওয়ার ফলে সমস্ত এফএফ বিনের ওজন কমপক্ষে 2/3 হয়। অন্যদিকে, সর্বোত্তম প্যাকিংয়ের প্রতিটি বিন-এর ওজন সর্বাধিক 1 + আর = 7/6 হয়, কারণ এই ধরনের প্রতিটি বিন-এর সর্বাধিক একটি আইটেম 1/2-এর চেয়ে বড় থাকে। অতএব, সমস্ত পণ্যের মোট ওজন সর্বাধিক 7 * 6 * ওপিটি, এবং এফএফ বিনের সংখ্যা সর্বাধিক 2 + (7 * 6 * ওপিটি/(2/3)) = 7 * 4 * ওপিটি + 2। উপসর্গহীন অনুপাত সর্বাধিক 1.7 নিম্নলিখিত প্রমাণ থেকে অভিযোজিত হয়। একটি ইনপুট আইটেমের ওজনকে আইটেমের আকার x কিছু বোনাস হিসাবে নিম্নরূপ গণনা করুনঃ দুটি দাবি থেকে অ্যাসিম্পটোটিক আনুমানিক অনুপাত অনুসরণ করা হয়ঃ সর্বোত্তম প্যাকিংয়ে, প্রতিটি বিন-এর ওজন সর্বাধিক 17/12 হয়; ফার্স্ট-ফিট প্যাকিংয়ে, প্রতিটি বিন-এর গড় ওজন কমপক্ষে 5/6 = 10/12 হয়। অতএব, উপসর্গহীনভাবে, এফএফ প্যাকিংয়ে বিনগুলির সংখ্যা সর্বাধিক 17/10 * ওপিটি হতে হবে। দাবি 1-এর জন্য, এটি প্রমাণ করার জন্য যথেষ্ট যে, যে কোনও সেট বি-এর জন্য সর্বাধিক 1 যোগফল সহ, বোনাস (বি) সর্বাধিক 5/12। প্রকৃতপক্ষেঃ যদি 'খ'-এর 1/2-এর চেয়ে বড় কোনও আইটেম না থাকে, তবে তার সর্বোচ্চ পাঁচটি আইটেম থাকে যা 1/6-এর চেয়ে বড়, এবং তাদের প্রত্যেকটির বোনাস সর্বাধিক 1/12 হয়; যদি 'খ'-এর একটি আইটেম 1/2-এর চেয়ে বড় হয় কিন্তু [1/3,1 2]-এ কোনও আইটেম না থাকে, তবে এতে সর্বাধিক দুটি আইটেমের জন্য জায়গা থাকে (1/6,1 3), এবং তাদের বোনাসের সমষ্টি সর্বাধিক (1/2/2-1/6) = 1/12, তাই মোট বোনাস হল 4/12 + 1/12 = 5/12। যদি 'খ'-এর একটি আইটেম 1/2-এর চেয়ে বড় হয় এবং একটি আইটেম [1/3,1 2]-এ থাকে, তবে এর জন্য 1/6-এর চেয়ে বড় আকারের আইটেমগুলির জন্য আর জায়গা নেই, তাই মোট বোনাস আবার 4/12+1 12 = 5/12। অতএব, বি-এর ওজন সর্বাধিক 1 + 5/12 = 17/12। দাবি 2-এর জন্য, প্রথমে একটি একক আইটেম সহ একটি এফএফ বিন বি বিবেচনা করুন। যদি যোগফল (বি) <1/2 হয়, তবে-এফএফ যেভাবে কাজ করে-বি-এর পরে প্রক্রিয়াজাত সমস্ত আইটেম অবশ্যই 1/2-এর চেয়ে বড় হতে হবে (অন্যথায় সেগুলি বি-তে ঢোকানো হত)। অতএব, যোগফল <1/2 সহ সর্বাধিক একটি এফ. এফ বিন রয়েছে। এখন যোগফল (বি)> 1/2 সহ একটি একক পণ্য সহ অন্যান্য সমস্ত বিন বি বিবেচনা করুন। এই সমস্ত বিনের জন্য ওজন (বি)> 1/2+1 3 = 5/6। এখন দুই বা ততোধিক আইটেম সহ এফএফ বিন বি বিবেচনা করুন। যদি যোগফল (বি) <2/3 হয়, তাহলে-যেভাবে এফএফ কাজ করে-বি-এর পরে প্রক্রিয়াজাত সমস্ত আইটেম অবশ্যই 1/3-এর চেয়ে বড় হতে হবে (অন্যথায় সেগুলি বি-তে ঢোকানো হত)। অতএব, দুই বা ততোধিক আইটেম সহ সমস্ত নিম্নলিখিত বিন 2/3 এর চেয়ে বড়। সুতরাং দুই বা ততোধিক আইটেম এবং যোগফল <2/3 সহ সর্বাধিক একটি এফএফ বিন রয়েছে। এখন দুই বা ততোধিক আইটেম এবং যোগফল> 2/3 সহ অন্যান্য সমস্ত বিন বিবেচনা করুন। বি [1], বি [2], বি [কে] দ্বারা চিহ্নিত করুন, যে ক্রমে সেগুলি খোলা হয়। 1,., k-এর প্রতিটি i-এর জন্য আমরা প্রমাণ করি যে, B [i] এবং B [i + 1]-এর বোনাসের যোগফল কমপক্ষে 5/6: যোগফল (B [i]) + বোনাস (B [i + 1])> = 5/6। প্রকৃতপক্ষে, যদি যোগফল (বি [আই])> = 5/6 হয় তবে বৈষম্যটি তুচ্ছ। অন্যথায়, ধরা যাক যোগফল (বি [আই]): = 1-এক্স। লক্ষ্য করুন যে x হল 1/6 এবং 2/6 এর মধ্যে, যেহেতু যোগফল (B [i]) হল 2/3 এবং 5/6 এর মধ্যে। যেহেতু বি [আই + 1] বি [আই]-এর পরে খোলা হয়, তাই বি [আই + 1]-তে কমপক্ষে দুটি বস্তু থাকে, যেমন সি1 এবং সি2, যা বি [আই]-এর সাথে খাপ খায় না, অর্থাৎঃ সি1, সি2> 1-সমষ্টি (বি [আই]) = এক্স> 1/6। তারপর সি1 এবং সি2-এর প্রত্যেকটির বোনাস হবে কমপক্ষে এক্স/2-1/12। অতএব, B [i + 1]-এর বোনাস কমপক্ষে x-1/6, তাই যোগফল (B [i]) + বোনাস (B [i + 1])> = (1-x) + (x-1/6) = 5/6। আমরা উপরের অসমতাটি ধারাবাহিক জোড়াগুলিতে প্রয়োগ করতে পারি এবং পেতে পারিঃ যোগফল (বি [1]) + বোনাস (বি [2]) + যোগফল (বি [2]) + বোনাস (বি [3]) + যোগফল (বি [কে-1]) + বোনাস (বি [কে])> = 5/6 * (কে-1)। অতএব, সমস্ত এফএফ বিনের মোট ওজন কমপক্ষে 5 * 6 * (এফএফ-3) (যেখানে আমরা একক এক-আইটেম বিনের জন্য 3 বিয়োগ করি যোগফল <1/2 দিয়ে, একক দুই-আইটেম বিন যোগফল <2/3 দিয়ে এবং দুই-আইটেম বিন থেকে কে-1 বিয়োগ করি যোগফল> = 2/3 দিয়ে)। সব মিলিয়ে, আমরা সেই 17/12 * OPT> = 5/6 * (FF-3) পাই, তাই FF <= 17/10 * OPT + 3। ডাসা এবং সিগাল একটি কঠোর বিশ্লেষণ উপস্থাপন করেন যা 3 থেকে মুক্তি পায় এবং সেই এফএফ <= 17/10 * ওপিটি পায়। লোয়ার বাউন্ড এমন কিছু উদাহরণ রয়েছে যেখানে 1.7OPT এর পারফরম্যান্স বাউন্ড টাইট থাকে। নিম্নলিখিত উদাহরণটি এর উপর ভিত্তি করে। বিনটির ধারণক্ষমতা 101 এবংঃ ক্রমটি হলঃ 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10)। সর্বোত্তম প্যাকিংয়ে 10টি বিন থাকেঃ [51+34 + 16] (x3), [51+34 + 10+6] (x7)। সমস্ত বিন যোগফল 101। ফার্স্ট ফিট প্যাকিংয়ে 17টি বিন রয়েছেঃ [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10)। বিন যোগফলগুলি হলঃ 92,68,68 (x5), 51 (x10)। পুরষ্কারগুলি (101-এ স্বাভাবিক) হল 0,0,16.8 (x5), 33.7 (x10)। মোট ওজন (101 এ স্বাভাবিক) হল 92,68,84.8 (x5), 84.7 (x10)। এটি দেখা যায় যে প্রায় সমস্ত ওজন 101 * 5/6 = 84.1 এর কাছাকাছি। রিফাইন্ড ফার্স্ট-ফিট রিফাইন্ড-ফার্স্ট-ফিট (আর. এফ. এফ) হল বিন প্যাকিংয়ের জন্য আরেকটি অনলাইন অ্যালগরিদম, যা পূর্বে উন্নত এফ. এফ অ্যালগরিদমের উপর উন্নতি করে। এটি উপস্থাপন করেছেন অ্যান্ড্রু চি-চিহ ইয়াও। অ্যালগরিদম আইটেমগুলি তাদের আকার অনুসারে চারটি শ্রেণীতে শ্রেণীবদ্ধ করা হয় (যেখানে বিন ক্ষমতা 1):-পিস-সাইজ ইন। - পিস-সাইজ ইন। - পিস-সাইজ ইন। - পিস-সাইজ ইন। একইভাবে, বিনগুলি চারটি শ্রেণীতে শ্রেণীবদ্ধ করা হয়েছেঃ 1,2,3 এবং 4। ধরা যাক একটি নির্দিষ্ট পূর্ণসংখ্যা। পরবর্তী আইটেমটি একটি বিন-এ বরাদ্দ করা হয়-ক্লাস 1, যদি একটি-পিস হয়, ক্লাস 2, যদি একটি-পিস হয়, ক্লাস 3, যদি একটি-পিস হয়, তবে কোনও পূর্ণসংখ্যার জন্য এখন পর্যন্ত দেখা তম-পিস নয়। ক্লাস 1, যদি এখন পর্যন্ত দেখা হয়, ক্লাস 4, যদি একটি-পিস হয়। একবার আইটেমের শ্রেণী নির্বাচন করা হলে, এটি প্রথম-ফিট বিন প্যাকিং ব্যবহার করে সেই শ্রেণীর বিনগুলির ভিতরে স্থাপন করা হয়। মনে রাখবেন যে আর. এফ. এফ কোনও-ফিট অ্যালগরিদম নয় কারণ এটি একটি নতুন বিন খুলতে পারে যদিও বর্তমান আইটেমটি একটি খোলা বিন (অন্য শ্রেণী থেকে) এর ভিতরে ফিট করে। আনুমানিক অনুপাত আর. এফ. এফ-এর একটি আনুমানিক নিশ্চয়তা রয়েছে। ফর-এর সঙ্গে তালিকার একটি পরিবার রয়েছে। ফার্স্ট-ফিট-ডিক্রিজিং (এফএফডি) হল ফার্স্ট-ফিটের অফলাইন সংস্করণঃ এটি সমস্ত ইনপুট আইটেম গ্রহণ করে, অবরোহী আকারের দ্বারা অর্ডার করে এবং ফার্স্ট-ফিট কল করে। এর অ্যাসিম্পটোটিক আনুমানিক অনুপাত অনেক ভালঃ 1.7 এর পরিবর্তে প্রায় 1.222। বাস্তবায়ন পাইথনঃ প্রাটিপি প্যাকেজে ফার্স্ট-ফিটের একটি বাস্তবায়ন রয়েছে। রেফারেন্স বিন প্যাকিং