مسئله تقسیم‌بندی

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از مسأله تقسیم‌بندی)
پرش به: ناوبری، جستجو

در علم کامپیوتر مسأله تقسیم‌بندی به مسأله امکان تقسیم یک مجموعه با تکرار (به انگلیسی: Multiset) از اعداد طبیعی به دو زیرمجموعهٔ S1 و S2 اطلاق می‌گردد به طوری که حاصل جمع اعداد این دو زیرمجموعه با هم برابر باشد. اگرچه این مسأله ان‌پی کامل است اما یک راه‌حل در زمان شبه چندجمله‌ای با استفاده از برنامه‌ریزی پویا برای آن وجود دارد. همچنین راه‌حل‌های اکتشافی(به انگلیسی: heuristic) برای حل بسیاری از نمونه‌های آن وجود دارد(چه بهینه و چه تقریبی). به همین دلیل این مسأله به عنوان "ساده‌ترین مسأله سخت" شناخته شده است.

یک حالت بهینه‌سازی از این مسأله نیز وجود دارد که به تقسیم یک مجموعه با تکرار به دو زیرمجموعهٔ 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 وجود دارد که حاصل جمع اعضای آن \lfloor N/2 \rfloor شود یا خیر. اگر چنین زیرمجموعه‌ای وجود داشته باشد:

  • اگر N زوج باشد، حاصل جمع سایر عضوهای S نیز \lfloor N/2 \rfloor خواهد بود.
  • اگر N فرد باشد، حاصل جمع سایر عضوهای S برابر \lceil N/2 \rceil خواهد بود و این بهترین جواب ممکن است.

رابطه بازگشتی[ویرایش]

( p (i,j را صحیح قرار می‌دهیم اگر زیرمجموعه‌ای از { x1, ..., xj} وجود داشته باشد که حاصل جمع عضوهایش برابر i شود و در غیر این صورت آن را برابر "غلط" قرار می‌دهیم.

پس ( p (\lfloor N/2 \rfloor , n صحیح است اگر و تنها اگر یک زیرمجموعه از S وجود داشته باشد که حاصل‌جمع اعضای آن \lfloor N/2 \rfloor باشد. پس هدف این الگوریتم محاسبه ( p (\lfloor N/2 \rfloor , n است. به توجه به این مطلب به رابطه بازگشتی زیر می‌رسیم:

( p (i,j صحیح است اگر ( p (i, j - 1 صحیح باشد یا ( p (i - xj, j - 1 صحیح باشد.
در غیر این صورت ( p (i, j غلط است.

دلیل این امر این است که زیرمجموعه‌ای از S با اعداد x1, ..., xj وجود دارد که حاصل‌جمع عضوهای آن برابر i است، اگر و تنها اگر حداقل یکی از عبارات زیر صحیح باشد:

زیر مجموعه‌ای از { x1, ..., xj} وجود داشته باشد که شامل xj نباشد و حاصل‌جمع عضوهای آن برابر i باشد.
زیر مجموعه‌ای از { x1, ..., xj} وجود داشته باشد که شامل xj نباشد و حاصل‌جمع عضوهای آن برابر i - xj باشد تا حاصل‌جمع xj و آن مجموع برابر i شود.

الگوریتم شبهه چندجمله‌ای[ویرایش]

الگوریتم به این نحو کار می‌کند که یک جدول با \lfloor N/2 \rfloor سطر و n ستون حاوی مقادیر بازگشتی می‌سازد. هنگامی که کل جدول ساخته شد، مقدار ( p (\lfloor N/2 \rfloor , n را در خروجی برمی‌گرداند. در شکل زیر یک نمونه از جدول P را ملاحظه می‌نمایید. در صورتی که مقدار یک خانه از جدول به مقدار خانه دیگری وابسطه باشد، یک پیکان از خانه دوم به اول در شکل رسم شده است.

(i, j ) وابستگی‌های عنصر
   INPUT:  A list of integers S
   OUTPUT: True if S can be partitioned into two subsets that have equal sum
1 function find_partition( S ):
2     n ← |S|
3     Nsum(S)
4     P ← empty boolean table of size (\lfloor N/2 \rfloor  +  1) by (n + 1)
5     initialize top row (P(0,x)) of P to True
6     initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
7     for i from 1 to \lfloor N/2 \rfloor 
8          for j from 1 to n
9          P(i, j)P(i, j-1) or P(i-S[j-1], j-1)
10    return P(\lfloor N/2 \rfloor , n)

مثال[ویرایش]

در شکل زیر جدول P را برای مجموعهٔ {S = {3,1,1,2,2,1 مشاهده می‌کنید.

P تأثیر اجرای الگوریتم روی جدول

زمان اجرا[ویرایش]

پیچیدگی زمانی این الگوریتم  O(Nn) می‌باشد که  n تعداد اعضای مجموعه در ورودی است و  N حاصل‌جمع این عضوها می‌باشد.

الگوریتم‌های تقریبی[ویرایش]

الگوریتم حریصانه[ویرایش]

در این الگوریتم که روی اعضای مجموعه که به صورت نزولی مرتب شده‌اند اجرا می‌شود، هر عضو داخل زیرمجموعه‌ای می‌رود که مجموع اعضایش کوچکتر است. این الگوریتم هنگامی که مقادیر اعضا برابر یا کمتر از تعداد آن‌ها باشد در مجموعه باشد، به خوبی کار می‌کند. زمان اجرای این الگوریتم  O(n log(n)) است.

بدیهی است که این الگوریتم ممکن است درست عمل نکند. برای مثال برای مجموعه {S = {5, 5, 4, 3, 3 الگوریتم حریصانه زیرمجموعه‌های {S1 = {5, 4 و {S2 = {5, 3, 3 را انتخاب می‌کند در حالی که پاسخ صحیح {S1 = {5, 5 و {S1 = {4, 4, 4 است.

این روش جوابی به اندازه ۴/۳ برابر جواب بهینه را می‌دهد. یعنی اگر این الگوریتم دو جواب  S_{1} و  S_{2} را بدهد، آنگاه:

 max(sum(S_{1}),sum(S_{2})) \leq 4/3OPT

در زیر شبه‌کد الگوریتم حریصانه آورده شده است.

   INPUT:  A list of integers S
   OUTPUT: An attempt at a partition of S into two sets of equal sum
1 function find_partition( S ):
2     A ← {}
3     B ← {}
4     sort S in descending order
5     for i in S:
6         if sum(A) <sum(B)
7              add element i to set A
8         else
9              add element i to set B
10     return {A, B}

الگوریتم تفاضلی[ویرایش]

یکی دیگر از الگوریتم‌های اکتشافی الگوریتم تفاضلی است که در هر مرحله دو عدد از مجموعه انتخاب می‌کند و آن‌ها را با تفاضلشان جایگزین می‌کند. این در واقع به معنای قرار دادن این دو عدد در دو زیرمجموعه مجزا می‌باشد بدون اینکه مشخص شود هرکدام از آن‌ها داخل کدام زیرمجموعه می‌شوند. این اگوریتم بهتر از الگوریتم حریصانه عمل می‌کند اما همچنان برای نمونه‌هایی از مسأله که در آن تعداد اعضای مجموعه به صورت نمایی هستند جواب خوبی نمی‌دهد.

نمونه‌های سخت[ویرایش]

مجموعه‌های که یک و یا هیچ تقسیم بندی برای آن‌ها وجود ندارد، نسبت به اندازه ورودی‌شان مشکل‌ترین هستند. هنگامی که مقادیر اعضا نسبت به اندازه مجموعه کوچک است، احتمال تقسیم‌بندی بهینه بیشتر است. پس می‌گوییم مسأله دستخوش تغییر فاز شده است بدین معنا که برای بعضی از مجموعه‌ها محتمل و برای برخی دیگر غیر محتمل است.

اگر m را تعداد بیت‌های مورد نیاز برای نشان دادن اعداد داخل مجموعه باشد و n اندازه مجموعه باشد، بنابراین شرط m/n <1 به جواب‌های زیادی منتهی می‌شود در حالی که m/n> 1 دارای جواب‌های کمتر و در برخی موارد بدون جواب است. در نتیجه هرچه n و m بیشتر می‌شوند، احتمال تقسیم‌بندی بهینه بین ۰ و ۱ در نوسان است.

مسأله تقسیم‌بندی Kتایی[ویرایش]

حالت دیگری از مسأله تقسیم بندی به نام تقسیم‌بندی ۳تایی وجود دارد که مسأله تقسیم مجموعه S به S|/3| زیرمجموعه با مجموع‌های برابر است. این مسأله با مسأله تقسیم‌بندی متفاوت است و هیچ راه‌حل شبه چندجمله‌ای برای آن وجود ندارد مگر P=NP.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

http://en.wikipedia.org/wiki/Partition_problem