الفرق بين المراجعتين لصفحة: «مسألة الرحالة التاجر»
اذهب إلى التنقل
اذهب إلى البحث
ط (١ مراجعة: الصفحات في تصنيف رياضيات) |
(تظيف) |
||
| سطر 17: | سطر 17: | ||
[[تصنيف:رياضيات]] | [[تصنيف:رياضيات]] | ||
[[تصنيف:نظرية المخططات]] | [[تصنيف:نظرية المخططات]] | ||
المراجعة الحالية بتاريخ 12:55، 23 أغسطس 2012
تعريف وتقديم
تُعرف مسألة التاجر الرحالة في نظرية المخططات ونظرية المسائل المعقدة كما يلي:
يريد تاجر أن يقوم بجولة كاملة يزور خلالها مدنا حيث يمر بكل المدن مرة واحدة ووحيدة ثم يعود إلى مدينة الانطلاق. المسألة هي: ما هو أقصر طريق؟
حول المشكلة
رغم أن صيغة المسألة تبدو بسيطة، إلا أن الحل صعب جدا, فكلما زاد عدد المدن زادت صعوبة المسألة: يحتاج الحاسوب إلى حوالي قرنين من الزمن لإيجاد أقصر مسار يمر على 100 مدينة
فهذه المسائل تصنف ضمن المسائل الصعبة, وبعبارة أكثر دقة: المسائل الحدودية غير المحددة الكاملة NP-complete.
