خوارزمية*
على
؟ كيف تعرف ما إذا كان الاحتمال واعد؟
- من خلال الدالة f (x) = g (x) + h (x)
- وهي وظيفة إرشادية
- G (x) هي تكلفة ، من الأصل ، الوصول إلى العقدة x
- H (x) هي وظيفة مجريات الأمور لتقدير تكلفة العقدة التالية
- ننظر دائمًا إلى إمكانيات توسيع الشجرة وحساب قيمة F (x)
- نضيف العقدة التي تحتوي على أصغر F (x) من بين أولئك الذين نجدهم
- OA* هي الخوارزمية الأكثر فعالية للحصول على الحد الأدنى من الطرق في الرسوم البيانية
- ومع ذلك ، فهي قيود شديدة
- من الضروري تحديد H (x) المقبول: لن يعيد أبدًا قيمة أكبر من المسافة الفعلية من x إلى y
- إذا كان H (x) مقبولًا ، ولكنه قلل من تقدير المسافة الفعلية ، فإن الخوارزمية غير فعالة للغاية. إذا لم يكن H (x) مقبولًا ، فقد لا تجد الخوارزمية الحد الأدنى
؟ تعقيد
- التعقيد يعتمد مباشرة على الوظيفة H (x) المستخدمة.
- في أسوأ الحالات ، تكون كمية العقد التي تم استكشافها أسيًا في حجم المسار الأصغر ، ولكن لها تعقيد متعدد الحدود إذا كان H ∗ (x) −H (x) ≤O (logh ∗ (x)).
؟ متى يكون من الجيد استخدامه؟
- الرسوم البيانية حيث يمكن للمرء أن يقلل من المسافة بين اثنين من القمت ، كما في الخرائط
- أقصر مسافة بين نقطتين هي خط ، ولكن ربما تكون المسافة الفعلية أكبر من ذلك
؟ ما هو الحد الأدنى في هذه الحالة؟
تنفيذ المشروع
نتيجة
المؤلفون
رخصة
هذا المشروع تحت معهد ماساتشوستس للتكنولوجيا. انظر هنا لمزيد من المعلومات.
