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