Quadratic assignment problem
চতুর্ভুজ অ্যাসাইনমেন্ট সমস্যা (কিউএপি) গণিতের অপ্টিমাইজেশন বা অপারেশন গবেষণার শাখার মৌলিক সমন্বয়মূলক অপ্টিমাইজেশান সমস্যাগুলির মধ্যে একটি, যা কোপম্যানস এবং বেকম্যান দ্বারা প্রথম প্রবর্তিত সুবিধার অবস্থান সমস্যাগুলির বিভাগ থেকে। সমস্যাটি নিম্নলিখিত বাস্তব জীবনের সমস্যার মডেল তৈরি করেঃ এখানে n সুবিধার একটি সেট এবং n অবস্থানের একটি সেট রয়েছে। প্রতিটি জোড়া অবস্থানের জন্য, একটি দূরত্ব নির্দিষ্ট করা হয় এবং প্রতিটি জোড়া সুবিধার জন্য একটি ওজন বা প্রবাহ নির্দিষ্ট করা হয় (যেমন, দুটি সুবিধার মধ্যে পরিবাহিত সরবরাহের পরিমাণ)। সমস্যাটি হল সংশ্লিষ্ট প্রবাহ দ্বারা গুণিত দূরত্বের যোগফলকে ন্যূনতম করার লক্ষ্য নিয়ে বিভিন্ন স্থানে সমস্ত সুবিধা বরাদ্দ করা। স্বজ্ঞাতভাবে, খরচ ফাংশন একে অপরের মধ্যে উচ্চ প্রবাহ সহ সুবিধাগুলি একসঙ্গে স্থাপন করতে উৎসাহিত করে। সমস্যা বিবৃতিটি অ্যাসাইনমেন্ট সমস্যার সাথে সাদৃশ্যপূর্ণ, ব্যতীত ব্যয়ের কার্যকারিতা দ্বিঘাত বৈষম্যের পরিপ্রেক্ষিতে প্রকাশ করা হয়, তাই নামটি। আনুষ্ঠানিক গাণিতিক সংজ্ঞা দ্বিঘাত অ্যাসাইনমেন্ট সমস্যার আনুষ্ঠানিক সংজ্ঞা নিম্নরূপঃ সমান আকারের দুটি সেট, পি ("সুবিধা") এবং এল ("অবস্থান") দেওয়া হয়েছে, একসাথে একটি ওজন ফাংশন ডাব্লুঃ পি × পি → আর এবং একটি দূরত্ব ফাংশন ডিঃ এল × এল → আর। সাধারণত ওজন এবং দূরত্ব ফাংশনগুলিকে বর্গ বাস্তব-মূল্যবান ম্যাট্রিক্স হিসাবে দেখা হয়, যাতে ব্যয় ফাংশনটি এইভাবে লেখা হয়ঃ ম্যাট্রিক্স নোটেশনেঃ যেখানে ক্রমবিকাশ ম্যাট্রিক্সের সেট, ওজন ম্যাট্রিক্স এবং দূরত্ব ম্যাট্রিক্স। গণনামূলক জটিলতা সমস্যাটি এনপি-হার্ড, তাই বহুপদী সময়ে এই সমস্যা সমাধানের জন্য কোনও পরিচিত অ্যালগরিদম নেই, এবং এমনকি ছোট দৃষ্টান্তের জন্যও দীর্ঘ গণনার সময় প্রয়োজন হতে পারে। এটিও প্রমাণিত হয়েছিল যে সমস্যাটির কোনও (ধ্রুবক) ফ্যাক্টরের জন্য বহুপদী সময়ে চলমান আনুমানিক অ্যালগরিদম নেই, যদি না পি = এনপি হয়। ট্রাভেল সেলসম্যান প্রবলেম (টিএসপি) কে কিউএপি-র একটি বিশেষ ক্ষেত্রে দেখা যেতে পারে যদি কেউ ধরে নেয় যে প্রবাহগুলি শুধুমাত্র একটি বলয় বরাবর সমস্ত সুবিধাকে সংযুক্ত করে, সমস্ত প্রবাহের একই অ-শূন্য (ধ্রুবক) মান রয়েছে এবং সমস্ত দূরত্ব টিএসপি দৃষ্টান্তের সংশ্লিষ্ট দূরত্বের সমান। স্ট্যান্ডার্ড কম্বিনেটোরিয়াল অপ্টিমাইজেশান সমস্যার অন্যান্য অনেক সমস্যা এই আকারে লেখা যেতে পারে। প্রয়োগ মূল উদ্ভিদ অবস্থান গঠনের পাশাপাশি, কিউএপি একটি মুদ্রিত সার্কিট বোর্ডে বা একটি মাইক্রোচিপের উপর আন্তঃসংযুক্ত বৈদ্যুতিন উপাদান স্থাপনের সমস্যার জন্য একটি গাণিতিক মডেল, যা ইলেকট্রনিক্স শিল্পে কম্পিউটার সহায়ক ডিজাইনের স্থান এবং পথ পর্যায়ের অংশ। কোয়াড্রাটিক বাটলনেক অ্যাসাইনমেন্ট সমস্যা রেফারেন্স নোটস সোর্স A2.5: ND43, pg.218 দেখুন। বাহ্যিক লিঙ্ক https://www.opt.math.tugraz.at/qaplib কিউএপিএলআইবি-একটি চতুর্ভুজ বরাদ্দ সমস্যা গ্রন্থাগার http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal এমএওএস-কিউএপি-জাভা ভিত্তিক চতুর্ভুজ বরাদ্দ সমস্যা সমাধানকারী https://CRAN.R-project.org/package=qap-আর প্যাকেজ কিউএপিঃ চতুর্ভুজ বরাদ্দ সমস্যার জন্য অনুসন্ধান https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ-উইন্ডোজের জন্য মেটা-হিউরিস্টিক কিউএপি সমাধানকারী 10/11 এনপি-হার্ড সমস্যা সমন্বয়মূলক অপ্টিমাইজেশন