مسألة الرحالة التاجر

تعريف وتقديم

تُعرف مسألة التاجر الرحالة في نظرية المخططات ونظرية المسائل المعقدة كما يلي:

يريد تاجر أن يقوم بجولة كاملة يزور خلالها مدنا حيث يمر بكل المدن مرة واحدة ووحيدة ثم يعود إلى مدينة الانطلاق. المسألة هي: ما هو أقصر طريق؟

حول المشكلة

رغم أن صيغة المسألة تبدو بسيطة، إلا أن الحل صعب جدا, فكلما زاد عدد المدن زادت صعوبة المسألة: يحتاج الحاسوب إلى حوالي قرنين من الزمن لإيجاد أقصر مسار يمر على 100 مدينة

فهذه المسائل تصنف ضمن المسائل الصعبة, وبعبارة أكثر دقة: المسائل الحدودية غير المحددة الكاملة NP-complete.