مشكلة البائع الجوال: Traveling Salesman Problem

خوارزميات البحث الذكية

• مشكلة البائع الجوال (Traveling Sales Man Problem) هي من أعقد المسائل حيث تعتبر من نوع NP.
• هذه المسألة يعبر عنها باعتبارها مجموعة من المدن التي نريد أن نزور كل منها مرة واحدة انطلاقا من مدينة معينة ويجب العودة إليها في النهاية، وذلك بقطع أقل مسافة ممكنة.
• هناك حالتين من البيانات هنا وهي:
  • بيان محدد بطرق محددة: أي لا يوجد وصلة بين كل عقد البيان.
  • بيان غير محدد بطرق: أي يوجد وصلة بين كل عقد البيان.

فكرة الحل بالخوارزمية التراجعية الكلاسيكية

• إذا أردنا حلها بشكل نظامي باستخدام الخوارزمية التراجعية الكلاسيكية سنحتاج إليّ نسبر فضاء الحلول كاملاً إليجاد الحل المطلوب وبالتالي سيكون التعقيد هذه المسألة من رتبة N.
• يمكن توصيف هذه المسألة بشكل عام على أنها مجموعة من المدن التي نريد أن نزور كل منها مرة واحدة انطلاقا من مدينة معينة ويجب العودة إليها في النهاية، وذلك بقطع أقل مسافة ممكنة.

فكرة الحل بالخوارزميةGreedy Choice

• إذا فكرنا بحل المسألة بفكرة ال Greedy Choice حيث تعتمد هذه الخوارزمية على البحث عن الطريق الأقصر أي إذا كنا في المنطقة A وأردنا الذهاب للمنطقة B سنختار أقصر طريق بينهما "وصلة".
• يمكن القول أن هذه الخوارزمية لا تعطينا حل अमثلي.

إشارات مختلفة

• الإشارة الدورية تطبق عليها س السل فورييه.
• الإشارة الغير دورية تطبق عليها تحويل فورييه.
• الإشارات المركبة مؤلفة من عدة إشارات بسيطة جيبية.
• كل لون من ألوان الطيف في تجربة إسحاق نيوتن له تردد وطول موجة محدد لأن سرعة الضوء ثابتة فيكون التغير في التردد f وطول الموجة λ.
• نبضة ديراك هي إشارة مربعة غير دورية.

أهم النقاط من المحاضرة السابقة

• إن الإشارة سواء طبق عليها سالسل فورييه أو تحويل فورييه فهي تنتقل من مجال الزمن إلى مجال التردد.
• إن الإشارة المركبة تكون في مجال الزمن وهي التي تطبق عليها تحويل فورييه أو سالسل فورييه وبدورها تتحول إلى مجال التردد.

هذه المحاضرة تتناول مادة مشتركة حول مشكلة البائع الجوال (Traveling Salesman Problem) وصعوبة حلها وتصنيفها ضمن نوعية المسائل NP التي تعبر عن المسائل الصعبة للحل.