كيف تجد الملاحة أفضل مسار؟ ديكسترا و A* | الهندسة الفضولية #03

المعلّم: Dr. Süleyman Burak ÇELİK

لماذا قد يكون الطريق الأطول الذي تقترحه الملاحة أسرع؟ نبدأ بمدينة ثلاثية الأبعاد تمثيلية وجسرين، ونبني حساب أفضل مسار خطوة بخطوة. نحدد تكلفة الرحلة، ونحول التقاطعات إلى عقد والطرق إلى حواف موزونة، ثم نتابع ديكسترا على مثال موجه من ست عقد. نرى طابور الأولوية وإرخاء الحواف واستعادة المسار من سجلات العقد السابقة أثناء البحث. في قسم A* ندرس الأولوية f = g + h، وحدًا أدنى للزمن مبنيًا على المسافة المستقيمة مقسومة على السرعة القصوى، وشرطي القبول والاتساق. توضح أمثلة منفصلة كيف قد تؤدي المبالغة في التقدير إلى فقدان أفضل طريق، وكيف يغير إغلاق جسر المسألة، ولماذا تتطلب الأوزان السالبة طريقة مثل بيلمان–فورد. ونختتم بقيود الانعطاف وهياكل البيانات وشبكات الطرق الكبيرة. المقارنة بين 100 و72 في مثال المدينة تخص عدد العقد المفحوصة فقط؛ ولا تمثل بيانات مرور حقيقية أو قياس سرعة لتطبيق ملاحة.