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

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

היסטוריה

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

הצורה הכללית של בעיית הסוכן הנוסע נחקרה לראשונה על ידי מתמטיקאים בשנת 1930, בפרט על ידי קרל מנגר שהגדיר את הבעיה והתייחס לפתרונות כוח גס ושיטת השכן הקרוב:
מבעיית השליחים (כיוון שבפועל הבעיה צריכה להיפתר על ידי כל דוור, וגם על ידי הרבה טיילים) אנו שמים לב למשימה למצוא למספר סופי של נקודות, שהמרחק בין כל צמד ידוע, את המסלול הקצר ביותר שיחבר את כל הנקודות. הבעיה פתירה מכך שיש מספר סופי של מסלולים. חוקים שיורידו את מספר המסלולים מתחת למספר התמורות אינם ידועים. השיטה בה יש ללכת מנקודת ההתחלה לנקודה הקרובה ביותר, ואז לקרובה ביותר אליה וכדומה, בכלליות לא מפיקה את המסלול הקצר ביותר.
בשנות ה-50 וה-60 של המאה ה-20 הבעיה הפכה פופולרית באירופה וארצות הברית לאחר שתאגיד ראנד מסנטה מוניקה הציע פרסים על מציאת שלבים בפתרון הבעיה. בעשורים שלאחר מכן נחקרה הבעיה על ידי מתמטיקאים, חוקרי מדעי המחשב, כימאים, פיזיקאים ומדענים אחרים. לעומת זאת, בשנות ה-60 התפתחה גישה חדשה - במקום לחפש את הפתרון האופטימלי, החלו אנשים לחפש את הפתרון הגרוע ביותר ובכך מצאו חסם עליון לבעיה.
ריצ'רד קארפ הראה בשנת 1972 שמסלול המילטון היא בעיה השייכת לקטגוריה NP-שלמה, ובכך סיפק הסבר מתמטי לקושי החישובי במציאת מסלול אופטימלי.
בשנת 1991 פרסם ג'רארד ריינלט ספרייה בשם TSPLIB שכללה אוסף של רשימות ערים לדוגמה בדרגות קושי שונות. חוקרים רבים עשו שימוש נרחב בספרייה, ובשנת 2006 ויליאם ג'ון קוק וחוקרים נוספים חישבו מסלול אופטימלי שעבר ב-85,900 נקודות, נכון להיום החישוב הגדול ביותר מתוך TSPLIB. ספריה זו מתוחזקת לצורך בדיקת אלגוריתמים לפתרון הבעיה, ומכילה נתונים רבים, חלקם ערים ומעגלים מודפסים אמתיים.

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

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

סימטריות

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

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

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

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

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