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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

[עריכה] דוגמה לאלגוריתם קירוב

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

בעיה זו היא NP-קשה, אולם ניתן לקרב אותה באופן הבא:

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

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

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

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

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