מפת הסיבוכיות
EN
תרגיל

ניתוח אלגוריתם העץ הכפול ל־TSP מטרי

שילוב חסם MST, סיור אוילרי וקיצורים מטריים לקבלת יחס 2.

מקורות מטלות

הכנה איכותית למבחן ופתרונות קהילתיים — נוי 2025פתרון קהילתיפתרון מטלה 5 - סיבוכיות.pdfAssignment 5הכנה איכותית ופתרון קהילתי — אינו מקור רשמי

שאלה

בגרף מלא בעל עלויות סימטריות אי־שליליות המקיימות אי־שוויון משולש, נתחו: חשבו MST, הכפילו קשתות, מצאו סיור אוילרי וקצרו הופעות חוזרות. הוכיחו מסע המילטוני בעלות לכל היותר 2 OPT2\,\mathrm{OPT} וזמן פולינומי.

דרישות קדם

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

רמז 1

מחיקת קשת ממסע אופטימלי נותנת עץ פורש.

רמז 2

הכפלה הופכת את כל הדרגות לזוגיות.

רמז 3

אי־שוויון המשולש מצדיק קיצור.

בנייה מודרכת

קירוב 2 ל־TSP מטרי בשיטת העץ הכפול

שלב 1 מתוך 6
קירוב 2 ל־TSP מטרי בשיטת העץ הכפול על חמש נקודותמופע מטרי מלא על חמש נקודות הופך לעץ פורש מינימלי, אחר כך לרב־גרף כפול, אחר כך למעגל אוילר, ולבסוף למסע המילטוני מקוצר.מופע מטרי מלא8151319871210117ABCDE
קשת מטרית עם עלותה
אי־שוויון המשולשעלויות: AB 8, AC 15, AD 13, AE 19, BC 8, BD 7, BE 12, CD 10, CE 11, DE 7מתקיים בכל שישים השלשות הסדורות של נקודות שונות

פתרון מלא

יהי TT עץ פורש מינימלי. מחיקת קשת ממסע המילטוני אופטימלי משאירה עץ פורש, ולכן

w(T)≤w(OPT).w(T)\le w(\mathrm{OPT}).

לאחר הכפלת קשתות TT כל הדרגות זוגיות והגרף קשיר, ולכן קיים סיור אוילרי שעלותו בדיוק 2w(T)2w(T).

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

w(פלט)≤2w(T)≤2w(OPT).w(\text{פלט})\le2w(T)\le2w(\mathrm{OPT}).

MST מחושב בזמן פולינומי, הכפלת הקשתות יוצרת 2(n−1)2(n-1) עותקים, סיור אוילרי נמצא בזמן לינארי בגודל הרב־גרף, וקיצור נעשה עם מערך ביקור. אריתמטיקה על משקלים בינאריים עדיין פולינומית.

כל הנחה דרושה: בלי משולש קיצור עלול להתייקר; בלי שלמות קשת הקיצור אולי חסרה; וסימטריה מתאימה לגרסה הלא־מכוונת. העץ עצמו אינו מסע, והסיור האוילרי אינו מסע TSP עד שמסירים חזרות.

נקודות בדיקה

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

טעויות נפוצות

  • כינוי MST מסע המילטוני.
  • קיצור בלי משולש ושלמות.
  • היפוך חסם w(T)≤OPTw(T)\le\mathrm{OPT}.

מקורות ואימות

  • Papadimitriou, ch. 13 (metric TSP approximation)
  • הערת כיסוי הקורפוס: אין כיסוי ישיר בסיכום הממוזג; עמודים 79-80 מכילים רק תבנית קשורה של עץ שטיינר.
  • מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

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

פתיחה בגלריית ההמחשות: קירוב 2 ל־TSP מטרי בשיטת העץ הכפול