Partition problem
সংখ্যা তত্ত্ব এবং কম্পিউটার বিজ্ঞানে, বিভাজন সমস্যা বা সংখ্যা বিভাজন হল ধনাত্মক পূর্ণসংখ্যার একটি প্রদত্ত মাল্টিসেট এস-কে দুটি উপসেট এস1 এবং এস2-এ বিভক্ত করা যেতে পারে কিনা তা নির্ধারণ করার কাজ যাতে এস1-এর সংখ্যার যোগফল এস2-এর সংখ্যার যোগফলের সমান হয়। যদিও বিভাজনের সমস্যাটি এনপি-সম্পূর্ণ, একটি ছদ্ম-বহুপদী সময় গতিশীল প্রোগ্রামিং সমাধান রয়েছে এবং এমন অনুসন্ধান রয়েছে যা অনেক ক্ষেত্রে সমস্যাটি সর্বোত্তমভাবে বা আনুমানিকভাবে সমাধান করে। এই কারণে, এটিকে "সবচেয়ে সহজ কঠিন সমস্যা" বলা হয়েছে। পার্টিশন সমস্যার একটি অপ্টিমাইজেশন সংস্করণ রয়েছে, যা মাল্টিসেট এস-কে দুটি উপসেট এস1, এস2-এ বিভক্ত করে যাতে এস1-এর উপাদানগুলির যোগফল এবং এস2-এর উপাদানগুলির যোগফলের মধ্যে পার্থক্য হ্রাস পায়। অপ্টিমাইজেশান সংস্করণটি এনপি-হার্ড, তবে বাস্তবে দক্ষতার সাথে সমাধান করা যেতে পারে। বিভাজন সমস্যা দুটি সম্পর্কিত সমস্যার একটি বিশেষ ক্ষেত্রেঃ উপসেট সমষ্টি সমস্যায়, লক্ষ্য হল S-এর একটি উপসেট খুঁজে বের করা যার যোগফল একটি নির্দিষ্ট লক্ষ্য সংখ্যা T যা ইনপুট হিসাবে দেওয়া হয় (বিভাজন সমস্যা হল বিশেষ ক্ষেত্রে যেখানে T হল S-এর অর্ধেক যোগফল)। মাল্টিওয়ে সংখ্যা বিভাজনে, একটি পূর্ণসংখ্যা পরামিতি k রয়েছে এবং লক্ষ্য হল সিদ্ধান্ত নেওয়া যে S কে সমান যোগফলের k উপসেটে ভাগ করা যেতে পারে কিনা (বিভাজনের সমস্যাটি হল বিশেষ ক্ষেত্রে যেখানে k = 2)। যাইহোক, এটি 3-পার্টিশন সমস্যার থেকে বেশ আলাদাঃ সেই সমস্যায়, উপসেটগুলির সংখ্যা আগে থেকে স্থির করা হয় না-এটি |S।/3 হওয়া উচিত, যেখানে প্রতিটি উপসেটে অবশ্যই ঠিক 3 টি উপাদান থাকতে হবে। 3-বিভাজন বিভাজনের তুলনায় অনেক কঠিন-পি = এনপি ছাড়া এর কোনও ছদ্ম-বহুপদী সময় অ্যালগরিদম নেই। প্রদত্ত উদাহরণগুলি হল S = {3,1,1,2,2,1}, পার্টিশন সমস্যার একটি বৈধ সমাধান হল দুটি সেট S1 = {1,1,1,2} এবং S2 = {{2,3}। উভয় সেটের যোগফল 5, এবং তারা পার্টিশন এস। মনে রাখবেন যে এই সমাধানটি অনন্য নয়। S1 = {3,1,1} এবং S2 = {2,2,1} হল আরেকটি সমাধান। ধনাত্মক পূর্ণসংখ্যার প্রতিটি মাল্টিসেটের সমান যোগফল সহ দুটি উপসেটে বিভাজন থাকে না। এই ধরনের একটি সেটের উদাহরণ হল S = {2,5}। গণনামূলক কঠোরতা বিভাজনের সমস্যা হল এন. পি কঠিন। উপসেট সমষ্টি সমস্যা থেকে হ্রাস করে এটি প্রমাণ করা যেতে পারে। উপসেটসামের একটি উদাহরণ ধনাত্মক পূর্ণসংখ্যার একটি সেট এস এবং একটি লক্ষ্য যোগফল টি নিয়ে গঠিত; লক্ষ্য হল ঠিক টি যোগফল সহ এস-এর একটি উপসেট আছে কিনা তা নির্ধারণ করা। এই ধরনের একটি উদাহরণ দেওয়া হলে, বিভাজনের একটি উদাহরণ তৈরি করুন যেখানে ইনপুট সেটটিতে মূল সেট যোগ দুটি উপাদান রয়েছেঃ z1 এবং z2, z1 = যোগফল (S) এবং z2 = 2T সহ। এই ইনপুট সেটের যোগফল হল যোগফল (S) + z1 + z2 = 2 যোগফল (S) + 2T, তাই বিভাজনের জন্য লক্ষ্য যোগফল হল যোগফল (S) + T। ধরুন উপসেটসম দৃষ্টান্তের একটি সমাধান S′ রয়েছে। তারপর যোগফল (S′) = T, তাই যোগফল (S′z _ 1) = যোগফল (S) + T, তাই S′z _ 1 হল বিভাজনের দৃষ্টান্তের একটি সমাধান। বিপরীতভাবে, ধরুন বিভাজনের উদাহরণের একটি সমাধান রয়েছে। তারপর, S′′-এ অবশ্যই z1 বা z2 থাকতে হবে, কিন্তু উভয়ই নয়, যেহেতু তাদের যোগফল যোগফল (S) + T-এর চেয়ে বেশি। যদি S "-এ z1 থাকে, তবে এতে অবশ্যই S-এর উপাদানগুলি থাকতে হবে যার যোগফল ঠিক T, তাই S" বিয়োগ z1 হল উপসেটসম উদাহরণের একটি সমাধান। যদি S "-এ z2 থাকে, তবে এতে অবশ্যই S থেকে সঠিক যোগফল (S) − T সহ উপাদান থাকতে হবে, তাই S-এর অন্যান্য বস্তুগুলি উপসেটসম উদাহরণের একটি সমাধান। আনুমানিক অ্যালগরিদম উপরে উল্লিখিত হিসাবে, পার্টিশন সমস্যাটি মাল্টিওয়ে-পার্টিশন এবং উপসেট-যোগফলের একটি বিশেষ ক্ষেত্রে। অতএব, এই সমস্যাগুলির প্রত্যেকটির জন্য তৈরি অ্যালগরিদম দ্বারা এটি সমাধান করা যেতে পারে। মাল্টিওয়ে সংখ্যা বিভাজনের জন্য তৈরি অ্যালগরিদমগুলির মধ্যে রয়েছেঃ লোভী সংখ্যা বিভাজন-সংখ্যার উপর লুপ, এবং প্রতিটি সংখ্যা সেটের মধ্যে রাখে যার বর্তমান যোগফল সবচেয়ে ছোট। যদি সংখ্যাগুলি সাজানো না হয়, তবে রানটাইম হল ও (এন) এবং আনুমানিক অনুপাত সর্বাধিক 3/2 ("আনুমানিক অনুপাত" মানে অ্যালগরিদম আউটপুটে বৃহত্তর যোগফল, একটি সর্বোত্তম পার্টিশনে বৃহত্তর যোগফল দ্বারা বিভক্ত)। সংখ্যাগুলি সাজানো রানটাইমকে ও (এন লগ এন)-এ বৃদ্ধি করে এবং আনুমানিক অনুপাতকে 7/6-এ উন্নত করে। যদি সংখ্যাগুলি [0,1]-এ সমানভাবে বিতরণ করা হয়, তবে আনুমানিক অনুপাতটি প্রায় নিশ্চিত এবং প্রত্যাশিত। বৃহত্তম পার্থক্য পদ্ধতি (কর্মকার-কার্প অ্যালগরিদম নামেও পরিচিত) সংখ্যাগুলিকে অবরোহী ক্রমে সাজায় এবং বারবার তাদের পার্থক্য দ্বারা সংখ্যাগুলিকে প্রতিস্থাপন করে। রানটাইম জটিলতা হল ও (এন লগ এন)। সবচেয়ে খারাপ ক্ষেত্রে, এর আনুমানিক অনুপাত একই-সর্বাধিক 7/6। যাইহোক, গড় ক্ষেত্রে এটি লোভী অ্যালগরিদমের তুলনায় অনেক ভাল কাজ করেঃ যখন সংখ্যাগুলি [0,1]-এ সমানভাবে বিতরণ করা হয়, তখন এর আনুমানিক অনুপাত সর্বাধিক প্রত্যাশিত হয়। এটি সিমুলেশন পরীক্ষায় আরও ভাল কাজ করে। মাল্টিফিট অ্যালগরিদম বিন প্যাকিংয়ের জন্য একটি অ্যালগরিদমের সাথে মিলিত বাইনারি অনুসন্ধান ব্যবহার করে। সবচেয়ে খারাপ ক্ষেত্রে, এর আনুমানিক অনুপাত 8/7। উপসেট সমষ্টি সমস্যার একটি এফ. পি. টি. এ. এস রয়েছে যা বিভাজনের সমস্যার জন্যও ব্যবহার করা যেতে পারে, লক্ষ্য সমষ্টি যোগফল (এস)/2 নির্ধারণ করে। সঠিক অ্যালগরিদম রয়েছে, যা সর্বদা সর্বোত্তম পার্টিশন খুঁজে পায়। যেহেতু সমস্যাটি এনপি-হার্ড, তাই এই ধরনের অ্যালগরিদমগুলি সাধারণভাবে সূচকীয় সময় নিতে পারে, তবে নির্দিষ্ট কিছু ক্ষেত্রে ব্যবহারিকভাবে ব্যবহারযোগ্য হতে পারে। মাল্টিওয়ে নম্বর পার্টিশনিং-এর জন্য তৈরি অ্যালগরিদমগুলির মধ্যে রয়েছেঃ সিউডোপলিনামিয়াল টাইম নম্বর পার্টিশনিং মেমরি নেয়, যেখানে ইনপুটের বৃহত্তম সংখ্যা। সম্পূর্ণ লোভী অ্যালগরিদম (সিজিএ) একটি বাইনারি ট্রি তৈরি করে সমস্ত বিভাজন বিবেচনা করে। গাছের প্রতিটি স্তর একটি ইনপুট সংখ্যার সাথে মিলে যায়, যেখানে মূলটি বৃহত্তম সংখ্যার সাথে মিলে যায়, নীচের স্তরটি পরবর্তী বৃহত্তম সংখ্যার সাথে মিলে যায় ইত্যাদি। প্রতিটি শাখা একটি ভিন্ন সেটের সাথে মিলে যায় যেখানে বর্তমান সংখ্যাটি রাখা যেতে পারে। গভীরতা-প্রথম ক্রমে গাছটি অতিক্রম করার জন্য কেবল জায়গার প্রয়োজন হয়, তবে সময় লাগতে পারে। একটি লোভী হিউরিস্টিক ব্যবহার করে রানটাইম উন্নত করা যেতে পারেঃ প্রতিটি স্তরে, প্রথমে সেই শাখাটি বিকাশ করুন যেখানে বর্তমান সংখ্যাটি ক্ষুদ্রতম যোগফলের সাথে সেটে রাখা হয়। এই অ্যালগরিদমটি প্রথমে লোভী সংখ্যা বিভাজনের দ্বারা পাওয়া সমাধানটি খুঁজে পায়, তবে তারপরে আরও ভাল সমাধানের সন্ধান করতে এগিয়ে যায়। এই ধারণার কিছু বৈচিত্র্য হল উপসেট-সমষ্টি সমস্যার জন্য সম্পূর্ণ বহুপদী-সময়ের আনুমানিক পরিকল্পনা, এবং তাই বিভাজন সমস্যার জন্যও। সম্পূর্ণ কর্মকার-কার্প অ্যালগরিদম (সিকেকে) একটি বাইনারি ট্রি তৈরি করে সমস্ত বিভাজন বিবেচনা করে। প্রতিটি স্তর এক জোড়া সংখ্যার সঙ্গে মিলে যায়। বাম শাখাটি তাদের বিভিন্ন উপসেটে রাখার সাথে সামঞ্জস্যপূর্ণ (অর্থাৎ, তাদের পার্থক্য দ্বারা প্রতিস্থাপন করা), এবং ডান শাখাটি তাদের একই উপসেটে রাখার সাথে সামঞ্জস্যপূর্ণ (অর্থাৎ, তাদের যোগফল দ্বারা প্রতিস্থাপন করা)। এই অ্যালগরিদম প্রথমে বৃহত্তম পার্থক্য পদ্ধতি দ্বারা পাওয়া সমাধান খুঁজে পায়, কিন্তু তারপর আরও ভাল সমাধান খুঁজে বের করতে এগিয়ে যায়। এটি এলোমেলো ক্ষেত্রে সিজিএ-র তুলনায় যথেষ্ট দ্রুত চলে। এর সুবিধা অনেক বেশি হয় যখন একটি সমান বিভাজন বিদ্যমান থাকে এবং মাত্রার বিভিন্ন ক্রমের হতে পারে। বাস্তবে, নির্বিচারে আকারের সমস্যাগুলি সিকেকে দ্বারা সমাধান করা যেতে পারে যদি সংখ্যাগুলির সর্বাধিক 12 টি উল্লেখযোগ্য সংখ্যা থাকে। সিকেকে যে কোনও সময় একটি অ্যালগরিদম হিসাবেও চলতে পারেঃ এটি প্রথমে কেকে সমাধান খুঁজে পায় এবং তারপরে সময়ের সাথে সাথে ক্রমান্বয়ে আরও ভাল সমাধান খুঁজে পায় (সম্ভবত সবচেয়ে খারাপ ক্ষেত্রে অনুকূলতায় পৌঁছানোর জন্য সূচকীয় সময়ের প্রয়োজন হয়)। এর জন্য জায়গার প্রয়োজন হয়, তবে সবচেয়ে খারাপ ক্ষেত্রে সময় লাগতে পারে। উপসেট যোগফলের জন্য তৈরি অ্যালগরিদমগুলির মধ্যে রয়েছেঃ হোরোভিটস এবং সানহি-সময়মতো চলে, তবে স্থান প্রয়োজন। শ্রোপেল এবং শামির-সময়মতো দৌড়ায় এবং অনেক কম জায়গার প্রয়োজন হয়। হাউগ্রেভ-গ্রাহাম এবং জোক্স-সময়মতো চলে, তবে এটি একটি এলোমেলো অ্যালগরিদম যা কেবল সিদ্ধান্তের সমস্যা সমাধান করে (অপ্টিমাইজেশান সমস্যা নয়)। হার্ড ইনস্ট্যান্স এবং ফেজ-ট্রানজিশন সেটগুলি শুধুমাত্র একটি বা কোনও পার্টিশন ছাড়াই তাদের ইনপুট আকারের তুলনায় সমাধান করা কঠিন (বা সবচেয়ে ব্যয়বহুল) হতে থাকে। যখন সেটের আকারের তুলনায় মানগুলি ছোট হয়, তখন নিখুঁত বিভাজনের সম্ভাবনা বেশি থাকে। সমস্যাটি একটি "পর্যায় পরিবর্তনের" মধ্য দিয়ে যায় বলে জানা যায়; কিছু সেটের জন্য সম্ভবত এবং অন্যদের জন্য অসম্ভব। যদি m সেটের যে কোনও সংখ্যা প্রকাশ করার জন্য প্রয়োজনীয় বিটের সংখ্যা হয় এবং n সেটের আকার হয় তবে অনেকগুলি সমাধান থাকে এবং খুব কম বা কোনও সমাধান থাকে না। n এবং m বড় হওয়ার সাথে সাথে একটি নিখুঁত বিভাজনের সম্ভাবনা যথাক্রমে 1 বা 0 হয়। এটি মূলত জেন্ট এবং ওয়ালশের পরীক্ষামূলক প্রমাণের ভিত্তিতে যুক্তি দেওয়া হয়েছিল, তারপরে মার্টেন্স দ্বারা পরিসংখ্যানগত পদার্থবিজ্ঞানের পদ্ধতি ব্যবহার করে এবং পরে বোর্গস, চেইস এবং পিটেল দ্বারা প্রমাণিত হয়েছিল। সম্ভাব্য সংস্করণ একটি সম্পর্কিত সমস্যা, যা কিছুটা জন্মদিনের প্যারাডক্সের অনুরূপ, তা হল ইনপুট সেটের আকার নির্ধারণ করা যাতে আমাদের অর্ধেকের সম্ভাবনা থাকে যে একটি সমাধান রয়েছে, এই ধারণার অধীনে যে সেটের প্রতিটি উপাদান এলোমেলোভাবে 1 এবং কিছু প্রদত্ত মানের মধ্যে অভিন্ন বিতরণের সাথে নির্বাচিত হয়। এই সমস্যার সমাধান জন্মদিনের প্যারাডক্সের মতো বিপরীত-স্বজ্ঞাত হতে পারে। বৈচিত্র্য এবং সাধারণীকরণ সমান-কার্ডিনালিটি পার্টিশন এমন একটি বৈচিত্র্য যেখানে উভয় অংশে সমান সংখ্যক আইটেম থাকা উচিত, পাশাপাশি সমান যোগফল থাকা উচিত। এই রূপটিও এন. পি-শক্ত। প্রমাণ। কিছু n সংখ্যা সহ একটি আদর্শ বিভাজনের উদাহরণ দেওয়া হলে, n শূন্য যোগ করে একটি সমান-কার্ডিনালিটি-বিভাজনের উদাহরণ তৈরি করুন। স্পষ্টতই, নতুন দৃষ্টান্তটির একটি সমান-কার্ডিনালিটি সমান-সমষ্টি বিভাজন রয়েছে যদি মূল দৃষ্টান্তটির একটি সমান-সমষ্টি বিভাজন থাকে। ব্যালেন্সড নম্বর পার্টিশনও দেখুন। স্বতন্ত্র পার্টিশন হল একটি বৈকল্পিক যেখানে সমস্ত ইনপুট পূর্ণসংখ্যা স্বতন্ত্র। এই রূপটিও এন. পি-শক্ত। পণ্য বিভাজন হল পূর্ণসংখ্যার একটি সেটকে একই গুণফলের (একই যোগফলের পরিবর্তে) সাথে দুটি সেটে বিভক্ত করার সমস্যা। এই সমস্যাটি দৃঢ়ভাবে এনপি-হার্ড। কোভালিয়ভ এবং পেস পার্টিশন-টাইপ সমস্যার এনপি-কঠোরতা প্রমাণ করার জন্য একটি সাধারণ পদ্ধতি নিয়ে আলোচনা করেছেন। প্রয়োগ বিভাজন সমস্যার একটি প্রয়োগ হল নির্বাচনের কারসাজির জন্য। ধরুন তিনজন প্রার্থী (এ, বি এবং সি) রয়েছেন। একক প্রার্থীকে ভোটের নিয়ম ব্যবহার করে নির্বাচিত করা উচিত, যেমন। ভেটো নিয়ম (প্রতিটি ভোটার একজন প্রার্থীকে ভেটো দেয় এবং সবচেয়ে কম ভেটো দেওয়া প্রার্থী জয়ী হয়)। যদি কোনও জোট নিশ্চিত করতে চায় যে 'সি' নির্বাচিত হয়েছে, তবে তাদের উচিত তাদের ভোটগুলি 'এ' এবং 'বি'-র মধ্যে ভাগ করা যাতে তাদের প্রত্যেকের ন্যূনতম সংখ্যক ভেটো পাওয়া যায়। যদি ভোটগুলি ওজন করা হয়, তবে সমস্যাটি বিভাজন সমস্যায় হ্রাস করা যেতে পারে এবং এইভাবে সিকেকে ব্যবহার করে এটি দক্ষতার সাথে সমাধান করা যেতে পারে। স্কোরিং-এর উপর ভিত্তি করে অন্য যে কোনও ভোটদানের নিয়মের ক্ষেত্রেও একই কথা প্রযোজ্য। দ্রষ্টব্য তথ্যসূত্র সংখ্যা বিভাজন দুর্বল এনপি-সম্পূর্ণ সমস্যা