First-fit-decreasing bin packing
ফার্স্ট-ফিট-ডিক্রিজিং (এফ. এফ. ডি) হল বিন প্যাকিংয়ের জন্য একটি অ্যালগরিদম। এর ইনপুট হল বিভিন্ন আকারের আইটেমের একটি তালিকা। এর আউটপুট হল একটি প্যাকিং-নির্দিষ্ট ক্ষমতার বিনগুলিতে আইটেমগুলির একটি বিভাজন, যাতে প্রতিটি বিন-এ আইটেমগুলির আকারের যোগফল সর্বাধিক ক্ষমতা হয়। আদর্শভাবে, আমরা যতটা সম্ভব কম বিন ব্যবহার করতে চাই, তবে বিনগুলির সংখ্যা হ্রাস করা একটি এনপি-হার্ড সমস্যা, তাই আমরা প্রায়-সর্বোত্তম হিউরিস্টিক ব্যবহার করি। বিবরণ এফএফডি অ্যালগরিদম নিম্নরূপ কাজ করে। সবচেয়ে বড় থেকে ছোট জিনিস অর্ডার করুন। একটি নতুন খালি বিন খুলুন, বিন #1। বড় থেকে ছোট প্রতিটি জিনিসের জন্য, প্রথম বিনটি খুঁজে বের করুন যেখানে জিনিসটি ফিট করে, যদি থাকে। যদি এমন একটি বিন পাওয়া যায়, তাহলে তাতে নতুন জিনিসটি রাখুন। অন্যথায়, একটি নতুন খালি বিন খুলুন এবং তাতে নতুন জিনিসটি রাখুন। সংক্ষেপেঃ এফ. এফ. ডি. অবরোহী আকারের পণ্য অর্ডার করে এবং তারপর ফার্স্ট-ফিট বিন প্যাকিং কল করে। এফ. এফ. ডি অ্যালগরিদমের সমতুল্য বিবরণ নিম্নরূপ। সবচেয়ে বড় থেকে ছোট জিনিস অর্ডার করুন। অবশিষ্ট জিনিস রয়েছেঃ একটি নতুন খালি বিন খুলুন। বৃহত্তম থেকে ক্ষুদ্রতম পর্যন্ত প্রতিটি জিনিসের জন্যঃ যদি এটি বর্তমান বিনটিতে ফিট করতে পারে তবে এটি সন্নিবেশ করান। স্ট্যান্ডার্ড বিবরণে, আমরা একবার আইটেমগুলির উপর লুপ করি, তবে অনেকগুলি খোলা বিন রাখি। সমতুল্য বর্ণনায়, আমরা জিনিসগুলির উপর অনেকবার লুপ করি, তবে প্রতিবার কেবল একটি খোলা বিন রাখি। কর্মক্ষমতা বিশ্লেষণ এফ. এফ. ডি-র কর্মক্ষমতা বিভিন্ন ধাপে বিশ্লেষণ করা হয়েছিল। নীচে, ইনপুট সেট এস এবং বিন-ক্ষমতা সি-এর জন্য এফ. এফ. ডি দ্বারা ব্যবহৃত বিনগুলির সংখ্যা নির্দেশ করা হয়েছে। 1973 সালে, ডি. এস। জনসন তাঁর ডক্টরেট থিসিসে প্রমাণ করেছেন যে, যে কোনও ক্ষেত্রে এস এবং ক্যাপাসিটি সি। 1985 সালে, বি. এস। ব্যাকার একটি সামান্য সহজ প্রমাণ দিয়েছেন এবং দেখিয়েছেন যে যোগাত্মক ধ্রুবক 3 এর বেশি নয়। ইউ মিনি প্রমাণ করেছেন যে, 1991 সালে এবং 1997 সালে লি রংহেং-এর সঙ্গে মিলে এই বিশ্লেষণের উন্নতি ঘটান। 2007 সালে গিওর্গি ডাসা টাইট বাউন্ড প্রমাণ করেন এবং যার জন্য একটি উদাহরণ উপস্থাপন করেন। সবচেয়ে খারাপ উদাহরণ দোসা দ্বারা প্রদত্ত নিম্ন সীমার উদাহরণটি নিম্নরূপঃ দুটি বিন কনফিগারেশন বিবেচনা করুনঃ যদি সর্বোত্তম সমাধানে 4 টি কপি এবং 2 টি কপি থাকে, তবে এফএফডি নিম্নলিখিত বিনগুলি গণনা করবেঃ কনফিগারেশন সহ 4 টি বিন, কনফিগারেশন সহ 1 টি বিন, কনফিগারেশন সহ 1 টি বিন, কনফিগারেশন সহ 1 টি ফাইনাল বিন, অর্থাৎ মোট 8 টি বিন, এবং সর্বোত্তমটিতে মাত্র 6 টি বিন রয়েছে। অতএব, উপরের সীমাটি শক্ত, কারণ। এই উদাহরণটি সমস্ত আকারের মধ্যে প্রসারিত করা যেতে পারেঃ সর্বোত্তম বিন্যাসে 9k + 6 টি বিন রয়েছেঃ 6k + 4 প্রকার B1 এবং 3k + 2 প্রকার B2। কিন্তু এফ. এফ. ডি-র কমপক্ষে 11 হাজার + 8টি বিন প্রয়োজন, যা হল। মনোটোনিসিটি বৈশিষ্ট্য অন্তর্দৃষ্টির বিপরীতে, সি-এর একঘেয়ে ফাংশন নয়। একইভাবে, এস-এ আইটেমগুলির আকারের একঘেয়ে ফাংশন নয়ঃ এটি সম্ভব যে কোনও আইটেম আকারে সঙ্কুচিত হয়, তবে ডাবের সংখ্যা বৃদ্ধি পায়। যাইহোক, এফ. এফ. ডি অ্যালগরিদমের একটি "অ্যাসিম্পটোটিক মনোটোনিসিটি" বৈশিষ্ট্য রয়েছে, যা নিম্নরূপ সংজ্ঞায়িত করা হয়েছে। প্রতিটি S এবং পূর্ণসংখ্যা m-এর জন্য, মিনক্যাপ (S, m)-কে ক্ষুদ্রতম ধারণক্ষমতা C হিসাবে ধরা যাক যাতে প্রতিটি পূর্ণসংখ্যা m-এর জন্য, মিনরেশিও (m)-কে r ≤1 সংখ্যার অসীম হিসাবে ধরা হয় যাতে, সমস্ত ইনপুট সেট S-এর জন্য,। এই পরিমাণের মাধ্যমে আমাদের বিনগুলি এমনভাবে "স্ফীত" করতে হবে যাতে এফ. এফ. ডি বিনগুলির সর্বোত্তম সংখ্যা অর্জন করে। তারপর, প্রতিটি ইনপুট এস-এর জন্য এবং প্রতিটি আর-এর জন্য ন্যূনতম অনুপাত (মি)। এটি বিশেষভাবে দেখায় যে, উপরের সংজ্ঞায় অসীমকে ন্যূনতম দ্বারা প্রতিস্থাপিত করা যেতে পারে। উদাহরণস্বরূপ, ধরুন ইনপুটটি হলঃ 44,24,24,22,21,17,8,6,6। ক্ষমতা 60 সহ, এফ. এফ. ডি 3 টি বিন প্যাক করেঃ 44,8,8; 24,24,6,6; 22,21,17। কিন্তু ধারণক্ষমতা 61 সহ, এফ. এফ. ডি 4টি বিন প্যাক করেঃ 44,17; 24,24,8; 22,21,8,6; 6। এর কারণ হল, ধারণক্ষমতা 61 সহ, 17 টি প্রথম বিনটিতে ফিট করে এবং এইভাবে নিম্নলিখিত 8,8-এর পথকে অবরুদ্ধ করে। আরেকটি উদাহরণ হিসাবে, ধরুন ইনপুটগুলি হলঃ 51,28,28,28,27,25,12,12,10,10,10,10,10,10,10,10। 75 ধারণক্ষমতা সহ, এফ. এফ. ডি 4টি বিন প্যাক করেঃ 51,12,12,28,28,10,28,27,10,10,10,10,10 কিন্তু 76 ধারণক্ষমতা সহ, এটির 5টি বিন প্রয়োজনঃ 51,25,28,28,12,28,27,12,10,10,10,10,10। যদি 17টি 16 হয়ে যায়, তাহলে ফলস্বরূপ প্যাকিং হবেঃ 44,16; 24,24,8; 22,21,8,6; 6। মডিফাইড ফার্স্ট-ফিট-ডিক্রিজিং মডিফাইড ফার্স্ট ফিট রিডিং (এম. এফ. এফ. ডি) অর্ধেক বিন-এর চেয়ে বড় আইটেমগুলির জন্য এফ. এফ. ডি-তে উন্নতি করে, আকার অনুসারে আইটেমগুলিকে চারটি আকারের শ্রেণীতে শ্রেণীবদ্ধ করে বড়, মাঝারি, ছোট এবং ছোট, যথাক্রমে আকার> 1/2 বিন,> 1/3 বিন,> 1/6 বিন এবং ছোট আইটেমগুলির সাথে সামঞ্জস্যপূর্ণ। তারপর এটি পাঁচটি পর্যায়ের মধ্য দিয়ে যায়ঃ প্রতিটি বড় আইটেমের জন্য একটি বিন বরাদ্দ করুন, যা বৃহত্তম থেকে ক্ষুদ্রতম। বাক্সের মধ্যে দিয়ে এগিয়ে যান। প্রতিটিতেঃ যদি সবচেয়ে ছোট অবশিষ্ট মাঝারি আইটেমটি মানানসই না হয়, তবে এই বিনটি এড়িয়ে যান। অন্যথায়, সবচেয়ে বড় অবশিষ্ট মাঝারি জিনিসটি রাখুন যা মানানসই। মাঝারি আকারের জিনিস না থাকা ডাস্টবিনগুলির মধ্যে দিয়ে পিছন দিকে এগিয়ে যান। প্রতিটিতেঃ যদি দুটি ক্ষুদ্রতম অবশিষ্ট ছোট আইটেম মানানসই না হয়, তবে এই বিনটি এড়িয়ে যান। অন্যথায়, সবচেয়ে ছোট অবশিষ্ট ছোট আইটেমটি এবং সবচেয়ে বড় অবশিষ্ট ছোট আইটেমটি রাখুন যা উপযুক্ত। সমস্ত বিন দিয়ে এগিয়ে যান। যদি কোনও আকারের শ্রেণীর সবচেয়ে ছোট অবশিষ্ট আইটেমটি মানানসই না হয়, তবে এই বিনটি এড়িয়ে যান। অন্যথায়, সবচেয়ে বড় জিনিসটি রাখুন যা ফিট করে এবং এই বিনটিতে রাখুন। অবশিষ্ট জিনিসগুলি নতুন পাত্রে প্যাক করতে এফ. এফ. ডি ব্যবহার করুন। এই অ্যালগরিদমটি 1985 সালে জনসন এবং গ্যারি প্রথম অধ্যয়ন করেছিলেন, যেখানে তারা তা প্রমাণ করেছিলেন। 1995 সালে ইউ এবং ঝাং দ্বারা এই সীমাটি উন্নত করা হয়েছিল যারা এটি প্রমাণ করেছিল। অন্যান্য রূপ বেস্ট-ফিট-ডিক্রিজিং (বি. এফ. ডি) এফ. এফ. ডি-র সাথে খুব মিল, তবে তালিকাটি বাছাই করার পরে, এটি বেস্ট-ফিট বিন প্যাকিং দ্বারা প্রক্রিয়াজাত করা হয়। এর অ্যাসিম্পটোটিক আনুমানিক অনুপাত এফএফডি-11/9-এর সমান। বাস্তবায়ন পাইথনঃ প্রাটিপি প্যাকেজে ফার্স্ট-ফিট হ্রাসের একটি বাস্তবায়ন রয়েছে। আরও দেখুন মাল্টিফিট অ্যালগরিদম-অভিন্ন-যন্ত্রের সময়সূচীর জন্য একটি অ্যালগরিদম, যা এফ. এফ. ডি-কে সাবরুটিন হিসাবে ব্যবহার করে। রেফারেন্স বিন প্যাকিং