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

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

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

 היסטוריה 
ממוזער|שמאל|ויליאם רואן המילטון

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

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

הצורה הכללית של בעיית הסוכן הנוסע נחקרה לראשונה על ידי מתמטיקאים בשנת 1930, בפרט על ידי קרל מנגר שהגדיר את הבעיה והתייחס לפתרונות כוח גס ושיטת השכן הקרוב:בשנות ה-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)
פתרון פשוט לבעיה הוא בדיקת כל התמורות האפשריות וחיפוש המסלול הקצר ביותר (תוך שימוש בכוח גס). פתרון זה מצריך בדיקה של  אפשרויות (עצרת של מספר הערים), ולכן סיבוכיות זמן הריצה במקרה כזה תהיה . חישוב כזה הופך מהר מאוד לבלתי מעשי (לבלתי יעיל, במינוח של מדעי המחשב). דוגמה להמחשת הבעיה: אם ישנן 70 ערים בהן על הסוכן לבקר, יצטרך הסוכן לבחון  מסלולי נסיעה אפשריים, אשר מהווים מספר רב יותר ממספר האטומים ביקום כולו.

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

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

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

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

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

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

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

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

 בעיית הסוכן הנוסע, אוניברסיטת ווטרלו
 ספריית TSPLIB, אוניברסיטת היידלברג



 הערות שוליים 

קטגוריה:אופטימיזציה בדידה
קטגוריה:תורת הגרפים
קטגוריה:בעיות NP-שלמות
קטגוריה:בעיות NP-קשות