Multidimensional assignment problem
বহুমাত্রিক অ্যাসাইনমেন্ট সমস্যা (এমএপি) একটি মৌলিক কম্বিনেটোরিয়াল অপ্টিমাইজেশন সমস্যা যা উইলিয়াম পিয়ার্সকালা দ্বারা প্রবর্তিত হয়েছিল। এই সমস্যাটিকে লিনিয়ার অ্যাসাইনমেন্ট সমস্যার সাধারণীকরণ হিসাবে দেখা যেতে পারে। সংক্ষেপে, সমস্যাটিকে নিম্নরূপ বর্ণনা করা যেতে পারেঃ সমস্যার একটি উদাহরণে বেশ কয়েকটি এজেন্ট (যেমন, কার্ডিনালিটি প্যারামিটার) এবং কাজের বেশ কয়েকটি বৈশিষ্ট্য (যেমন, ডাইমেনশনালিটি প্যারামিটার) যেমন কাজ, মেশিন, সময়ের ব্যবধান ইত্যাদি রয়েছে। উদাহরণস্বরূপ, একজন এজেন্টকে কাজ এক্স, মেশিনে ওয়াই, সময় ব্যবধান জেড চলাকালীন সম্পাদন করার জন্য নিযুক্ত করা যেতে পারে। যে কোনও এজেন্টকে কোনও মূল্যে অনন্য কাজের বৈশিষ্ট্যগুলির যে কোনও সংমিশ্রণ সহ একটি কাজ সম্পাদনের জন্য নিযুক্ত করা যেতে পারে। এই খরচগুলি কাজের বৈশিষ্ট্যগুলির সংমিশ্রণে এজেন্টের নিয়োগের উপর ভিত্তি করে পরিবর্তিত হতে পারে-নির্দিষ্ট কাজ, মেশিন, সময়ের ব্যবধান ইত্যাদি। সমস্যাটি হল এজেন্টদের নিয়োগের মোট খরচ কমানো যাতে প্রতিটি কাজের বৈশিষ্ট্যের জন্য এজেন্টদের নিয়োগ একটি ইনজেকটিভ ফাংশন, বা এজেন্টদের থেকে একটি প্রদত্ত কাজের বৈশিষ্ট্যের জন্য এক-থেকে-এক ফাংশন হয়। বিকল্পভাবে, গ্রাফ তত্ত্ব ব্যবহার করে সমস্যাটি বর্ণনা করাঃ বহুমাত্রিক অ্যাসাইনমেন্ট সমস্যাটি একটি ওজনযুক্ত মাল্টিপার্টাইট গ্রাফে একটি প্রদত্ত আকারের মিল খুঁজে বের করা নিয়ে গঠিত, যেখানে প্রান্তগুলির ওজনের যোগফল সর্বনিম্ন। আনুষ্ঠানিক সংজ্ঞা সাহিত্যে এই সমস্যার বিভিন্ন সূত্র পাওয়া যায়। খরচ-ফাংশন ব্যবহার করে, ডাইমেনশনাল অ্যাসাইনমেন্ট সমস্যা (বা এমএপি) নিম্নরূপ বর্ণনা করা যেতে পারেঃ প্রদত্ত সেট, এবং, সমান আকারের, একসাথে একটি খরচ অ্যারে বা বহুমাত্রিক ওজন ফাংশন সহঃ, বিন্যাসগুলি খুঁজে বের করুনঃ এ → যাতে মোট খরচ ফাংশনঃ ন্যূনতম হয়। মাল্টিডাইমেনশনাল অ্যাসাইনমেন্ট প্রবলেম (এমএপি)-এর দুটি মূল পরামিতি রয়েছে যা একটি সমস্যার উদাহরণের আকার নির্ধারণ করেঃ ডাইমেনশনালিটি প্যারামিটার কার্ডিনালিটি প্যারামিটার, যেখানে উপাদানগুলির সংখ্যা বোঝায়। খরচ বিন্যাসের আকার পরামিতি সহ এমএপি-এর যে কোনও সমস্যার উদাহরণের নির্দিষ্ট খরচ বিন্যাস রয়েছে, যা উদাহরণ-নির্দিষ্ট খরচ/ওজনের পরামিতি নিয়ে গঠিত। এটি খরচ অ্যারের আকার। সম্ভাব্য সমাধানের সংখ্যা এমএপি-র সম্ভাব্য অঞ্চল বা সমাধানের স্থান অনেক বড়। সম্ভাব্য সমাধানের সংখ্যা (এমএপি দৃষ্টান্তের আকার) এমএপি পরামিতিগুলির উপর নির্ভর করে। বিশেষ করে,। গণনামূলক জটিলতা সমস্যাটি সাধারণত এন. পি-হার্ড হয়। অন্য কথায়, বহুপদী সময়ে এই সমস্যা সমাধানের জন্য কোনও পরিচিত অ্যালগরিদম নেই, এবং তাই মাঝারি আকারের (মাত্রা এবং কার্ডিনালিটি পরামিতিগুলির উপর ভিত্তি করে) সমস্যার উদাহরণগুলি সমাধান করার জন্য একটি দীর্ঘ গণনামূলক সময়ের প্রয়োজন হতে পারে। অ্যাপ্লিকেশন সমস্যাটি অনেক ক্ষেত্রে প্রয়োগ পাওয়া গেছেঃ সময়সূচী (উৎপাদন প্রক্রিয়া) মাল্টি-সেন্সর ডেটা ফিউশন রেকর্ড সংযোগ বা মাল্টিপার্টাইট সত্তা রেজোলিউশন প্রাথমিক কণা পদার্থবিজ্ঞান ছোট পরিধানযোগ্য ডিভাইস সহ বয়স্কদের মধ্যে পতন সনাক্তকরণ রেফারেন্স কম্বিনেটরিয়াল অপ্টিমাইজেশন https://issuu.com/ostraky/docs/the_top_5_english_coursework_help_strategies_for_t