فصل 11 وزیرانی: فروشنده دوره گرد تقریبی

در این فصل یک PTAS برای حالت خاصی از فروشنده دوره گرد می دهیم که در آن نقاط در فضای d بعدی اقلیدسی داده شده اند. مثل قبل ایده ی اصلی PTAS تعریف یک جواب دانه درشت {منظور جوابی است که جزئیات آن حذف شده باشد} بر حسب پارامتر خطای اپسیلون و پیدا کردن جواب آن با برنامه ریزی پویا (dp) است. ویژگی این مساله این است که این بار به طور قطعی نمی توانیم جواب دانه درشت را مشخص کنیم و به صورت احتمالی این کار را انجام می دهیم.

مساله 11.1. فروشنده دوره گرد افلیدسی: برای d ثابت، n نقطه در R^d داده شده است، مساله پیدا کردن دور با کمترین طول گذرنده از n نقطه است. فاصله ی بین دو نقطه x و y فاصله ی اقلیدسی بین آنهاست. (جذر مجموع توان 2 تفاضل ابعاد متناظرشان!)

11.1. الگوریتم

در دو بعد حل می کنیم تعمیم آن به ابعاد بالاتر ساده است.

جعبه محیطی (bounding box) یک نمونه از مساله کوچکترین مربع با اضلاع موازی محورهاست که همه ی نقاط درون آن باشد. با کمی تقسیم بندی در ورودی می توانیم فرض کنیم طول ضلع این مربع L، برابر 4n^2 است و یک توری به ضلع یک روی آن طوری تعریف شده که هر نقطه روی یک راس توری می افتد. (تمرین 11.1). به علاوه بدون از دست رفتن عمومیت مساله فرض کنید n توان 2 باشد و قرار بدهید: L=2^k که k=2+lg n

"برش اولیه" جعبه محیطی یک افراز بازگشتی به مربع های کوچکتر است. پس مربع L * L به چهار مربع L/2 * L/2 تقسیم می شود و ... . این تقسیم را به صورت یک درخت چهارتایی (درجه هر راس 4) می بینیم T که ریشه آن جعبه محیطی است. فرزندان آن 4 مربع L/2*L/2 اند. گره های درخت T دارای level هستند. ریشه 0 و فرزندانش 1 و ... . پس مربع سطح iام ابعادش L/2^i * L/2^i است. تا رسیدن به مربع 1*1 ادامه می دهیم. T عمق k=O(log n) دارد. منظور از یک "مربع مفید" مربعی است که نمایانگر یک راس درخت باشد. {خلاصه همان quad-tree است!}

اپسیلون را هم روی ارتفاع درخت تعریف کرده است. (درشت دانه بودن). می خواهیم ثابت کنیم که مسیری که ساخته می شود 1+اپسیلون تقریب است. قبل از آن نشان می دهیم که چرا این موضوع PTAS بودن را نتیجه می دهد.

لم 11.2: یک گشت که فقط از راسها و وسط راسها بگذرد و خودش را قطع نکند (خوش رفتار باشد). حتما گشت خوش رفتار دیگری هست که هر وسط راس را حداکثر دو بار می بیند و طول آن کمتر مساوی طول گشت اولی است.

اثبات: دلیل اصلی این است که حذف تقاطع با خود به وسیله پرش یک گشت کوتاهتر می دهد. (نامساوی مثلث). اگر گشت اولی از وسط یالی که روی خط L است بیشتر از دو بار عبور کند، می توانیم در دو طرف L انقدر پرش انجام بدهیم که وسط یال حداکثر دو بار دیده شود. اگر این تقاطع با خود های دیگر بسازد به همین ترتیب می توانیم حذفشان کنیم.

لم 11.3: گشت توصیف شده در بالا را به طور بهینه می توان در زمان n^O(1/epsilon) به دست آورد. (2 به توان عمق درشت شده!)

اثبات: حالت بندی، dp، پرانتزگذاری صحیح

11.2. اثبات درستی

همیشه طول دور تقریب 1+اپسیلون جواب بهینه نیست. به جای این خانواده ی بزرگتری از انحرافها را می سازیم و نشان می دهیم که برای هر چیدمان نقاط حداقل نصف حالتها شرایط مورد نظر را دارند. یکی را تصادفی بر می داریم. ...

لم 11.4: تعداد تقاطع های گشت جواب کمتر مساوی 2 برابر جواب بهینه است.

در ادامه حقیقتی که باعث به دست آمدن PTAS برای مساله می شود آمده است.

قضیه 11.5: برداشتن a و b (شروع خطوط تقسیم) به صورت تصادفی یکنواخت از بازه ی 0-L باعث افزایش میانگین هزینه ساخت جواب بهینه به میزان کمتر از 2 اپسیلون برابر جواب بهینه می شود.

اثبات: امیدریاضی هزینه را محاسبه می کنیم و بر حسب اپسیلون به دست می آوریم. (با توجه به بازه ی شامل ارتفاع دانه درشت)

نکته 11.6: ایده های منجر به قضیه 11.5 به صورت زیر خلاصه می شوند. چون خطوط سطح پایینتر مربع های بزرگتری مجاورشان است، ما مجبور بودیم وسط ضلع های آنها را دورتر بگذاریم تا هر کدام حداکثر 4 برابر عمق دانه درشت وسط ضلع داشته باشند (که باعث می شود dp در زمان چندجمله ای امکان پذیر باشد). اما این باعث شد که ما نمونه های بیشتری بسازیم که هیچ جواب کوچکی نداشتند. (تمرین 11.3). به علاوه تعداد خطوط کمتری سطح های پایین دارند. (قضیه 11.5).

نتیجه 11.7: احتمال اینکه تصادفی یکنواخت شروع توری را انتخاب کنیم و طول گشت حداکثر 4 اپسیلون برابر جواب بهینه شود بیشتر مساوی 1/2 است.

PTAS: یک تقسیم بندی تصادفی می سازیم و جواب بهینه را برای آن پیدا می کنیم (با dp). (طبق لم 11.3). الگوریتم را می تواینم با امتحان کردن همه ی حالتهای شیفت و چاپ کمترین در بین آنها غیرتصادفی کنیم.

قضیه 11.8: برای فروشنده دوره گرد اقلیدسی در صفحه یک PTAS هست.

فصل 9 تقریبی Bin Packing

مساله: n شی با اندازه های a1,..,an در بازه 0 تا 1 (بزرگتر از 0) داده شده اند. بسته بندی به سطل های با اندازه 1 پیدا کنید که تعداد سطلهای لازم را مینیمم کند.

الگوریتم تقریب 2:

First-Fit: ترتیب دلخواه از اشیا را در نظر می گیریم. در گام i-ام لیستی از سطلهای نیمه پر داریم: B1,..,Bk. سعی می کنیم شی بعدی (ai) را در یکی از این جعبه ها بگذاریم (به همین ترتیب). اگر در هیچ کدام از این سطلها جا نشد، یک سطل جدید B(k+1) باز می کنیم و ai را درون آن می گذاریم. اگر الگوریتم از m سطل استفاده کند، حداقل m-1 سطل بیش از نصفشان پر است. {چون اگر کمتر از نصف قبلی پر باشد و کمتر از نصف سطل جدید هم پر باشد این نصفه را می توانستیم در همان سطل قبلی بریزیم. پس سطل نیمه پر نداریم مگر سطل آخری.} یعنی:

sum_i_1_n(ai) > (m-1)/2

چون جمع وزن اشیا کران پایین روی جواب بهینه است، {همه ی سطلها کامل پر شده باشند} پس

(m-1)/2 < OPT ==> m-1 <2OPT ==> m <= 2OPT

اما اشکال این است:

قضیه 9.2: برای هر اپسیلون مثبت، هیچ الگوریتم تقریبی نیست که 3/2-epsilon تقریب برای مساله بسته بندی سطلی باشد. (مگر اینکه P=NP باشد.)

اثبات: اگر چنین الگوریتمی بود، مساله NP-سخت تصمیم گیری وجود افرازی که n عدد نامنفی a1,...,an را به دو مجموعه که جمع اعضای هر کدام 1/2sum(ai) باشد را حل می کند. بدیهی است که جواب این سوال "بله" است اگر و تنها n شی بتوانند به دو سطل با اندازه ی 1/2sum(ai) ها بسته بندی شوند. اگر جواب "بله" باشد الگوریتم تقریبی با ضریب 3/2-epsilon یک جواب بهینه برای بسته بندی می دهد و مساله افراز را حل می کند.

{حس می کنم باید جایی در این اثبات تقسیم بر مجموع می کرد که اندازه ی اشیا بین 0 و 1 شود!}

9.1. یک شمای تقریبی چندجمله ای مجانبی

لم 9.4: اگر K یک عدد صحیح نامنفی ثابت و اپسیلون ثابت داده شده باشد. اگر هر شی در بسته بندی سطلی اندازه اش حداکثر اپسیلون باشد و تعداد اندازه های مختلف K باشد، الگوریتم چندجمله ای هست که این مساله را به صورت بهینه حل می کند.

اثبات: تعداد اشیای سطل کمتر از یک بر اپسیلون است. (M). پس تعداد سطلهای با میزان پر بودن متمایز کمتر از انتخاب M از M+K است. (R). (تمرین 9.4). که یک ثابت بزرگ است. بدیهی است که تعداد سطلهای به کار رفته حداکثر n است. {هر شی در یک سطل!}. پس تعداد بسته بندی های ممکن کمتر از انتخاب R از R+n است که چندجمله ای برحسب n است. (تمرین 9.4). شمارش اینها و انتخاب بهترین بسته بندی جواب بهینه را می دهد.

لم 9.5: به ازای اپسیلون مثبت ثابت، نسخه ای از مساله بسته بندی سطلی را که در آن اشیا اندازه حداقل اپسیلون دارند در نظر بگیرید. یک الگوریتم تقریبی با زمان چندجمله ای هست که این مساله را با تقریب 1+epsilon حل می کند.

اثبات: فرض کنید I نمونه ای از مساله ورودی باشد. اشیا را به ترتیب اندازه شان مرتب کنید و آنها را به K=ceil(1/epsilon^2) دسته افراز کنید که هر دسته حداکثر Q=floor(n*epsilon^2) شی دارد. توجه کنید که دو دسته ممکن است اشیای هم اندازه داشته باشند.

نمونه ای از مساله (J) را با رند کردن اندازه ی هر شی به اندازه ی بزرگترین شی آن دسته بسازید. نمونه J حداکثر K اندازه شی متمایز دارد.

پس طبق لم 9.4 می توانیم جواب بهینه برای J پیدا کنیم. بدیهی است که این بسته بندی برای مساله اولیه هم جواب معتبر است. در ادامه نشان می دهیم که جواب بهینه J یک تقریب 1+اپسیلون برای جواب بهینه I است.

یک نمونه ی J' از مساله می سازیم که در آن وزن هر شی را به کمترین وزن آن دسته رند می کنیم. بدیهی است که جواب بهینه J' کمتر از جواب بهینه مساله است. مشاهده می کنیم که یک بسته بندی برای J' برای همه اشیا به جز Q تا بزرگترین شی J می دهد. (تمرین 9.6) پس:

OPT(J) <= OPT(J') + Q <= OPT(I)+Q

چون هر شی I اندازه اش حداقل اپسیلون است پس OPT(I) >= n*epsilon است پس Q = floor(n*epsilon^2) <= epsilon*OPT. پس حکم نتیجه می شود.

قضیه 9.3: برای هر اپسیلون مثبت کمتر مساوی 1/2 یک الگوریتم تقریبی A_epsilon هست که زمان اجرای چندجمله ای بر حسب n دارد و مساله بسته بندی سطلی را با حداکثر (1+2epsilon) * بهینه+1 سطل حل می کند.

دنباله ی الگوریتم های A_epsilon یک PTAS مجانبی برای بسته بندی سطلی است؛ چون برای هر اپسیلون مثبت یک N مثبت وجود دارد و یک الگوریتم چندجمله ای در این دنباله هست (B) که تقریب 1+اپسیلون برای همه ی ورودی هایی که هزینه جواب بهینه بیشتر مساوی N دارند می دهد. 

اثبات: فرض کنید I نمونه ی داده شده باشد و I' را با حذف اشیای با وزن کمتر از اپسیلون از روی آن بسازید. طبق لم 9.5 برای I' بسته بندی با تقریب 1+اپسیلون برابر جواب بهینه برای I' هست. بعد اشیای با وزن کمتر از اپسیلون را با روش First-Fit در سطلهای I' می گذاریم. سطلهای جدید به شرطی ساخته می شوند که در سطلهای قبلی جا نباشد.

اگر هیچ سطل جدیدی لازم نشد که خود به خود تقریب 1+اپسیلون هست. در حالت دوم، M را جمع سطلهای به کار رفته بگیرید. بدیهی است که همه ی سطلها به جز آخری به اندازه ی 1-اپسیلون پر خواهند بود. پس جمع اشیای I حداقل (M-1)(1-epsilon) است. چون این یک کران پایین برای جواب بهینه است به دست می آوریم:

M <= OPT/(1-epsilon)+1 <= (1+2*epsilon)OPT+1

که از فرض اپسیلون کمتر مساوی 1/2 برای نامساوی سمت راست استفاده کردیم. پس برای هر مقدار اپسیلون بین 0 تا 1/2 یک الگوریتم چندجمله ای داریم که تقریب بالا را دارد.

الگوریتم 9.6: الگوریتم A_epsilon

1) همه ی اشیای با وزن کمتر از اپسیلون را حذف کن.

2) اندازه ها را رند کن تا تعداد وزن های متمایز اشیا ثابت باشد (لم 9.5).

3) بسته بندی بهینه را به دست بیاور. (لم 9.4).

4) از این بسته بندی برای اندازه های اصلی استفاده کن.

5) اشیای با وزن کمتر از اپسیلون را با First-Fit بسته بندی کن.

تمرین های فصل 8 وزیرانی

8.1- الگوریتم حریصانه برای کوله پشتی را در نظر بگیرید. اشیا را بر حسب نسبت سود به اندازه ی آنها نزولی مرتب کنید و حریصانه اشیا را به این ترتیب بردارید. نشان دهید حالتی هست که این الگوریتم به میزان دلخواه بد عمل کند.

من هر مثالی به ذهنم رسید دو برابر بیشتر نشد. :)

فصل 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 برحسب سودهای جدید باشد. پس:

...

حل 2_15 وزیرانی

البته اصل حل مربوط به یک سوال دیگر در کتاب WS بود اما فکر کنم این سوال هم همین طوری حل می شود. (حداقل می دانم سوالهایی که حل آنها در این دو کتاب نیامده در امتحان هم نمی آید!)

تمرین های فصل 2 WS (زمانبندی کارها) 2.1,2.3

2- فرض مساله را به صورت زیر می نویسیم

OPT/3 < w_1 <= w_2 <=...<=w_m

الگوریتم LPT هم کارها را به ترتیب از زمان اجرای زیاد به کم انجام می دهد. می خواهیم ثابت کنیم این کار به جواب بهینه می رسد.

از فرض داده شده می فهمیم به هر پردازنده حداکثر 2 کار می رسد. جواب بهینه جوابی است که زوج کارهایی که به یک پردازنده داده می شوند، جمعشان مینیمم شود. اگر تعداد پردازنده ها از نصف کارها بیشتر باشد که کارهای با زمان طولانی تر به تنهایی روی یک پردازنده اجرا می شوند و کارهای با زمان کمتر هر دو تا روی یک پردازنده اجرا می شوند. پردازنده هایی که به آنها دو کار داده شده است، باید طوری باشند که جمع این دو کار مینیمم شود. برای این کار بهترین کار این است که کار با بیشترین زمان و کمترین زمان را با هم به یک پردازنده بدهیم.

3- الگوریتم زمانبندی لیست کارها را به ترتیبی دلخواه در یک لیست می گذارد و کار بالای لیست را به اولین پردازنده ای که بیکار شد می دهد. اثبات آن به اثبات جستجوی محلی ارجاع داده شده بود.

بر خلاف اثبات سوال بدون اولویت نمی توانیم از میانگین به عنوان کران پایین استفاده کنیم. 

فصل 2 WS

* زمانبندی کارهای دارای ددلاین روی یک ماشین

هدف این کار می تواند تمام شدن همه ی کارها در کمترین زمان، کم شدن میانگین زمان انجام کار باشد. ما ساده ترین نسخه را حل می کنیم.

مساله: فرض کنید n کار را می خواهیم روی یک ماشین زمانبندی کنیم که هر ماشین در هر زمان می تواند یک کار را پردازش کند و کار را بعد از شروع آن باید تا اتمام آن ادامه دهد. فرض کنید پردازش کار jام از زمان مشخصی زودتر قابل انجام نباشد (r_j). فرض می کنیم زمانبندی در زمان 0 شروع می شود و هر زمان انجامی مثبت است. به علاوه کار jام یک زمان پایان d_j دارد. اگر کار را در زمان Cj تمام کنیم، دیرکرد آن Lj = Cj-dj است، ما می خواهیم کارها را طوری زمانبندی کنیم که L_max را مینیمم کنیم که L_max ماکسیمم دیرکردها (Lj) ها است.

این مساله NP-hard است. حتی نسخه ی تصمیم گیری اینکه L_max < 0 است (= تصمیم گیری اینکه همه کارها می توانند قبل از زمان مهلتشان تمام شوند) هم strongly np-hard است.

ما در زندگی روزمره مان با یک الگوریتم تقریبی ساده این کار را انجام می دهیم: روی کاری با نزدیک ترین مهلت تمرکز کنید. نشان می دهیم که در شرایط خاصی قابل اثبات است که این کار خوبی است. هرچند همان طور که گفته شد جواب نزدیک بهینه (تقریبی) ندارد. اگر یک الگوریتم تقریبی برای آن بود، برای هر مساله با جواب L_max = 0 راه حل تقریبی مساله در حالت کلی برای آن ضریب تقریب * 0 = 0 پس باید برای مساله تمام شدن همه ی کارها قبل از ددلاین یک راه حل بهینه باشد که ممکن نیست مگر اینکه P=NP. برای حالت هایی که L_max مینیمم در آنها منفی شود، کار سخت تر است. یک حالت ساده ی رخ دادن این مشکل این است که فرض کنیم همه ی زمان های پایانی منفی هستند که باعث می شود جواب همیشه مثبت باشد. برای این حالت یک الگوریتم 2-تقریبی می دهیم.

ابتدا یک کران پایین خوب برای جواب بهینه برای مساله زمانبندی می دهیم. فرض کنید S زیرمجموعه ای از کارها باشد و r(S) را مینیمم r_j ها قرار دهید (زمان شروع ها) و p(S) را جمع pjها (زمان پردازش ها) و d(S) را ماکسیمم dj ها (زمان پایان ها). L* جواب بهینه است.

لم: برای هر زیر مجموعه از کارها داریم:

L*_max >= r(S)+p(S)-d(S)

اثبات:

هر کاری در زودترین زمانی که می تواند برسد r(S) است که اگر همه ی کارها پشت سر هم انجام شوند p(S) طول می کشد پس زمان بیشتر از r(S)+p(S) است که از طرفین d(S) را کم می کنیم. (پایان اثبات)

یک کار j در زمان t مجاز است اگر زمان رسیدن r_j از t کمتر مساوی باشد. الگوریتم زیر را در نظر می گیریم: در هر لحظه که ماشین بیکار است، کار در دسترس بعدی که زودترین ددلاین را دارد شروع کن. به این کار earliest due date (EDD) (زودترین مهلت انجام) می گویند.

قضیه: قانون EDD یک الگوریتم 2-تقریبی برای مساله کمینه کردن ماکسیمم تاخیر (L_max) روی یک ماشین با توجه به زمانهای رسیدن و با فرض مهلت پایان های منفی است. {با فرض اینکه مهلت کارها گذشته باشد.}

اثبات: جواب الگوریتم را در نظر بگیرید. فرض کنید j کاری باشد که L_max به ازای آن رخ می دهد. Lmax = Cj-dj. روی زمان Cj بحث می کنیم: اولین زمانی را پیدا کنید t<= Cj که ماشین به ازای آن در کل بازه ی بسته ی t تا باز Cj در حال کار بوده است. چندین کار می توانسته اند در این زمان پردازش شوند. ما فقط کارهایی را که ماشین به ازای آنها مدتی بیکار نباشد لازم داریم. فرض کنید S مجموعه کارهایی باشد که در بازه ی t بسته تا Cj باز پردازش می شوند. با توجه به نحوه انتخاب t، می دانیم که قبل از t هیچ کدام از این کارها در دسترس نبوده اند ( و حتما یک کار در S در زمان t در دسترس بوده است)؛ پس r(S) = t. به علاوه چون تنها کارهای موجود در S در طول این زمان پردازش می شوند: p(S) = Cj-t=Cj-r(S). پس Cj <= r(S)+p(S).

چون d(S) منفی است پس طبق لم قبل:

L*_max >= r(S)+p(S)-d(S) >= r(S)+p(S) >= Cj

با استفاده از همین لم و در نظر گرفتن مجموعه تک عضوی کار j-ام داریم:

L*_max >= rj+pj-dj >= -dj

از جمع دو نامساوی قبل به دست می آید:

2*L*_max >= Cj-dj

Cj-dj = L_max

==> L_max <= 2*L*_max

----------------------------------------------------------------------------------------------------------------------------------------

* زمانبندی کارها روی ماشین های موازی یکسان

نسخه ای از مساله که در آن چند ماشین داریم و هیچ زمان شروعی نداریم، اما هدف ما مینیمم کردن زمانی است که همه ی کارها تمام شوند. فرض کنید n کار باید پردازش شوند، و m ماشین یکسان هستند که به طور موازی کار می کنند و به هر کدام هر کار ممکن است اختصاص داده شود. هر کار باید روی یکی از این ماشینها به مدت pj بدون وقفه اجرا شود و همه ی کارها در زمان 0 در دسترس هستند. هر ماسین می تواند یک کار را در هر زمان انجام دهد. هدف تمام کردن همه ی کارها در زودترین زمان است، یعنی اگر کار j در زمان Cj (با فرض اینکه زمانبندی از 0 شروع شود) تمام شود، می خواهیم C_max را مینیمم کنیم که C_max ماکسیمم C_j ها است. که معمولا makespan یا طول برنامه نامیده می شود. یک دید معادل به مساله، مساله load-balancing است: n چیز داریم که وزن pj دارند و بین m ماشین توزیع شده اند، هدف تخصیص دادن هر چیز به یک ماشین است که ماکسیمم جمع وزن داده شده به یک ماشین را مینیمم کنیم.

این مساله انقدر ساده است که هم جستحو محلی هم حریصانه برای طول برنامه تقریب 2 می دهند.

الگوریتم جستجوی محلی به صورت تغییرات محلی یا حرکت های محلی است که یک جواب ممکن را به یک جواب ممکن دیگر تبدیل می کنند. ساده ترین جستجوی محلی برای این مساله زمانبندی به صورت زیر است: با یک زمانبندی شروع کنید؛ کار j را در نظر بگیرید که آخرین کاری است که تمام می شود، چک کنید که ماشینی وجود دارد که بتوان این کار را به آن داد و زودتر تمام شود. اگر هست، کار j را به آن ماشین بدهید. می توانیم تشخیص دهیم که کار j را به ماشین دیگر منتقل کنیم یا نه، با چک کردن اینکه آیا ماشینی وجود دارد که این کارهایش را زودتر از Cj-pj تمام می کند. {یعنی قبل از شروع کار j توسط ماشین فعلی بیکار شده باشد.} الگوریتم جستجوی محلی این کار را تا زمانی که آخرین کار تمام شده نتواند منتقل شود ادامه می دهد.

برای تحلیل عملکرد این الگوریتم جستجوی محلی، ما ابتدا یک کران پایین روی طول زمانبندی بهینه C*_max می دهیم. چون هر کار باید پردازش شود، داریم:

2.3: C*_max >= max(pi)

از طرف دیگر می دانیم که در کل باید P = sum(pi) واحد پردازش انجام شود و کلا m ماشین داریم. پس میانگین P/m کار به هر ماشین داده می شود، پس ماشینی هست که حداقل به اندازه میانگین کار داشته باشد:

2.4: C*_max >= ( sum(pi) )/m

جوابی که توسط الگوریتم جستجوی محلی تولید شده است را در نظر بگیرید. فرض کنید j کاری باشد که در برنامه نهایی آخرین کاری باشد که انجام می شود؛ پس زمان اتمام کار j یعنی Cj جواب مساله است. چون الگوریتم با کار j-ام پایان یافته است، پس همه ی پردازنده های دیگر باید از شروع زمان (0) تا زمان شروع کار j-ام مشغول باشند. Sj = Cj-pj (زمان شروع کار j). می توانیم زمانبندی را به دو بازه ی زمانی مجزا تقسیم کنیم، یکی از 0 تا شروع j یعنی Sj و دیگری از آن زمان تا پایان کل برنامه. طبق نامساوی 2.3 بازه ی دوم اندازه ی حداکثر C*_max دارد. حالا بازه ی اول را در نظر بگیرید، چون همه ی ماشین ها در این زمان مشغول هستند پس m*Sj زمان کار در این بازه انجام شده است که بدیهی است از کل کاری که باید انجام شود یعنی sum(pi) ها کمتر است. پس:

2.5: Sj <= (sum(pi) / m)

با ترکیب این نامساوی و نامساوی 2.4 به دست می آید:

Sj <= C*_max

پس، طول برنامه قبل از شروع کار j حداکثر C*_max بوده است و طول آن بعد از انجام کار هم همین قدر است، پس طول برنامه ی الگوریتم حداکثر دو برابر جواب بهینه (2C*_max) است.

حالا زمان اجرای این الگوریتم را در نظر بگیرید. این جستجوی محلی این خاصیت را دارد که دنباله ی C_max های تولید شده در آن هیچ گاه نزولی نیست ( می تواند ثابت باشد اما در این صورت تعداد ماشین هایی که به مقدار زمان بیشینه می رسند کاهش می یابد). یک فرض طبیعی این است که وقتی کاری را به یک ماشین دیگر می دهیم، آن را به ماشینی بدهیم که در حال حاضر زودتر از همه کارش را تمام می کند. ما زمان اجرای این نسخه را به جای قبلی به دست می آوریم. فرض کنید C_min زمان اتمام ماشینی باشد که زودتر از همه کارهایش را تمام می کند. یک نتیجه ی تمرکز روی این نسخه این است که C_min هیچ گاه کم نمی شود (و اگر همان قدر بماند، تعداد ماشینهایی که این کمترین مقدار را به دست می آورند کاهش می یابد). در ادامه نشان می دهیم که این نتیجه می دهد که ما هیچ وقت یک کار را دو بار جا به جا نمی کنیم. فرض کنید این ادعا درست نباشد، اولین کار j را که دو بار جا به جا شده است در نظر بگیرید، فرض کنید از ماشین i به ماشین i' و بعد از آن به i*. وقتی کار j از ماشین i به i' منتقل می شود، در زمان Cmin برنامه فعلی شروع می شود. به طور مشابه وقتی کار j از i' به i* منتقل می شود، در زمان C'_min شروع می شود. به علاوه هیچ تغییری روی ماشین i' در بین این دو انتقل رخ نداده اشت. پس C'_min باید اکیدا کمتر از C_min باشد (تا انتقال یک عمل بهبود دهنده باشد) اما این با ادعای C_min در طول اجرای الگوریتم جستجوی محلی غیر نزولی است متناقض است. پس هیچ کاری دو بار منتقل نشده است و بعد از حداکثر n گام، الگوریتم متوقف می شود. پس ما قضیه زیر را ثابت کردیم:

قضیه 2.5: الگوریتم جستجوی محلی برای زمانبندی کارها روی ماشین های موازی یکسان یک الگوریتم 2-تقریبی است.

تحلیل ضریب تقریب می تواند کمی بهبد یابد. در به دست آوردن نامساوی 2.5، کار j را بین کارهایی که قبل از شروع کار j تمام می شوند حساب کرده ایم. پس می توانیم به دست بیاوریم:

Sj <= (sum( pi) -pj) / m

==> total length <= pj+(sum(pi)-pj)/m = (1-1/m)pj+sum(pi) /m

با اعمال دو کران پاینن 2.3 و 2.4 روی دو جمله بالا می توانیم نشان دهیم که طول برنامه حداکثر 

(2-1/m)C*_max

است. البته تفاوت بین این کران و 2 تنها وقتی مهم است که تعداد ماشینها خیلی کم باشد.

-----

الگوریتم طبیعی دیگری که برای محاسبه برنامه است الگوریتم حریصانه ای است که هر کار را به محض اینکه یک ماشین بیکار شد به آن اختصاص می دهد. این الگوریتم معمولا list scheduling algorithm نامیده می شود، چون می توان الگوریتم را به صورت مرتب کردن کارها در یک لیست به ترتیب دلخواه دید که کار بعدی که انجام می شود کار سر لیست است. یک دید دیگر، از دیدگاه load-balancing است که کار بعدی لیست به ماشینی که الآن کمترین بار را دارد اختصاص داده شود. در این حالت است که الگوریتم می تواند به صورت حریصانه دیده شود. تحلیل این الگوریتم اکنون بدیهی است؛ اگر کسی از این برنامه به عنوان نقطه شروع جستجوی محلی استفاده کند، الگوریتم همان موقع اعلام می کند که زمانبندی نمی تواند بهبود داده شود. برای فهمیدن این موضوع، کار j را که یکی از کارهاست که آخرین کاری است که اجرایش تمام می شود، در نظر بگیرید. هر ماشینی تا زمان Cj-pj مشغول است، چون در غیر این صورت به آن کار j را اختصاص می دادیم. پس هیچ انتقالی امکان پذیر نیست.

قضیه 2.6: الگوریتم list scheduling برای مساله کمینه کردن طول برنامه با داشتن m ماشین یکسان موازی 2-تقریبی است.

به دست آوردن نتیجه بهتر با بهبود این الگوریتم سخت نیست. همه ی لیست ها یک برنامه را نمی دهند و طبیعی است که از قانون حریصانه ی اضافی استفاده کنیم که ابتدا کارها را به صورت غیر صعودی مرتب می کند. {نزولی غیر اکید}. یک راه برای دیدن نتیجه قضیه 2.5 و 2.6 این است که خطای نسبی طول برنامه کاملا مربوط به آخرین کار انجام شده است. پس اگر کار کوتاهی انجام شود، خطا خیلی بزرگ نمی شود. این الگوریتم حریصانه longest processing time یا به اختصار LPT نامیده می شود.

قضیه 2.7: LPT یک الگوریتم 4/3-تقریبی برای زمانبندی کارها برای مینمم کردن طول برنامه روی ماشین های موازی یکسان است.

اثبات: برهان خلف: فرض کنید یک ورودی مثال نقضی برای قضیه باشد. برای سادگی نگارش فرض کنید p1>= ...>= pn باشد. ابتدا می توانیم فرض کنیم که آخرین کاری که انجام می شود آخرین (کوتاهترین) کار در لیست است. این نتیجه می دهد (بدون از دست رفتن عمومیت مساله) که هر مثال نقضی که آخرین کار آن کوتاهترین کار نباشد و کار j-ام باشد، می توانیم ثابت کنیم که غلط است، چون کارهای j+1,...,n راحذف می کنیم، طول برنامه همان می ماند و جواب بهینه ورودی کاهش یافته نمی تواند بزرگتر باشد. پس این ورودی کاهش یافته هم یک مثال نقض است.

پس می دانیم که آخرین کاری که کامل می شود کار nام است. اگر این یک مثال نقض باشد، ما در مورد pn=pj چه می دانیم؟ اگر pj <= C*_max باشد، تحلیل قضیه 2.6 نتیجه می دهد که طول برنامه حداکثر (4/3)C*_max است و درنتیجه این یک مثال نقض نیست. پس می دانیم که در این مثال نقض فرضی، کار n ام (و در نتیجه همه کارها) زمان پردازش اکیداً بیشتر از 1/3C*_max دارند. این نتیجه ی ساده ی زیر را دارد:

در زمانبندی بهینه، هر ماشین می تواند حداکثر دو کار را پردازش کند (چون در غیر این صورت زمان پردازش آن از C*_max بیشتر می شود).

اینجا مثال نقض فرض مان به جایی رسیده است که وجود آن امکان پذیر نیست. برای ورودی های دارای این ساختار، لم بعد را به کار می بریم.

لم 2.8: برای هر ورودی مساله مینیمم کردن زمان روی ماشین های موازی یکسان که در آن نیازمندی های هر کار از 1/3 طول زمان مورد نیاز بیشتر است، longest processing time (LPT) جواب بهینه را به دست می آورد.

این لم می تواند با استفاده از چک کردن حالت ها انجام شود (تمرین 2.2). هر چند نتیجه این لم مشخص است: هیچ مثال نقضی برای این قضیه وجود ندارد پس برقرار است.

در قسمت 3.2 نشان می دهیم که می توان برای این مساله الگوریتم تقریبی با زمان چندجمله ای ارائه داد.

وبلاگ سمیه!

درس های موازی و تقریبی را دارد!

mycourse.blog.ir

تمرین های فصل 5 وزیرانی

1- نشان دهید اگر وزن یالی در نامساوی مثلث صدق نکند، آنگاه مساله k-مرکز نمی تواند تقریبی بهتر از a(n) برای هر تابع a(n) قابل محاسبه داشته باشد.

راهنمایی: از ایده قضیه 3.6 و 5.7 استفاده کنید.

5.7 = dominating set، یالهای گراف 1، یالهای دیگر 2

3.6 = وجود جواب برای مساله: هزینه ی n، عدم وجود جواب: هزینه a(n).n

حل: 

حل تمرین های WS فصل 5.1-5.3

1- در مساله k-برش ماکسیمم، گراف بدون جهت G با وزنهای نامنفی wij>=0 به ازای هر یال (i,j) گراف داده شده است. هدف افراز راسهای گراف به k قسمت V1,...,Vk است طوری که وزن یالهایی که سرهای مختلف آن در مولفه های همبندی مختلف است ماکسیمم شود.

یک الگوریتم (k-1)/k تقریبی برای MAX k-Cut بدهید.

حل: k-برش مینیمم را که با k تا برش ایزوله سبکتر به دست می آوردیم، این را با k تا برش ایزوله ی سنگین تر به دست می آوریم. (برش ایزوله را هم با سنگین ترین یالها حساب می کنیم).

میانگین وزن k-1 برش سنگینتر از میانگین وزن k برش سنگینتر بیشتر است، پس ضریب تقریب (k-1)/k است.

2-الگوریتم حریصانه زیر را برای مساله برش ماکسیمم در نظر بگیرید. فرض کنید راسها از 1 تا n برچسب زده شده اند. در تکرار اول، الگوریتم راس 1 را در U قرار می دهد. در تکرار k-ام الگوریتم راس k را یا در U یا در W می گذاریم. برای اینکه تصمیم بگیریم کدامیک از انتخابها را انجام دهیم به مجموعه یالهای F که راس k یک سر آنها است و سر دیگر آنها بین راسهای 1,...,(k-1) است، پس F={(j,k)| 1<= j <= k-1}. ما بر اساس اینکه کدام انتخاب تعداد یالهای F را که بریده می شود بیشتر می کند، عمل می کنیم.

الف) ثابت کنید که این الگوریتم 1/2-تقریبی است. (برای مساله برش ماکسیمم)

ب) ثابت کنید که این الگوریتم معادل غیرتصادفی کردن الگوریتم بخش 5.1 با روش امیدریاضی شرطی است.

حل:

الف)

OPT <= sum(deg_U(v))+sum(deg_W(v)) <= 2*sum(max(deg_U(v),deg_W(v)))

ALG(v) = max(deg_U(v),deg_W(v)) ==> ALG = sum(max(deg_U(v),deg_W(v)))

==> OPT <= 2*ALG

(نکته اینه که سوال تکراریه..؟)

ب)

pr(k in U)=1/2 = pr(k in W)

E(#edges) = E(#edges| v_k in U)Pr(v_k in U)+E(#edges| v_k in W)pr(v_k in W)=1/2(E(#edges|v_k in U)+E(#edges|v_k in W) )

b_k = argmax( E(#edges|v_k in b_k) ) ==> E(#edges|v_k in b_k) >= E(#edges)

(j,k) in F: pr((j,k) in U| v_(k-1)=b_(k-1),...) = 1 if j in W, 1-(1/2)^k if j in U

3- در برش ماکسیمم جهت دار (MAX DICUT)، یک گراف جهتدار داده شده و هر یال آن وزن نامنفی دارد wij >= 0. هدف تقسیم راسها به دو زیرمجموعه U و W است که جمع وزن یالهایی که از U به W می روند ماکسیمم شود. یک الگوریتم تصادفی 1/4-تقریبی برای این مساله بدهید.

همان استدلال و روش سوال بالا+

E(#edges) >= 1/4 OPT

که 1/4 از ضرب احتمال حضور سر اول یال در U و سر دوم آن در W به دست آمده است: 1/2*1/2=1/4