الگوریتم‌های تقریبی: نزدیک‌شدن اثبات‌پذیر به بهینه برای مسائل سخت

چرا تقریب یک پاسخ منطقی به NP-Completeness است

همان‌طور که پیش‌تر در این مجموعه بحث شد، اثبات NP-complete بودن یک مسئله شواهد قوی فراهم می‌کند که هیچ الگوریتم زمان-چندجمله‌ای راه‌حل بهینه دقیق را پیدا نمی‌کند. به‌جای رها‌کردن مسئله، یک Approximation Algorithm (الگوریتم تقریبی) عمداً تضمین یافتن راه‌حل بهینه دقیق را در ازای تضمین اجرا در زمان چندجمله‌ای معامله می‌کند، در حالی که همچنان یک کران ریاضی روی اینکه پاسخش چقدر می‌تواند از بهینه دور باشد فراهم می‌کند.

تعریف نسبت تقریبی

یک الگوریتم یک Approximation Ratio (نسبت تقریبی) ρ(n) دارد اگر، برای هر ورودی به اندازه n، نسبت بین هزینه راه‌حل الگوریتم و هزینه بهینه واقعی هرگز از ρ(n) فراتر نرود (برای مسائل کمینه‌سازی)، یا هرگز از 1/ρ(n) کمتر نشود (برای مسائل بیشینه‌سازی).

برای یک مسئله کمینه‌سازی:
C / C* ≤ ρ(n)

جایی که C هزینه راه‌حل تقریبی پیداشده است،
و C* هزینه راه‌حل بهینه واقعی است

یک تقریب ρ(n) = 2 تضمین می‌کند راه‌حل الگوریتم
هرگز بیش از دو برابر بهینه واقعی هزینه نداشته باشد،
صرف‌نظر از اینکه چه ورودی داده شود

این تضمین برای هر ورودی ممکن برقرار است، نه صرفاً به‌طور میانگین — یک تمایز حیاتی که به الگوریتم‌های تقریبی دندان‌های ریاضی واقعی می‌دهد، به‌جای صرفاً یک ابتکار که "معمولاً" خوب کار می‌کند.

مسئله پوشش رأس: یک تقریب-۲

یک Vertex Cover (پوشش رأس) یک گراف، زیرمجموعه‌ای از رأس‌ها است طوری‌که هر یال حداقل یک نقطه‌انتهایی در زیرمجموعه دارد. مسئله Minimum Vertex Cover Problem (مسئله پوشش رأس کمینه) کوچک‌ترین چنین زیرمجموعه‌ای را می‌خواهد، و NP-complete است، که پیش‌تر در این مجموعه درباره NP-completeness بحث شد.

APPROX-VERTEX-COVER(G):
  C = مجموعه خالی
  E' = یک کپی از G.E
  تا زمانی که E' خالی نباشد:
      فرض کن (u, v) یک یال دلخواه از E' باشد
      C = C ∪ {u, v}       // هر دو نقطه‌انتهایی را اضافه کن
      هر یال متصل به u یا v را از E' حذف کن
  C را برگردان

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

اثبات تضمین تقریب-۲

اثبات به یک مشاهده ماهرانه درباره یال‌های انتخاب‌شده در طول اجرای الگوریتم متکی است، به نام یک Matching (تطبیق) — مجموعه‌ای از یال‌ها که هیچ دوتایشان یک نقطه‌انتهایی مشترک ندارند.

مشاهده کلیدی: یال‌های (u,v) انتخاب‌شده در سراسر همه
تکرارهای حلقه while یک تطبیق تشکیل می‌دهند، چون
وقتی u و v به C اضافه می‌شوند، هر یالی که هرکدام از
آن‌ها را لمس می‌کند حذف می‌شود، پس هیچ یال انتخاب‌شده
آینده‌ای نمی‌تواند یک نقطه‌انتهایی با یکی قبلی مشترک داشته باشد

از آنجا که هیچ دو یال انتخاب‌شده یک نقطه‌انتهایی مشترک ندارند،
هر پوشش رأس — شامل بهینه — باید حداقل یک نقطه‌انتهایی
از هر یال انتخاب‌شده را شامل شود
(یک رأس منفرد نمی‌تواند دو یال غیرمجاور را پوشش دهد)

بنابراین: |C*| ≥ (تعداد یال‌های انتخاب‌شده)

اما پوشش C الگوریتم دقیقاً
2 · (تعداد یال‌های انتخاب‌شده) رأس دارد،
چون هر بار هر دو نقطه‌انتهایی را اضافه می‌کند

بنابراین: |C| = 2 · (تعداد یال‌های انتخاب‌شده) ≤ 2 · |C*|

این اثبات می‌کند خروجی الگوریتم هرگز بیش از دو برابر اندازه پوشش رأس کمینه واقعی نیست، یک تقریب-۲ تضمین‌شده، که با یک الگوریتم به‌طور قابل‌توجه ساده و سریع که در زمان O(V + E) اجرا می‌شود به دست می‌آید.

مسئله فروشنده دوره‌گرد با نامساوی مثلث

Traveling Salesman Problem (TSP) کوتاه‌ترین مسیر ممکن که دقیقاً یک‌بار از هر شهر بازدید می‌کند و به ابتدا برمی‌گردد را می‌خواهد. این مسئله NP-complete است، و در عمومی‌ترین شکلش، نمی‌تواند به هیچ فاکتور ثابتی تقریب زده شود مگر اینکه P = NP. با این حال، وقتی وزن‌های یال Triangle Inequality (نامساوی مثلث) را برآورده کنند (فاصله مستقیم بین دو نقطه هرگز طولانی‌تر از یک مسیر از میان یک نقطه سوم نیست — فرضی طبیعی برای فاصله‌های جغرافیایی واقعی)، یک تقریب-۲ ظریف وجود دارد.

APPROX-TSP-TOUR(G, c):
  یک درخت پوشای کمینه T از G محاسبه کن،
  با استفاده از یک الگوریتم که پیش‌تر در این مجموعه بحث شد
  (مانند الگوریتم پریم یا کروسکال)

  یک پیمایش جستجوی عمق‌اول T انجام بده،
  که پیش‌تر در این مجموعه بحث شد، و رأس‌ها را
  به ترتیبی که ابتدا بازدید می‌شوند فهرست کن

  توری که رأس‌ها را به این ترتیب بازدید می‌کند برگردان،
  سپس به رأس شروع برمی‌گردد

چرا این به یک تقریب-۲ دست می‌یابد

اثبات سه کمیت را با استفاده از یک استدلال ماهرانه متصل می‌کند. اول، هر تور TSP، اگر یک یال حذف شود، به یک مسیر همیلتونی تبدیل می‌شود، که خودش یک درخت پوشاست، پس هزینه تور بهینه حداقل وزن درخت پوشای کمینه است: MST ≤ OPT. دوم، یک پیمایش کامل جستجوی عمق‌اول MST، که هر یال را دقیقاً دو بار طی می‌کند (یک‌بار پایین‌رفتن، یک‌بار بازگشت)، هزینه کل دقیقاً 2 · MST دارد. سوم، با استفاده از نامساوی مثلث، "کوتاه‌کردن" این پیمایش دوبرابرشده — پریدن از رأس‌های از‌قبل‌بازدیدشده برای رفتن مستقیم به بعدی بازدیدنشده — فقط می‌تواند کل فاصله را کاهش دهد، هرگز افزایش دهد.

ترکیب این حقایق:
هزینه تور تقریبی ≤ 2 · MST ≤ 2 · OPT

این زنجیره نامساوی‌ها اثبات می‌کند تور الگوریتم هرگز بیش از دو برابر تور بهینه واقعی هزینه ندارد، تقریب-۲ تمیز دیگری، که در زمان غالب‌شده توسط محاسبه درخت پوشای کمینه، که پیش‌تر در این مجموعه بحث شد، معمولاً O(E log V)، اجرا می‌شود.

نسبت‌های تقریبی همه به‌یک‌اندازه خوب نیستند

مسائل NP-hard مختلف تقریب‌های کیفیت به‌طور چشمگیری متفاوتی می‌پذیرند. برخی مسائل یک Polynomial-Time Approximation Scheme (PTAS) دارند، که یک نسبت تقریبی به‌طور دلخواه نزدیک به ۱ را اجازه می‌دهد (هرچند زمان اجرا با نزدیک‌شدن نسبت به ۱ رشد می‌کند). دیگران، مانند TSP عمومی بدون نامساوی مثلث، اثبات شده‌اند هیچ تقریب فاکتور-ثابتی را اصلاً نمی‌پذیرند مگر اینکه P = NP. باز هم دیگران بین این دو قرار دارند، و برخی نسبت تقریبی ثابت را می‌پذیرند اما نه بهتر، صرف‌نظر از اینکه الگوریتم چقدر ماهرانه طراحی شده باشد. درک اینکه یک مسئله NP-hard مشخص به کدام دسته تعلق دارد خودش یک حوزه پژوهشی نظری فعال است.

چرا الگوریتم‌های تقریبی برای اپلیکیشن‌های دنیای واقعی اهمیت دارند

نوع‌های پوشش رأس و TSP در سراسر لجستیک، طراحی شبکه، و مسائل تخصیص منابع ظاهر می‌شوند جایی که یک راه‌حل بهینه دقیق، هرچند از نظر تئوری مطلوب، از نظر محاسباتی برای ورودی‌های با اندازه واقع‌بینانه غیرقابل‌اجرا است. الگوریتم‌های تقریبی یک میانه از نظر ریاضی دقیق فراهم می‌کنند: یک راه‌حل که تضمین می‌شود سریع اجرا شود و تضمین می‌شود درون یک فاکتور شناخته‌شده و اثبات‌پذیر از بهینه باشد، تضمینی بسیار قوی‌تر از یک ابتکار اثبات‌نشده، حتی اگر اتفاقاً در عمل خوب عمل کند.