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