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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

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

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