فصل 8 وزیرانی: کوله پشتی

اگر یک مساله np-سخت بهینه سازی داشته باشیم که یک تابع هدف f دارد، الگوریتم A را برای این مساله یک شمای تقریبی می نامیم اگر به ازای ورودی های I و اپسیلون که I یک نمونه از مساله و اپسیلون مثبت پارامتر خطا است، جوابی که بر می گرداند اگر مساله کمینه سازی است 1+epsilon برابر جواب بهینه و اگر ماکسیمم کردن است 1-epsilon برابر جواب بهینه باشد.

اگر A به ازای هر اپسیلون مثبت در زمان چندجمله ای بر حسب نمونه I اجرا شود به آن شمای تقریبی با زمان چندجمله ای (PTAS) می گویند.

اگر A به ازای هر اپسیلون مثبت در زمان چندجمله ای بر حسب نمونه I و 1/epsilon اجرا شود به آن شمای تقریبی با زمان چندجمله ای کامل (FPTAS) می گویند.

بهترین جوابی که برای یک مساله np-سخت می توان داشت FPTAS است. کوله پشتی از این مساله ها است.

مساله کوله پشتی: مجموعه S={a1,...,an} از اشیا داده شده که هر کدام یک اندازه ی صحیح size(ai) دارند و سود صحیح profit(ai) و کوله پشتی هم ظرفیت B (صحیح) دارد. یک زیرمجموعه از اشیا که جمع آنها کمتر مساوی B و سود آنها ماکسیمم باشد پیدا کنید.

یک راه بدیهی برای این مساله مرتب کردن اشیا بر حسب نسبت سود به اندازه ی آنها و برداشتن حریصانه ی اشیا به این ترتیب است. می توان نشان داد که این مساله می تواند عملکرد خیلی بدی داشته باشد. (تمرین 8.1)

* الگوریتم شبه چندجمله ای برای کوله پشتی

ما تا حالا فرض می کردیم که اعداد باینری هستند (هزینه ی نمونه) ولی اگر اعداد را یونری (unary) در نظر بگیریم، اندازه ی مساله تعداد بیت های لازم برای نوشتن آن به صورت یونری است. به الگوریتمی که بر حسب اندازه ی نمونه چندجمله ای باشد کارا می گویند. (efficient).

به الگوریتمی که زمان اجرای آن روی نمونه I به اندازه ی یونری مساله وابسته باشد، شبه چندجمله ای می گویند.

کوله پشتی np-سخت است ولی الگوریتم شبه چندجمله ای دارد. همه ی الگوریتم های مسائل np-سخت که شبه چندجمله ای هستند با برنامه نویسی پویا حل می شوند. (dynamic programming)

P=ماکسیمم سود بین اشیا؛ در این صورت کران بالای بدیهی مساله nP است.

S(i,p) = به ازای هر i بین 1 تا n و هر p بین 1 تا nP : زیرمجموعه ای از اشیای 1 تا i که سود p دارد و اندازه ی آن کمینه است.

َA(i,p) = اندازه ی مجموعه ی S(i,p) و بینهایت اگر چنین مجموعه ای وجود نداشته باشد.

ما برای هر سود p مقدار A(1,p) را می دانیم (شی a1 را برداریم و سود آن را ببریم و در بقیه حالت ها بینهایت.)

دنباله ی بازگشتی زیر نجوه ی محاسبه ی مقادیر A(i,p) را در زمان O(n^2P) نشان می دهد:

بیشترین سودی که می توان با اشیای با مجموعه اندازه ی کمتر از B به دست آورد، ماکسیمم سود A(n,p) هایی است که کمتر مساوی B اند.

این یک جواب شبه چندجمله ای برای کوله پشتی می دهد.

* یک FPTAS برای کوله پشتی

دقت کنید که اگر سود اشیا کوچک باشد، مثلا کمتر از چندجمله ای بر حسب n باشد، در این صورت این الگوریتم چندجمله ای معمولی خواهد بود چون زمان آن چندجمله ای بر حسب اندازه ی نمونه است. (باینری). ایده ی اصلی به دست آوردن FPTAS استفاده از همین است: ما بیتهای کم ارزش سود اشیا را بسته به اپسیلون در نظر نمی گیریم، در نتیجه سود جدید می تواند به صورت چندجمله ای بر حسب n و 1/epsilon دیده شود. این به ما امکان پیدا کردن جواب با سود حداقل 1-epsilon برابر بهینه در زمان چندجمله ای بر حسب n و 1/epsilon را می دهد.

الگوریتم 8.2: FPTAS برای کوله پشتی

1) یک اپسیلون مثبت داده شده، K=epsilon*P/n قرار بده.

2) به ازای هر شی ai، سود جدید آن را کف سود قبلی تقسیم بر K قرار بده.

3) با این سودهای جدید الگوریتم dp را اجرا کن و مجموعه با بیشترین سود را به دست بیاور. S'

4) S' را برگردان.

لم 8.3. اگر A زیرمجموعه ای باشد که الگوریتم بر می گرداند، آنگاه:

profit(A) >= (1-epsilon)*OPT

اثبات: فرض کنید O زیرمجموعه بهینه باشد. به ازای هر شی a به دلیل رند کردن به پایین K*profit'(a) می تواند از profit(a) کمتر باشد، اما نه بیشتر از K.

{

طبق تعریف جزء صحیح می دانیم که حداکثر K تا از مقدار کم شده (در واقع K-1) پس برای هر شی داریم:

K * (profit(ai)-(K-1))/K <= K.profit'(ai) ==>

profit(ai) - K <= K*profit'(ai) ==>

profit(ai)-K*profit'(ai) <= K ==>

(sum): profit(O)-K*profit'(O) <= |O|*K <= n*K

}

پس:

profit(O)-K*profit'(O) <= nK

در گام dp باید جوابی که برمی گردد حداقل به خوبی O برحسب سودهای جدید باشد. پس:

...