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

من ويكيبيديا، الموسوعة الحرة

[عدل] تعريف و تقديم

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

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

[عدل] حول المشكلة

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

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