בעיית הסוכן הנוסע

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

בעיית הסוכן הנוסע (באנגלית: Travelling Salesman Problem ובראשי תיבות: TSP) היא בעיה ידועה בתורת הגרפים ובתורת הסיבוכיות, המעלה את השאלה הבאה: "בהינתן רשימת ערים והמרחק בין כל שתי ערים, מהו המסלול הקצר ביותר, אשר יעבור בכל עיר פעם אחת, ויחזור לעיר ממנה התחיל?"

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

היסטוריה

ויליאם רואן המילטון

מקורות הבעיה לא ברורים. מדריך לסוכן הנוסע משנת 1832 מזכיר את הבעיה ומכיל דוגמאות למסלולים בגרמניה ושווייץ, אבל לא מכיל התייחסות מתמטית לנושא^[1].

בעיית הסוכן הנוסע נוסחה לראשונה במאה ה-19 על ידי המתמטיקאי האירי ויליאם רואן המילטון והמתמטיקאי הבריטי תומאס קירקמן (Thomas Kirkman). המילטון פיתח בשנת 1857 את "משחק איקוסיאן" (Icosian game) שמטרתו הייתה למצוא מסלול המילטוני שיעבור בכל הקודקודים של דודקהדרון בדיוק פעם אחת ויחזור לנקודת ההתחלה.

הצורה הכללית של בעיית הסוכן הנוסע נחקרה לראשונה על ידי מתמטיקאים בשנת 1930, בפרט על ידי קרל מנגר שהגדיר את הבעיה והתייחס לפתרונות כוח גס ושיטת השכן הקרוב^[2]:

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

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

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

בשנת 1991 פרסם ג'רארד ריינלט ספרייה בשם TSPLIB שכללה אוסף של רשימות ערים לדוגמה בדרגות קושי שונות. חוקרים רבים עשו שימוש נרחב בספרייה, ובשנת 2006 ויליאם ג'ון קוק וחוקרים נוספים חישבו מסלול אופטימלי שעבר ב-85,900 נקודות, נכון להיום החישוב הגדול ביותר מתוך TSPLIB. ספריה זו מתוחזקת לצורך בדיקת אלגוריתמים לפתרון הבעיה.

מאפיינים

בעיית הסוכן הנוסע סימטרית עם 4 ערים

הצגה כבעיית גרפים

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

סימטריות

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

סיבוכיות חישוב

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

מאפיינים נוספים

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

פתרון הבעיה

הקווים המנחים לטיפול בבעיות NP-קשות הם:

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

אלגוריתמים מדויקים

פתרון בעיה סימטרית עם 7 ערים. משמאל – האפשרות הנבדקת. מימין – האפשרות הטובה ביותר עד כה. מספר האפשרויות – 360=2/!(7-1)

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

בשנת 2001 נמצא פתרון מדויק של הבעיה עם 15,112 ערים בגרמניה מתוך TSPLIB. החישובים התבצעו ברשת של 110 מעבדים באוניברסיטאות רייס ופרינסטון שבארצות הברית. במאי 2004 נמצא מסלול באורך 72,500 קילומטרים שעבר בכל 24,978 הערים בשוודיה והוכח כמסלול הקצר ביותר שקיים^[3]. במרץ 2005 נמצא מסלול שעבר דרך 33,810 נקודות על מעגל מודפס שאורכו היה 66,048,945 (יחידות TSPLIB). חישוב המסלול ארך זמן המקביל ל-15.7 שנות חישוב של מעבד ממוצע באותה התקופה. באפריל 2006 נמצא מסלול שעבר דרך 85,900 נקודות, בכוח עיבוד שהקביל ל-136 שנות חישוב.

קירובים לפתרון

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

אף על פי שהבעיה קשה לחישוב, כיום ידועות מספר היוריסטיקות לפתרונות מקורבים שלה. שיטות מודרניות יכולות למצוא פתרונות לבעיות גדולות מאוד (מיליוני ערים), בזמן סביר, שמובטחים להיות בסטייה של עד 2%–3% מהמסלול האופטימלי^[4].

אלגוריתם חמדן

דוגמה לאלגוריתם חמדן המחפש קירוב למסלול הקצר ביותר היא "שיטת השכן הקרוב". בשיטה זו בכל צעד הסוכן יפנה לעיר הקרובה אליו ביותר שעוד לא ביקר בה. בעזרת אלגוריתם זה ניתן לקבל במהירות מסלול קצר ויעיל. עבור מספר מסוים של ערים בפיזור אקראי לרוב יתקבל מסלול ארוך ב-25% מהמסלול הקצר ביותר^[5]. עם זאת, קיימים סידורי ערים מיוחדים שגורמים לאלגוריתם זה להניב את התוצאה הגרועה ביותר, הן בגרסה הסימטרית והן בגרסה הא-סימטרית.

יישומים נוספים

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

ביצועים אנושיים

בעיית הסוכן הנוסע עניינה חוקרים מתחום הפסיכולוגיה הקוגניטיבית שבדקו את הביצועים האנושיים בהתמודדות עם הבעיה. מחקרים מראים שאנשים מסוגלים ליצור פתרונות איכותיים במהירות^[6], מסקנה שרומזת שייתכן וביצועי מחשבים בתחום יכולים להשתפר על ידי הבנה וחיקוי של דרכי חשיבה של בני אדם. מחקרים אלו גם הובילו לגילויים חדשים על המנגנון שמאחורי המחשבה האנושית^[7]. הגיליון הראשון של כתב העת "Journal of Problem Solving" הוקדש לנושא של ביצועים אנושיים בניסיון פתרון הבעיה.

בתרבות

סרט הקולנוע "הסוכן הנוסע" (Travelling Salesman) מאת הבמאי טימותי לנזון הוא סיפור על ארבעה מתמטיקאים שנשכרו על ידי ממשלת ארצות הברית כדי לפתור את הבעיה הפתוחה במדעי המחשב: שאלת P=NP^[8].

ראו גם

קישורים חיצוניים

מדיה וקבצים בנושא בעיית הסוכן הנוסע בוויקישיתוף

בעיית הסוכן הנוסע, אוניברסיטת ווטרלו
ספריית TSPLIB, אוניברסיטת היידלברג
בעיית הסוכן הנוסע, באתר MathWorld (באנגלית)
בעיית הסוכן הנוסע, באתר אנציקלופדיה בריטניקה (באנגלית)

הערות שוליים

^ "הסוכן הנוסע — איך הוא צריך להיות ומה הוא צריך לעשות כדי לקבל עמלה ולהיות בטוח בהצלחת עסקיו" מאת סוכן מכירות לא ידוע (מגרמנית - "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur")
^ מגרמנית: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."
^ הטיול האופטימלי בשוודיה (אנגלית), ‏2004
^ Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin, "Traveling salesman problem heuristics: leading methods, implementations and latest advances", European Journal of Operational Research 211 (3): 427–441, 2011
^ Johnson, D.S. and McGeoch, L.A., The traveling salesman problem: A case study in local optimization, Local search in combinatorial optimization, 1997
^ Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem", Perception & Psychophysics 58 (4): 527–539, doi:10.3758/BF03213088
^ James N. MacGregor, Yun Chu, סקירת ביצועים אנושיים בבעיית הסוכן הנוסע ובעיות קשורות (מאנגלית - Human Performance on the Traveling Salesman and Related Problems: A Review), The Journal of Problem Solving כרך 3, חורף 2011
^ DUNCAN GEERE, 'Travelling Salesman' movie considers the repercussions if P equals NP (Wired UK), Wired, ‏26/04/2012

[1] "הסוכן הנוסע — איך הוא צריך להיות ומה הוא צריך לעשות כדי לקבל עמלה ולהיות בטוח בהצלחת עסקיו" מאת סוכן מכירות לא ידוע (מגרמנית - "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur")

[2] מגרמנית: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."

[3] הטיול האופטימלי בשוודיה (אנגלית), ‏2004

[4] Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin, "Traveling salesman problem heuristics: leading methods, implementations and latest advances", European Journal of Operational Research 211 (3): 427–441, 2011

[5] Johnson, D.S. and McGeoch, L.A., The traveling salesman problem: A case study in local optimization, Local search in combinatorial optimization, 1997

[6] Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem", Perception & Psychophysics 58 (4): 527–539, doi:10.3758/BF03213088

[7] James N. MacGregor, Yun Chu, סקירת ביצועים אנושיים בבעיית הסוכן הנוסע ובעיות קשורות (מאנגלית - Human Performance on the Traveling Salesman and Related Problems: A Review), The Journal of Problem Solving כרך 3, חורף 2011

[8] DUNCAN GEERE, 'Travelling Salesman' movie considers the repercussions if P equals NP (Wired UK), Wired, ‏26/04/2012

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]