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

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

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

יש כמה סוגים, בהתאם לדיוק שלהם ולזמן הריצה.

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

סכמת קירוב פולינומית מקבלת פרט ε כקלט ומספקת פתרון שמקבל כמעט את האופטימום, עד טעות של ε. זמן הריצה פולינומי בגודל הקלט, אך יכול להיות תלוי בצורה חזקה ב‑1/ε. תת־סוג חשוב הוא FPTAS: כאן זמן הריצה פולינומי גם ב‑1/ε וגם בגודל הקלט. לבעיית התרמיל (knapsack) קיים FPTAS.

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

אלגוריתם קירוב פשוט: בונים עץ פורש מינימלי (MST). בוחרים שורש, מטיילים בעץ בסדר של חיפוש לעומק (DFS) ונבצע "קיצורי דרך" כדי לא לעבור על צומת פעמיים. בלי קיצורי דרך המסלול עובר כל קשת פעמיים, לכן שוקל בדיוק פעמיים משקל ה‑MST. מאחר שהגרף מטרי (קיים יחס משולש, כלומר מעקפים לא מגדילים מרחקים), הקיצורים רק מקטינים משקל. גם משקל ה‑MST אינו גדול ממשקל המסלול ההמילטוני האופטימלי, כי כל מסלול מכיל עץ פורש. לכן המסלול המתקבל שוקל לכל היותר פעמיים הפתרון האופטימלי.

מסקנה: האלגוריתם הזה נותן יחס קירוב של 2 לבעיית ה‑TSP המטרית.

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

במדע המחשב יש בעיות שקשה מאוד לפתור בדיוק. קוראים להן NP-קשות (בעיות קשות). יש בעיות שאפשר רק לקרב, לא לפתור בדיוק.

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

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

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

מסקנה: בשיטה הזו מקבלים יחס קירוב של 2. זה אומר שהמסלול יכול להיות עד פי שניים כבד מהמסלול הטוב ביותר.