בעיית המסלול הארוך ביותר

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

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

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

מבוא בלתי פורמלי[עריכת קוד מקור | עריכה]

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

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

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

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

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

רדוקציה של הבעיה[עריכת קוד מקור | עריכה]

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

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

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

2. לשם הרדוקציה נבחר בבעיה מוכרת מ-NPC (אוסף הבעיות השלמות במחלקת NP): במקרה זה תתאים שאלת מציאת המסלול ההמילטוני.

3. נבצע את הרדוקציה לבעיה המוכרת:

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

ב. נוכיח כי תשובה חיובית לבעיה החדשה שקולה (כלומר: נכונה אם ורק אם) לתשובה חיובית גם לבעיה המוכרת:

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

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