אלגוריתם קירוב

אלגוריתם קירוב (באנגלית: approximation algorithm) הוא אלגוריתם שמוצא פתרון שאינו בהכרח פתרון אופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון אופטימלי. אלגוריתמים אלו שימושיים במיוחד בבעיות שהאלגוריתמים הידועים לפתרונן הם בסיבוכיות גבוהה, ובפרט בבעיות NP קשות^[1], קבוצת הבעיות NP קשות שקיים להם אלגוריתם קירוב נקראת APX, ניתן להוכיח שיש בעיות שאין להם אלגוריתם קירוב אלא אם כן P=NP.

על פי רוב מודדים קירוב של אלגוריתם בהתאם ליחס בין הפתרון שנמצא על ידי האלגוריתם לבין הפתרון האופטימלי. נאמר כי אלגוריתם קירוב לבעיה משיג יחס קירוב של $c$ (לפעמים נאמר גם אלגוריתם $c$ -מקרב) אם הפתרון המושג על ידי האלגוריתם קטן מ- $c$ פעמים הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מינימיזציה) או גדול מהחלק ה- $c$ של הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מקסימיזציה).

סוגי אלגוריתמי קירוב

ישנם כמה סוגים של אלגוריתמי קירוב, שנבדלים ביניהם בסוג הקירוב שהם מציעים ובסיבוכיות שלהם:

קירוב באמצעות קבוע

אלגוריתמי קירוב אלו מציעים קירוב בפער של מכפלה במספר קבוע מהערך האופטימלי, למשל השמה של לפחות חצי מהערך המקסימלי בבעיית התרמיל, בזמן פולינומי לגודל הקלט. אלגוריתמים חמדניים שנותנים קירוב הם מסוג זה.

סכמת קירוב פולינומית (PTAS)

אלגוריתמי קירוב מסוג סכמת קירוב פולינומית^[2] מקבלים $\varepsilon$ כלשהו כקלט ומתייחסים אליו כקבוע, ומציעים קירוב של מכפלה של $1-\varepsilon$ מהערך האופטימלי (או $1+\varepsilon$ בבעיות מינימום). כל זה בזמן פולינומי לגודל הקלט, זה עלול להיות אקספוננציאלי ביחס ל- $1/\varepsilon$ (הוא יכול להיות החזקה).

תת קבוצה של אלגוריתמים אלו היא סכמת קירוב פולינומית מלאה (FPTAS). באלגוריתמים אלו הסיבוכיות פולינומית גם בגודל הקלט וגם ב- $1/\varepsilon$ . קירוב כזה קיים לבעיית תרמיל הגב למשל.

דוגמה לאלגוריתם קירוב

בעיית הסוכן הנוסע בגרף מטרי מוגדרת כבעיית מציאת מסלול המילטוני בגרף ממושקל: דהיינו מסלול שעובר בכל צומת בדיוק פעם אחת וחוזר לצומת הראשון, ומשקלו מינימלי.

בעיה זו היא NP-קשה, אולם ניתן לקרב אותה באופן הבא (האלגוריתם של קריסטופידס^[3]):

אלגוריתם: מוצאים עץ פורש מינימלי בגרף. בוחרים צומת כלשהו כשורש, ומטיילים לעומקו של העץ, במסלול ששקול לחיפוש לעומק. כאשר אנו מגלים שאנו חוזרים לצומת בו כבר היינו, נבצע "קיצור דרך", דהיינו, נמשיך ישירות לצומת הבא ברשימה - וזאת עד שביקרנו בכל הצמתים ונחזור לצומת שממנו התחלנו.

טיעון קירוב: על מנת להיווכח שהאלגוריתם המתואר לעיל הוא אלגוריתם קירוב, יש לבחון את הפתרון שנמצא ביחס לפתרון האופטימלי.

ראשית, קל להיווכח כי משקלו של העץ הפורש המינימלי קטן ממשקלו של המסלול ההמילטוני המינימלי, משום שהמסלול ההמילטוני מכיל עץ פורש, ולכן משקלו גדול יותר. כמו כן ניתן להשתכנע כי המסלול שביצע האלגוריתם ללא קיצורי דרך עבר על כל קשת בדיוק פעמיים - פעם בדרך "הלוך" ופעם בדרך "חזור". לכן, משקל המסלול שמצאנו ללא קיצורי דרך יהיה בדיוק פעמיים משקל העץ הפורש המינימלי ממנו התחלנו את האלגוריתם. בנוסף, משום שהגרף הוא גרף מטרי, קיצור הדרך שביצענו רק הקטינו את משקלו של המסלול שמצאנו.

לכן משקלו של המסלול המקוצר (אותו מצא האלגוריתם) הוא לכל היותר פעמיים משקל העץ הפורש המינימלי, שהוא לכל היותר פעמיים משקל המסלול ההמילטוני, שהוא הפתרון האופטימלי לבעיה.

לפיכך, האלגוריתם שתואר הוא אלגוריתם קירוב עם יחס קירוב של 2.

ראו גם

הערות שוליים

^ Bernard., Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press. ISBN 9780521195270. OCLC 671709856.
^ Petra Schuurman, Gerhard J. Woeginger. Approximation Schemes – A Tutorial
^ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[Bernard._2011-1] Bernard., Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press. ISBN 9780521195270. OCLC 671709856.

[2] Petra Schuurman, Gerhard J. Woeginger. Approximation Schemes – A Tutorial

[3] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[1]

[2]

[3]