אלגוריתם קירוב
אלגוריתם קירוב (approximation algorithm באנגלית) הוא אלגוריתם שמוצא פתרון שאינו בהכרח פתרון אופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון אופטימלי.
על פי רוב מודדים קירוב של אלגוריתם בהתאם ליחס בין הפתרון שנמצא על ידי האלגוריתם לבין הפתרון האופטימלי.
נאמר כי אלגוריתם קירוב לבעיה משיג יחס קירוב של אם הפתרון המושג על ידי האלגוריתם קטן מ- פעמים הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מינימיזציה) או גדול מהחלק ה- של הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מקסימיזציה).
דוגמה לאלגוריתם קירוב
בעיית הסוכן הנוסע בגרף מטרי מוגדרת כבעיית מציאת מסלול המילטוני בגרף ממושקל: דהיינו מסלול שעובר בכל צומת בדיוק פעם אחת וחוזר לצומת הראשון, ומשקלו מינימלי.
בעיה זו היא NP-קשה, אולם ניתן לקרב אותה באופן הבא (האלגוריתם של קריסטופידס[1]):
אלגוריתם: מוצאים עץ פורש מינימלי בגרף. בוחרים צומת כלשהו כשורש, ומטיילים לעומקו של העץ, במסלול ששקול לחיפוש לעומק. כאשר אנו מגלים שאנו חוזרים לצומת בו כבר היינו, נבצע "קיצור דרך", דהיינו, נמשיך ישירות לצומת הבא ברשימה - וזאת עד שביקרנו בכל הצמתים ונחזור לצומת שממנו התחלנו.
טיעון קירוב: על מנת להיווכח שהאלגוריתם המתואר לעיל הוא אלגוריתם קירוב, יש לבחון את הפתרון שנמצא ביחס לפתרון האופטימלי.
ראשית, קל להיווכח כי משקלו של העץ הפורש המינימלי קטן ממשקלו של המסלול ההמילטוני המינימלי, משום שהמסלול ההמילטוני מכיל עץ פורש, ולכן משקלו גדול יותר. כמו כן ניתן להשתכנע כי המסלול שביצע האלגוריתם ללא קיצורי דרך עבר על כל קשת בדיוק פעמיים - פעם בדרך "הלוך" ופעם בדרך "חזור". לכן, משקל המסלול שמצאנו ללא קיצורי דרך יהיה בדיוק פעמיים משקל העץ הפורש המינימלי ממנו התחלנו את האלגוריתם. בנוסף, משום שהגרף הוא גרף מטרי, קיצור הדרך שביצענו רק הקטינו את משקלו של המסלול שמצאנו.
לכן משקלו של המסלול המקוצר (אותו מצא האלגוריתם) הוא לכל היותר פעמיים משקל העץ הפורש המינימלי, שהוא לכל היותר פעמיים משקל המסלול ההמילטוני, שהוא הפתרון האופטימלי לבעיה.
לפיכך, האלגוריתם שתואר הוא אלגוריתם קירוב עם יחס קירוב של 2.
ראו גם
הערות שוליים
- ^ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
