الرئيسيةبحث

مشكلة الرحالة التاجر

تعريف و تقديم

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

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

حول المشكلة

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

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