في نظرية المخططات و نظرية المشاكل المعقدة, تُعرف مشكلة التاجر الرحالة كما يلي:
يريد تاجر أن يقوم بجولة كاملة يزور خلالها مدنا حيث يمر بكل المدن مرة واحدة و وحيدة ثم يعود إلى مدينة الانطلاق. المشكلة هي: ما هو أقصر طريق؟؟
رغم أن صيغة المشكلة تبدو بسيطة, إلا أن الحل صعب جدا, فكلما زاد عدد المدن زادت صعوبة المشكل: يحتاج الحاسوب إلى حوالي قرنين من الزمن لإيجاد أقصر مسار يمر على 100 مدينة
فهذه المشاكل تصنف ضمن المشاكل الصعبة, و بعبارة أكثر دقة: المشاكل الحدودية غير المحددة الكاملة NP-complete.