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

تعريف وتقديم

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

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

حول المشكلة

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

فهذه المسائل تصنف ضمن المسائل الصعبة البالغة التعقيد الحوسبي, وبعبارة أكثر دقة: المسائل الحدودية غير المحددة الكاملة NP-complete. أبسط حل رياضي للمشكلة يمكن إيجاده عن طريق توليد جميع الحالات الممكنة ثم بعدها إختيار أقصر و أفضل مسار. مشكلة هذا الحل هو إستحالته الحوسبية، لكون درجة تعقيده الخوارزمي تقع ضمن نطاق !n مما يعني تطلبه لوقت طويل جداً في اجهزتنا الحالية لحل المشكلة.مثلاً لو كان لدينا جهاز بإمكانه توليد مسار جديد كل 3 ميكرو ثانية، سيكون هذا الجهاز قادر على حل المشكلة في ثلاث ثواني إذا كان عدد المدن عشرة و في نصف دقيقة إذا كان عدد المدن إحدى عشر مدينة و في 147 77 سنة إذا كان عدد المدن فقط 20!. المشكلة تكمن في عدد المسارات التي يتم توليدها، إذ أن 12 مدينة فقط تعني 600 001 479 إمكانية (توليفة).