مشكلة الرحالة التاجر
من ويكيبيديا، الموسوعة الحرة
[تحرير] تعريف و تقديم
في نظرية المخططات و نظرية المشاكل المعقدة, تُعرف مشكلة التاجر الرحالة كما يلي:
يريد تاجر أن يقوم بجولة كاملة يزور خلالها مدنا حيث يمر بكل المدن مرة واحدة و وحيدة ثم يعود إلى مدينة الانطلاق. المشكلة هي ما هو أقصر طريق؟؟
[تحرير] حول المشكلة
رغم أن صيغة المشكلة تبدو بسيطة, إلا أن الحل صعب جدا, فكلما زاد عدد المدن زادت صعوبة المشكل: يحتاج الحاسوب إلى حوالي قرنين من الزمن لإيجاد أقصر مسار يمر على 100 مدينة
فهذه المشاكل تصنف ضمن المشاكل الصعبة, و بعبارة أكثر دقة: المشاكل الحدودية غير المحددة الكاملة NP-complet.