موضوع مقاله: مسئله تقسیم‌بندی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله تقسیم‌بندی | مقدمه: در علم کامپیوتر مسئله تقسیم‌بندی به مسئله امکان تقسیم یک مجموعه با تکرار از اعداد طبیعی به دو زیرمجموعهٔ S1 و S2 گفته می‌شود به طوری که حاصل جمع اعداد این دو زیرمجموعه با هم برابر باشد. | ## بخش 1: مسئله تقسیم‌بندی | اگرچه این مسئله ان‌پی کامل است اما یک راه‌حل در زمان شبه چندجمله‌ای با استفاده از برنامه‌ریزی پویا برای آن وجود دارد. همچنین راه‌حل‌های اکتشافی برای حل بسیاری از نمونه‌های آن وجود دارد(چه بهینه و چه تقریبی). یک حالت بهینه‌سازی از این مسئله نیز وجود دارد که به تقسیم یک مجموعه با تکرار به دو زیرمجموعهٔ S1 و S2 می‌پردازد به نحوی که تفاوت حاصل جمع اعضای این دو زیر. مثال‌ها با داشتن مجموعه {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 = x1, ..., xn متغیر N را مجموع تمام اعضای داخل S در نظر بگیرید. در ادامه الگوریتمی ارائه خواهیم داد که مشخص می‌کند آیا زیرمجموعه‌ای از S وجود دارد که حاصل جمع اعضای آن شود یا خیر. اگر چنین زیرمجموعه‌ای وجود داشته باشد: اگر N زوج باشد، حاصل جمع سایر عضوهای S نیز خواهد بود. اگر N فرد باشد، حاصل جمع سایر عضوهای S برابر خواهد بود و این بهترین جواب ممکن است. | ## بخش 2: مسئله تقسیم‌بندی | رابطه بازگشتی ( p (i,j را صحیح قرار می‌دهیم اگر زیرمجموعه‌ای از { x1, ..., xj} وجود داشته باشد که حاصل جمع عضوهایش برابر i شود و در غیر این صورت آن را برابر "غلط" قرار می‌دهیم. پس ( p (, n صحیح است اگر و تنها اگر یک زیرمجموعه از S وجود داشته باشد که حاصل‌جمع اعضای آن باشد. دلیل این امر این است که زیرمجموعه‌ای از S با اعداد x1, ..., xj وجود دارد که حاصل‌جمع عضوهای آن برابر i است، اگر و تنها اگر حداقل یکی از عبارات زیر صحیح باشد: زیر مجموعه‌ای از { x1, ..., xj} وجود داشته باشد که شامل xj نباشد و حاصل‌جمع عضوهای آن برابر i باشد. زیر مجموعه‌ای از { x1, ..., xj} وجود داشته باشد که شامل xj نباشد و حاصل‌جمع عضوهای آن برابر i - xj باشد تا حاصل‌جمع xj و آن مجموع برابر i شود. الگوریتم شبهه چندجمله‌ای الگوریتم به این نحو کار می‌کند که یک جدول با سطر و n ستون حاوی مقادیر بازگشتی می‌سازد. در صورتی که مقدار یک خانه از جدول به مقدار خانه دیگری وابسته باشد، یک پیکان از خانه دوم به اول در شکل رسم شده‌است. الگوریتم‌های تقریبی الگوریتم حریصانه در این الگوریتم که روی اعضای مجموعه که به صورت نزولی مرتب شده‌اند اجرا می‌شود، هر عضو داخل زیرمجموعه‌ای می‌رود که مجموع اعضایش کوچکتر است. این الگوریتم هنگامی که مقادیر اعضا برابر یا کمتر از تعداد آن‌ها باشد در مجموعه باشد، به خوبی کار می‌کند. برای مثال برای مجموعه {S = {5, 5, 4, 3, 3 الگوریتم حریصانه زیرمجموعه‌های {S1 = {5, 4 و {S2 = {5, 3, 3 را انتخاب می‌کند در حالی که پاسخ صحیح {S1 = {5, 5 و {S1 = {4, 4, 4 است. یعنی اگر این الگوریتم دو جواب و را بدهد، آنگاه: در زیر شبه‌کد الگوریتم حریصانه آورده شده‌است. | ## بخش 3: مسئله تقسیم‌بندی | این در واقع به معنای قرار دادن این دو عدد در دو زیرمجموعه مجزا می‌باشد بدون اینکه مشخص شود هرکدام از آن‌ها داخل کدام زیرمجموعه می‌شوند. این الگوریتم بهتر از الگوریتم حریصانه عمل می‌کند اما همچنان برای نمونه‌هایی از مسئله که در آن تعداد اعضای مجموعه به صورت نمایی هستند جواب خوبی نمی‌دهد. نمونه‌های سخت مجموعه‌های که یک یا هیچ تقسیم‌بندی برای آن‌ها وجود ندارد، نسبت به اندازه ورودی‌شان مشکل‌ترین هستند. هنگامی که مقادیر اعضا نسبت به اندازه مجموعه کوچک است، احتمال تقسیم‌بندی بهینه بیشتر است. پس می‌گوییم مسئله دستخوش تغییر فاز شده‌است بدین معنا که برای بعضی از مجموعه‌ها محتمل و برای برخی دیگر غیر محتمل است. اگر m را تعداد بیت‌های مورد نیاز برای نشان دادن اعداد داخل مجموعه باشد و n اندازه مجموعه باشد، بنابراین شرط به جواب‌های زیادی منتهی می‌شود در حالی که دارای جواب‌های کمتر و در برخی موارد بدون جواب است. در نتیجه هرچه n و m بیشتر می‌شوند، احتمال تقسیم‌بندی بهینه بین ۰ و ۱ در نوسان است. مسئله تقسیم‌بندی Kتایی حالت دیگری از مسئله تقسیم‌بندی به نام تقسیم‌بندی ۳تایی وجود دارد که مسئله تقسیم مجموعه S به S|/3| زیرمجموعه با مجموع‌های برابر است. | ## جمع‌بندی | این مسئله با مسئله تقسیم‌بندی متفاوت است و هیچ راه‌حل شبه چندجمله‌ای برای آن وجود ندارد مگر P=NP.