בעיית הסוכן הנוסע – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה

→ העריכה הקודמת העריכה הבאה ←

תוכן שנמחק תוכן שנוסף

חזותיקוד ויקי

בשורה

גרסה מ־17:24, 7 בדצמבר 2015

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

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

מאפיינים

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

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

סימטריות

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

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

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

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

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

פתרון הבעיה

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

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

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

פתרון בעיה סימטרית עם 7 ערים. משמאל - האפשרות הנבדקת. מימין - האפשרות הטובה ביותר עד כה. מספר האפשרויות - 360

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

ראו גם

לקריאה נוספת

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

הערות שוליים

^ "הסוכן הנוסע — איך הוא צריך להיות ומה הוא צריך לעשות כדי לקבל עמלה ולהיות בטוח בהצלחת עסקיו" מאת סוכן מכירות לא ידוע (מגרמנית - "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]

@@ שורה 2: / שורה 2: @@
 {{פירוש נוסף|נוכחי=בעיה ב[[תורת הגרפים]]|אחר=דילמה במדעי החברה ובניהול|ראו=[[דילמת הסוכן]]}}
 [[תמונה:TSP short cycles.png|ממוזער|שמאל|250px||בעיית הסוכן הנוסע - מסלולים קצרים]]
-'''בעיית הסוכן הנוסע''' (ידועה גם בקיצור כ-TSP - Travelling Salesman Problem) היא בעיה ידועה ב[[תורת הגרפים]] וב[[תורת הסיבוכיות]]. הבעיה עוסקת בסוכן נוסע, שבמסגרת תפקידו עליו לעבור בערים רבות, המקושרות ביניהן ברשת כבישים, יש למצוא את המסלול הקצר ביותר אשר מבקר בכל עיר פעם אחת בדיוק. ניסוח הבעיה במונחי תורת הגרפים: למצוא ב[[גרף ממושקל]] [[מסלול המילטוני]] שמשקלו הוא הקטן ביותר.
+'''בעיית הסוכן הנוסע''' (באנגלית: Travelling Salesman Problem ובראשי תיבות: TSP) היא בעיה ידועה ב[[תורת הגרפים]] וב[[תורת הסיבוכיות]], המעלה את השאלה הבאה: ''"בהינתן רשימת ערים והמרחק בין כל שתי ערים, מהו המסלול הקצר ביותר, אשר יעבור בכל עיר פעם אחת, ויחזור לעיר ממנה התחיל?".''
+הבעיה נכללת ב[[NP (מחלקת סיבוכיות)|מחלקת הסיבוכיות NP]], והיא אחת מהבעיות המרכזיות בתחום [[אופטימיזציה (מתמטיקה)|האופטימיזציה.]]
-בנוסף לחשיבותה התאורטית, לבעיה גם חשיבות מעשית, לא רק בבעיות של תחבורה ולוגיסטיקה, אלא גם, למשל, בייצורו של [[מעגל מודפס]], שבו על מכונת הייצור לעבור מסלול מסוים בעת שהיא יוצרת חורים בלוח שעליו נמצא המעגל.
+== היסטוריה ==
-פתרון פשוט לבעיה הוא בדיקת כל המסלולים האפשריים. אלא, שכאשר יש <math>n</math> ערים, פתרון זה מצריך בדיקה של <math>n!</math> אפשרויות, ([[עצרת]] של מספר הערים), ולכן דרך זו הופכת מהר מאוד לבלתי מעשית (לבלתי [[חישוב יעיל|יעילה]], במינוח של [[מדעי המחשב]]). דוגמה להמחשת הבעיה: אם ישנן 70 ערים בהן על הסוכן לבקר, יצטרך הסוכן לבחון [[עצרת|!]]70 מסלולי נסיעה אפשריים, אשר מהווים מספר רב יותר ממספר האטומים ביקום כולו.
+[[תמונה:William Rowan Hamilton painting.jpg|ממוזער|שמאל||ויליאם רואן המילטון]]
-בתורת הסיבוכיות הוכח שבעיה זו נכללת בקטגוריה [[NP (מחלקת סיבוכיות)#בעיות NP-קשות (NP-Hard) ובעיות NP-שלמות (NPC)|{{כ}}NP-קשה]], והצגתה כ[[בעיית הכרעה]] ("האם קיים מסלול שאורכו פחות מ-x ק"מ?") היא בקטגוריה [[NP-שלמה]]. ניתן להוכיח שהוספת דרישה שבתום המסע יחזור הסוכן הנוסע לעיר שממנה יצא אינה משנה את ה[[סיבוכיות]] של הבעיה.
+מקורות הבעיה לא ברורים. מדריך לסוכן הנוסע משנת 1832 מזכיר את הבעיה ומכיל דוגמאות למסלולים בגרמניה ושוויץ, אבל לא מכיל התייחסות מתמטית לנושא{{הערה|"הסוכן הנוסע — איך הוא צריך להיות ומה הוא צריך לעשות כדי לקבל עמלה ולהיות בטוח בהצלחת עסקיו" מאת סוכן מכירות לא ידוע (מגרמנית - "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")}}.
-הקושי למצוא פתרון אופטימלי לבעיה דוחף למציאת פתרון קרוב לאופטימלי, באמצעות [[אלגוריתם קירוב]] (ראו תיאור של [[אלגוריתם קירוב#דוגמה לאלגוריתם קירוב|אלגוריתם קירוב לבעיית הסוכן הנוסע]]). [[אלגוריתם חמדן]] הוא דרך מעשית נוספת להשגת פתרון שאינו בהכרח אופטימלי.
+בעיית הסוכן הנוסע נוסחה לראשונה במאה ה-19 על ידי המתמטיקאי האירי [[ויליאם רואן המילטון]] והמתמטיקאי הבריטי [[תומאס קירקמן]] (Thomas Kirkman). המילטון פיתח בשנת 1857 את "משחק איקוסיאן" (Icosian game) שמטרתו הייתה למצוא [[מסלול המילטוני]] שיעבור בכל הקודקודים של [[דודקהדרון]] בדיוק פעם אחת ויחזור לנקודת ההתחלה.
+הצורה הכללית של בעיית הסוכן הנוסע נחקרה לראשונה על ידי מתמטיקאים בשנת 1930, בפרט על ידי [[קרל מנגר (מתמטיקאי)|קרל מנגר]] שהגדיר את הבעיה והתייחס לפתרונות [[כוח גס]] ושיטת השכן הקרוב{{הערה|מגרמנית: "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."}}:{{ציטוט|אנגלית = |תוכן = מבעיית השליחים (כיוון שבפועל הבעיה צריכה להיפתר על ידי כל דוור, וגם על ידי הרבה טיילים) אנו שמים לב למשימה למצוא למספר סופי של נקודות, שהמרחק בין כל צמד ידוע, את המסלול הקצר ביותר שיחבר את כל הנקודות. כמובן שהבעיה פתירה מכך שיש מספר סופי של מסלולים. חוקים שיורידו את מספר המסלולים מתחת למספר התמורות אינם ידועים. השיטה בה יש ללכת מנקודת ההתחלה לנקודה הקרובה ביותר, ואז לקרובה ביותר אליה וכדומה, בכלליות לא מפיקה את המצלול הקצר ביותר.|מקור = }}בשנות ה-50 וה-60 של המאה ה-20 הבעיה הפכה פופולארית באירופה וארצות הברית לאחר ש[[תאגיד ראנד]] מ[[סנטה מוניקה]] הציע פרסים על מציאת שלבים בפתרון הבעיה. בעשורים שלאחר מכן נחקרה הבעיה על ידי מתמטיקאים, חוקרי מדעי המחשב, כימאים, פיזיקאים ומדענים אחרים. לעומת זאת, בשנות ה-60 התפתחה גישה חדשה - במקום לחפש את הפתרון האופטימלי, החלו אנשים לחפש את הפתרון הגרוע ביותר ובכך מצאו חסם עליון לבעיה.
+[[ריצ'רד קארפ]] הראה בשנת 1972 שמסלול המילטון היא בעיה השייכת לקטגוריה [[NP-שלמה]], ובכך סיפק הסבר מתמטי לקושי החישובי במציאת מסלול אופטימלי.
+בשנת 1991 פרסם [[ג'רארד ריינלט]] ספרייה בשם TSPLIB שכללה אוסף של רשימות ערים לדוגמה בדרגות קושי שונות. חוקרים רבים עשו שימוש נרחב בספרייה, ובשנת 2006 [[ויליאם ג'ון קוק]] וחוקרים נוספים חישבו מסלול אופטימלי שעבר ב-85,900 נקודות, נכון להיום החישוב הגדול ביותר מתוך TSPLIB. ספריה זו מתוחזקת לצורך בדיקת אלגוריתמים לפתרון הבעיה, ומכילה נתונים רבים, חלקם ערים ומעגלים מודפסים אמתיים.
+== מאפיינים ==
+[[תמונה:Weighted K4.svg|ממוזער|שמאל||בעיית הסוכן הנוסע סימטרית עם 4 ערים]]
+=== הצגה כבעיית גרפים ===
+ניתן להציג את בעיית הסוכן הנוסע כ[[גרף ממושקל]] לא מכוון, בו כל עיר היא [[צומת (תורת הגרפים)|צומת]], שביל בין עיר לעיר היא [[תורת הגרפים|קשת]], והמרחק בין כל שתי ערים מצוין על ידי משקל הקשת המחברת ביניהן. בצורה כזו ניתן לשאול מהו המסלול עם המשקל הנמוך ביותר, שיצא ויחזור לאותו צומת לאחר שעבר בכל צומת אחר פעם אחת בדיוק. לרוב הבעיה תוצג על גבי [[גרף שלם]] (גרף בו כל זוג צמתים מחוברים בקשת). אם לא קיימת דרך בין שתי ערים ניתן להוסיף לגרף קשת עם משקל גבוה מאוד ובכך להשלים את הגרף לגרף שלם מבלי לפגוע בפתרון האופטימלי.
+=== סימטריות ===
+בגרסה ה[[סימטריה|סימטרית]] של הבעיה, המרחק בין כל שתי ערים זהה למרחק בכיוון ההפוך בין אותן שתי ערים. במקרה כזה תוצג הבעיה כגרף לא מכוון. סימטריה זו מקטינה את מספר הפתרונות האפשריים פי שניים. בגרסה ה[[אסימטריה|א-סימטרית]] של הבעיה, יתכן ודרך לא תתאפשר לשני הכיוונים, או שהמרחק בכיוונים שונים יהיה שונה. במקרה כזה תוצג הבעיה כגרף מכוון. דוגמאות לדרכים בהן ניתן להפוך את הבעיה לבעיה א-סימטרית הן כבישים חד סטריים, נתיבי תעופה בין ערים עם זמני הגעה או עלויות שונות, תאונות דרכים ועוד.
+=== סיבוכיות חישוב ===
+בעיה זו נכללת בקטגוריה [[NP-קשה]], והצגתה כ[[בעיית הכרעה]] (בהינתן האורך X, קבע האם קיים מסלול שאורכו קטן מ-X) שייכת לקטגוריה [[NP-שלמה]]. לכן, אפשרי ש[[סיבוכיות זמן|זמן הריצה]] הגרוע ביותר של כל [[אלגוריתם]] לפתרון הבעיה יפעל ב[[זמן ריצה מעריכי|סדר גודל מעריכי]] כתלות בקלט (מספר הערים).
+=== מאפיינים נוספים ===
+* ניסוח הבעיה במונחי תורת הגרפים: בהינתן [[גרף ממושקל]] [[גרף שלם|שלם]] לא מכוון, מהו המסלול ההמילטוני שמשקלו הוא הקטן ביותר.
+* הדרישה שהמסלול יסתיים בנקודה בה התחיל לא משפיעה על [[סיבוכיות]] החישוב של הבעיה.
+* בעיית הסוכן הנוסע היא מקרה פרטי של [[בעיית הקונה הנוסע]] העוסקת בקונה שעליו לקנות מספר פריטים. הוא יכול לרכוש אותם בערים שונות אך לא בכולן אותם המחירים. המטרה היא למצוא את המסלול שיקטין את עלויות הרכישה (מחיר הפריטים ומחיר הנסיעה) למינימום.
+== פתרון הבעיה ==
+הקווים המנחים לטיפול בבעיות [[NP-קשה|NP-קשות]] הם:
+* תכנון [[אלגוריתם|אלגוריתמים]] למציאת פתרון מדויק (יעבדו בזמן סביר רק עבור מספר קטן של ערים)
+* תכנון אלגוריתמים [[היוריסטיקה|היוריסטים]] למציאת קירובים טובים לפתרון, אך לא פתרונות מדויקים מוכחים.
+* מציאת מקרים פרטיים של הבעיה להם קיימים פתרונות מדויקים.
+=== אלגוריתמים מדויקים ===
+[[תמונה:Bruteforce.gif|מסגרת|שמאל||פתרון בעיה סימטרית עם 7 ערים. משמאל - האפשרות הנבדקת. מימין - האפשרות הטובה ביותר עד כה. מספר האפשרויות - 360]]
+פתרון פשוט לבעיה הוא בדיקת כל ה[[תמורה (מתמטיקה)|תמורות]] האפשריות וחיפוש המסלול הקצר ביותר (תוך שימוש ב[[כוח גס]]). פתרון זה מצריך בדיקה של <math>n!</math> אפשרויות ([[עצרת]] של מספר הערים), ולכן סיבוכיות זמן הריצה במקרה כזה תהיה <math>O(n!)</math>. חישוב כזה הופך מהר מאוד לבלתי מעשי (לבלתי [[חישוב יעיל|יעיל]], במינוח של [[מדעי המחשב]]). דוגמה להמחשת הבעיה: אם ישנן 70 ערים בהן על הסוכן לבקר, יצטרך הסוכן לבחון <math>70!</math> מסלולי נסיעה אפשריים, אשר מהווים מספר רב יותר ממספר האטומים ביקום כולו.
+בשנת 2001 נמצא פתרון מדויק של הבעיה עם 15,112 ערים בגרמניה מתוך TSPLIB. החישובים התבצעו ברשת של 110 [[מעבד|מעבדים]] באוניברסיטאות רייס [[אוניברסיטת פרינסטון|ופרינסטון]] שבארצות הברית. במאי 2004 נמצא מסלול באורך 72,500 קילומטרים שעבר בכל 24,978 הערים בשוודיה והוכח כמסלול הקצר ביותר שקיים<ref>{{קישור כללי|הכותב = |כתובת = http://www.math.uwaterloo.ca/tsp/sweden/|כותרת = הטיול האופטימלי בשוודיה (אנגלית)|אתר = |תאריך = 2004}}</ref>. במרץ 2005 נמצא מסלול שעבר דרך 33,810 נקודות על [[מעגל מודפס]] שאורכו היה 66,048,945 (יחידות TSPLIB). חישוב המסלול ארך זמן המקביל ל-15.7 שנות חישוב של מעבד ממוצע באותה התקופה. באפריל 2006 נמצא מסלול שעבר דרך 85,900 נקודות, בכוח עיבוד שהקביל ל-136 שנות חישוב.
+=== קירובים לפתרון ===
+[[תמונה:Nearestneighbor.gif|מסגרת|שמאל||דוגמה לאלגוריתם השכן הקרוב. הפתרונות משתנים לפי נקודת המוצא]]
+למרות שהבעיה קשה לחישוב, כיום ידועות מספר [[היוריסטיקה|היוריסטיקות]] לפתרונות מקורבים שלה. שיטות מודרניות יכולות למצוא פתרונות לבעיות גדולות מאוד (מיליוני ערים), בזמן סביר, שמובטחים להיות בסטייה של עד 2-3% מהמסלול האופטימלי.<ref>{{צ-מאמר|מחבר = 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}}</ref>
+==== אלגוריתם חמדן ====
+דוגמה ל[[אלגוריתם חמדן]] המחפש קירוב למסלול הקצר ביותר היא "שיטת השכן הקרוב". בשיטה זו בכל צעד הסוכן יפנה לעיר הקרובה אליו ביותר שעוד לא ביקר בה. בעזרת אלגוריתם זה ניתן לקבל במהירות מסלול קצר ויעיל. עבור מספר מסוים של ערים בפיזור אקראי לרוב יתקבל מסלול ארוך ב-25% מהמסלול הקצר ביותר<ref>{{צ-מאמר|מחבר = Johnson, D.S. and McGeoch, L.A.|שם = The traveling salesman problem: A case study in local optimization|כתב עת = Local search in combinatorial optimization|שנת הוצאה = 1997}}</ref>. עם זאת, קיימים סידורי ערים מיוחדים שגורמים לאלגוריתם זה להניב את התוצאה הגרועה ביותר, הן בגרסה הסימטרית והן בגרסה הא-סימטרית.
+== יישומים נוספים ==
+בנוסף לחשיבותה התאורטית בתחום [[חקר ביצועים]], לבעיה גם חשיבות מעשית - לא רק בתחום ה[[תחבורה]] וה[[לוגיסטיקה]], אלא גם בייצורו של [[מעגל מודפס]], שבו על מכונת הייצור לעבור מסלול מסוים בעת שהיא יוצרת חורים בלוח שעליו נמצא המעגל. שימוש נוסף מגיע מתחום האסטרונומיה - אסטרונומים הצופים בגופים רבים בחלל רוצים לצמצם את הזמן שנדרש לכיוון הטלסקופ בין גוף לגוף ככל האפשר, ובכך לייעל את עבודתם.
+== ביצועים אנושיים ==
+בעיית הסוכן הנוסע עניינה חוקרים מתחום ה[[פסיכולוגיה קוגניטיבית|פסיכולוגיה הקוגניטיבית]] שבדקו את הביצועים האנושיים בהתמודדות עם הבעיה. מחקרים מראים שאנשים מסוגלים ליצור פתרונות איכותיים במהירות{{הערה|Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem", Perception & Psychophysics 58 (4): 527–539, doi:10.3758/BF03213088}}, מסקנה שרומזת שיתכן וביצועי מחשבים בתחום יכולים להשתפר על ידי הבנה וחיקוי של דרכי חשיבה של בני אדם. מחקרים אלו גם הובילו לגילויים חדשים על המנגנון שמאחורי המחשבה האנושית<ref>{{צ-מאמר|מחבר = James N. MacGregor, Yun Chu|שם = סקירת ביצועים אנושיים בבעיית הסוכן הנוסע ובעיות אחרות (מאנגלית - Human Performance on the Traveling Salesman and
+Related Problems: A Review)|כתב עת = The Journal of Problem Solving|כרך = כרך 3|שנת הוצאה = חורף 2011}}</ref>. הגיליון הראשון של כתב העת "''Journal of Problem Solving"'' הוקדש לנושא של ביצועים אנושיים בניסיון פתרון הבעיה.
+== בתרבות ==
+"''הסוכן הנוסע''" (''Travelling Salesman)'' מאת הבמאי טימותי לנזון הוא סיפור על ארבעה מתמטיקאים שנשכרו על ידי ממשלת ארצות הברית כדי לפתור את הבעיה הקשה בהיסטוריית מדעי המחשב: [[בעיית P נגד NP]].<ref>{{קישור כללי|כותרת = 'Travelling Salesman' movie considers the repercussions if P equals NP  (Wired UK)|כתובת = http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman|אתר = Wired|תאריך_וידוא = 2015-11-10|הכותב = DUNCAN GEERE|תאריך = 26/04/2012}}</ref>
+== ראו גם ==
+* [[NP (מחלקת סיבוכיות)]]
+* [[בעיית הדוור הסיני]]
+* [[הגשרים של קניגסברג]]
+== לקריאה נוספת ==
+== קישורים חיצוניים ==
+* [http://www.math.uwaterloo.ca/tsp/index.html בעיית הסוכן הנוסע], [[אוניברסיטת ווטרלו]]
+* ספריית [http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ TSPLIB], [[אוניברסיטת היידלברג]]
+== הערות שוליים ==
-{{קצרמר|מדעי המחשב}}
 [[קטגוריה:תורת הגרפים]]
 [[קטגוריה:בעיות NP-שלמות]]

	הערך נמצא בשלבי עבודה במסגרת מיזם "עבודות ויקידמיות". נא לא לערוך ערך זה עד להסרת התבנית. הערות לערך נא להוסיף בדף השיחה.
	העבודה על הערך עתידה להסתיים בתאריך 31 בינואר 2016. ניתן להסיר את התבנית משחלפו שלושה שבועות מן התאריך הנקוב.	שיחה

הערך נמצא בשלבי עבודה במסגרת מיזם "עבודות ויקידמיות". נא לא לערוך ערך זה עד להסרת התבנית. הערות לערך נא להוסיף בדף השיחה.
העבודה על הערך עתידה להסתיים בתאריך 31 בינואר 2016. ניתן להסיר את התבנית משחלפו שלושה שבועות מן התאריך הנקוב.