فصل 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 هست.