مدونة نجيب عباس احمد عبدالعليم
مسألة البائع المتجول (Travelling salesman problem )
نجيب عباس احمد عبدالعليم | Najeeb Abdulaleem
30/01/2022 القراءات: 4004
مسألة البائع المتجول (Travelling salesman problem ) إحدى اهم المسائل في نظرية المخططات والاكثر تعقيدا.
نص المسألة هو : وصل تاجر او بائع الى دولة فيها 35 مدينة ويريد البائع يزور جميع هذه المدن في هذه الدولة بحيث يزور كل مدينة مرة واحدة فقط ويزور هذه المدن بالترتيب وينهي مهمة السفر بين المدن في اقصر وقت.
تبدو المسألة بسيطة ولكن الحقيقة هذه المسألة هي احدى المسائل المعقدة والتي لا يعرف لها خوارزمية تحلها بسرعة ودقة مطلوبة، المقصود بالخوارزمية هي مجموعة خطوات رياضية منطقية ومتسلسلة لازمة لحل مشكلة ما وسميت خوارزمية نسبة للعالم محمد بن موسى الخوارزمي وبالتالي اذا حسبنا كم عدد الترتيبات او المحاولات لزيارة 35 مدينة بحيث نختار اقصر طريق من جميع هذه المحاولات او الطرق المحتملة سنجدها تساوي تقريبا 10 اس 40 (10^40) بمعنى 10 دودشيليون محاولة او طريقة وهذا يعني نحتاج الى اكثر من الف عام للوصول الى الحل الذي هو اقصر طريق وبالتالي اطلق على هذه المسألة انها
NP= nondeterminstic polynomial
وتم رصد جائزة بمبلغ مليون دولار لمن يحل هذا النوع من المسائل، ايجاد خوارزمية دقيقة لحل هذا النوع من المسائل سوف يكون لها ايجابيات وسلبيات من الايجابيات سوف تصبح جميع المنتجات رخيصة وبكفائة عالية لان هذه الخوارزمية سوف تقلل تكلفة النقل والتوصيل وتقلص تكلفة التصنيع والتعبيئة ... الخ. ومن السلبيات انها سوف تدمر الانظمة البنكية والمواقع والتطبيقات التي تحتاج الى سرية في التعامل لانه سيكون سهل فك الكلمات السرية
Travelling salesman problem
يجب تسجيل الدخول للمشاركة في اثراء الموضوع