انقر على الصورة لتطلع على بعض المساهمين في بناء الموسوعة

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

من موسوعة العلوم العربية
اذهب إلى التنقل اذهب إلى البحث

تعريف وتقديم

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

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

حول المشكلة

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

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