Harmonic bin packing
হারমোনিক বিন-প্যাকিং হল বিন প্যাকিংয়ের জন্য অনলাইন অ্যালগরিদমের একটি পরিবার। এই ধরনের অ্যালগরিদমের ইনপুট হল বিভিন্ন আকারের আইটেমের একটি তালিকা। আউটপুট হল একটি প্যাকিং-নির্দিষ্ট ক্ষমতার বিনগুলিতে আইটেমগুলির একটি বিভাজন, যাতে প্রতিটি বিন-এ আইটেমগুলির আকারের যোগফল সর্বাধিক ক্ষমতা হয়। আদর্শভাবে, আমরা যতটা সম্ভব কম বিন ব্যবহার করতে চাই, তবে বিনগুলির সংখ্যা হ্রাস করা একটি এনপি-হার্ড সমস্যা। হারমোনিক বিন-প্যাকিং অ্যালগরিদমগুলি একটি হারমোনিক অগ্রগতি অনুসরণ করে আইটেমগুলিকে তাদের আকারের উপর ভিত্তি করে বিভাগে বিভক্ত করার উপর নির্ভর করে। এই ধারণার বিভিন্ন রূপ রয়েছে। হারমোনিক-কে অ্যালগরিদম সামঞ্জস্যপূর্ণভাবে আকারের ব্যবধানকে টুকরো টুকরো করে ভাগ করে। একটি বস্তুকে বলা হয়-আইটেম, যদি। অ্যালগরিদম খালি বিনগুলির সেটকে অসীম শ্রেণীতে বিভক্ত করে, প্রতিটি আইটেম প্রকারের জন্য একটি বিন প্রকার। একটি ধরনের বিন শুধুমাত্র ধরনের জিনিসপত্র প্যাক করার জন্য ব্যবহার করা হয়। এই ধরনের প্রতিটি বিন ঠিক-আইটেম ধারণ করতে পারে। অ্যালগরিদমটি এখন নিম্নরূপ কাজ করেঃ যদি পরবর্তী আইটেমটি একটি-আইটেমের জন্য হয়, তবে আইটেমটি প্রথম (শুধুমাত্র খোলা) বিনটিতে স্থাপন করা হয় যাতে একাধিক টুকরো থাকে বা যদি এমন কোনও বিন বিদ্যমান না থাকে তবে একটি নতুন খোলে। যদি পরবর্তী আইটেমটি একটি-আইটেম হয়, তবে অ্যালগরিদম এটিকে নেক্সট-ফিট ব্যবহার করে টাইপের বিনগুলিতে রাখে। এই অ্যালগরিদমটি প্রথম বর্ণনা করেছিলেন লি এবং লি। এটির একটি সময় জটিলতা রয়েছে যেখানে n হল ইনপুট আইটেমের সংখ্যা। প্রতিটি ধাপে, সর্বাধিক খোলা বিন রয়েছে যা সম্ভাব্যভাবে আইটেমগুলি রাখার জন্য ব্যবহার করা যেতে পারে, অর্থাৎ এটি একটি কে-বাউন্ডেড স্পেস অ্যালগরিদম। লি এবং লি অ্যাসিম্পটোটিক আনুমানিক অনুপাতও অধ্যয়ন করেছিলেন। তারা একটি ক্রমকে সংজ্ঞায়িত করেছে এবং প্রমাণ করেছে যে এর জন্য এটি ধারণ করে। কারণ এটি তা ধরে রাখে। উপরন্তু, তারা রিফাইন্ড-হারমনিক (আর. এইচ)-এর জন্য সবচেয়ে খারাপ উদাহরণের একটি পরিবার উপস্থাপন করেছে রিফাইন্ড-হারমনিক রিফাইন্ড-ফার্স্ট-ফিটের ধারণার সাথে হারমনিক-কে অ্যালগরিদমের ধারণাগুলিকে একত্রিত করে। এটি রিফাইন্ড-ফার্স্ট-ফিটের মতো বড় আইটেমগুলি রাখে, যেখানে ছোট আইটেমগুলি হারমোনিক-কে ব্যবহার করে স্থাপন করা হয়। এই কৌশলটির অন্তর্দৃষ্টি হ 'ল এর চেয়ে বড় টুকরো ধারণকারী বিনগুলির জন্য বিশাল বর্জ্য হ্রাস করা। অ্যালগরিদমটি নিম্নলিখিত ব্যবধানগুলির সাথে সম্পর্কিত আইটেমগুলিকে শ্রেণীবদ্ধ করেঃ,,,, জন্য, এবং। অ্যালগরিদমটি-আইটেমগুলিকে হারমোনিক-কে-এর মতো রাখে, যেখানে এটি এবং-এর আইটেমগুলির জন্য একটি ভিন্ন কৌশল অনুসরণ করে। চারটি সম্ভাবনার মধ্যে রয়েছে-------------------------------------------------- একটি-বিন শুধুমাত্র একটি-আইটেম ধারণ করে। একটি-বিন শুধুমাত্র একটি-আইটেম ধারণ করে। একটি-বিন একটি-আইটেম এবং একটি-আইটেম নিয়ে গঠিত। একটি বিন-এ দুটি জিনিস থাকে। একটি-বিন একটি বিনকে বোঝায় যা একটি দ্বিতীয়-আইটেম ধারণ করার জন্য মনোনীত করা হয়। অ্যালগরিদমটি সমাধানে সংশ্লিষ্ট বিনগুলির সংখ্যা গণনা করতে N _ a, N _ b, N _ ab, N _ b b এবং N _ b 'সংখ্যা ব্যবহার করে। উপরন্তু, একটি তালিকার জন্য N _ c = N _ b + N _ ab অ্যালগরিদম রিফাইন্ড-হারমোনিক-k L = (i _ 1, \dot i _ n): 1। N _ a = N _ b = N _ bb = N _ b '= N _ c = 02। যদি আই _ জে একটি আই _ কে-পিস হয় তবে এটি 3 প্যাক করার জন্য অ্যালগরিদম হারমনিক-কে ব্যবহার করুন। অন্যথায় যদি আই _ জে একটি আই _ এ-আইটেম হয় তবে এন _ বি! = 1, তবে আই _ জে-কে যে কোনও জে _ বি-বিন-এ প্যাক করুন; এন _ বি--; এন _ এবি + +; অন্যথায় আই _ জে-কে একটি নতুন (খালি) বিন-এ রাখুন; এন _ এ + +; 4। অন্যথায় যদি আই _ জে একটি আই _ বি-আইটেম হয় তবে যদি এন _ বি '= 1 হয় তবে আই _ জে-কে আই _ বি'-বিন-এ রাখুন; এন _ বি '= 0; এন _ বিবি + +; 5। অন্যথায় যদি এন _ বিবি <3এনসি হয় তবে আই _ জে রাখুন। তারা প্রমাণ করেছে যে এটি তার জন্য ধারণ করে। অন্যান্য রূপ পরিবর্তিত হারমোনিক (এমএইচ)-এর অ্যাসিম্পটোটিক অনুপাত রয়েছে। পরিবর্তিত হারমোনিক 2 (MH2)-এর অ্যাসিম্পটোটিক অনুপাত রয়েছে। হারমোনিক + 1 (এইচ + 1)-এর অ্যাসিম্পটোটিক অনুপাত রয়েছে। হারমোনিক + + (এইচ + +)-এর অ্যাসিম্পটোটিক অনুপাত রয়েছে এবং। রেফারেন্স বিন প্যাকিং