أ* إرشادي، المبالغة في التقدير/التقليل من التقدير؟

Question

أنا في حيرة من أمري بشأن مصطلحات المبالغة في التقدير/التقليل من التقدير.أنا أفهم تمامًا كيف تعمل خوارزمية A*، لكنني غير متأكد من تأثيرات وجود إرشادي يبالغ في تقديره أو يقلل من شأنه.

هل هناك مبالغة في التقدير عندما تأخذ مربع خط رؤية الطائر المباشر؟ولماذا يجعل الخوارزمية غير صحيحة؟يتم استخدام نفس الكشف عن مجريات الأمور لجميع العقد.

هل يعتبر التقليل من شأن عندما تأخذ الجذر التربيعي لخط رؤية الطيور المباشر؟ولماذا لا تزال الخوارزمية صحيحة؟

لم أتمكن من العثور على مقال يشرح الأمر بشكل لطيف وواضح، لذا آمل أن يكون لدى شخص ما هنا وصف جيد.

Answer 1

أنت تبالغ عندما تقدير الكشف عن مجريات الأمور هو أعلى من تكلفة مسار النهائية الفعلية. كنت التقليل عندما يكون أقل (لم يكن لديك أن نقلل، عليك أن لا نبالغ؛ <م> الصحيحة التقديرات على ما يرام). إذا كانت تكاليف حافة الرسم البياني الخاص بك كلها 1، ثم الأمثلة تعطي من شأنه أن يوفر مبالغات وأقل من الواقع، على الرغم من السهل تنسيق المسافة أيضا يعمل خوخي في الفضاء الديكارتي.

والمبالغة لا يجعل بالضبط خوارزمية "غير صحيحة". ما يعنيه ذلك هو أن لم يعد لديك ل<م> الكشف عن مجريات الأمور مقبولة ، الذي هو شرط لA * لتكون مضمونة لإنتاج السلوك الأمثل. مع الكشف عن مجريات الأمور غير مقبول، ويمكن للخوارزمية يختتم القيام طن من مسارات عمل دراسة لزوم لها أنه ينبغي أن يكون تجاهل، وربما إيجاد مسارات الأمثل لاستكشاف تلك. سواء كان ذلك يحدث في الواقع يعتمد على مساحة مشكلتك. يحدث ذلك لأن تكلفة الطريق هو 'من أصل مشترك "مع التكلفة التقديرية، مما يعطي أساسا خوارزمية افسدت أفكار حول أي مسارات هي أفضل من غيرها.

ولست متأكدا ما إذا كنت سوف قد وجدت، ولكنك قد ترغب في النظر في ويكيبيديا A * المقالة . أذكر (وصلة) أساسا لأنه من المستحيل تقريبا لجوجل لذلك.

Answer 2

من مقالة ويكيبيديا أ*, ، الجزء ذو الصلة من وصف الخوارزمية هو:

تستمر الخوارزمية حتى تصبح عقدة الهدف أقل F قيمة من أي عقدة في قائمة الانتظار (أو حتى تصبح قائمة الانتظار فارغة).

الفكرة الرئيسية هي أنه، مع التقليل من التقدير، لن يتوقف A* عن استكشاف المسار المحتمل للوصول إلى الهدف إلا عندما يعلم أن التكلفة الإجمالية للمسار ستتجاوز تكلفة المسار المعروف للوصول إلى الهدف.نظرًا لأن تقدير تكلفة المسار يكون دائمًا أقل من أو يساوي التكلفة الحقيقية للمسار، فيمكن لـ A* تجاهل المسار بمجرد أن تتجاوز التكلفة المقدرة التكلفة الإجمالية لمسار معروف.

مع المبالغة في التقدير، ليس لدى A* أي فكرة عن الوقت الذي يمكنه فيه التوقف عن استكشاف مسار محتمل حيث يمكن أن تكون هناك مسارات بتكلفة فعلية أقل ولكن تكلفة تقديرية أعلى من أفضل مسار معروف حاليًا للوصول إلى الهدف.

Answer 3

وبقدر ما أعرف، وتريد أن نقلل عادة بحيث قد لا تزال تجد أقصر الطرق. يمكنك العثور على إجابة أسرع عن طريق المبالغة، ولكن قد لا تجد أقصر الطرق. ومن ثم لماذا المبالغة هو "غير صحيح"، في حين لا يزال التقليل توفير أفضل الحلول.

وأنا آسف أنني لا يمكن أن توفر أي فكرة عن خطوط birdview ...

Answer 4

اجابة قصيرة

إجابة @chaos مضللة بعض الشيء (يجب تسليط الضوء عليها)

المبالغة في التقدير لا تجعل الخوارزمية "غير صحيحة" تمامًا؛ما يعنيه ذلك هو أنه لم يعد لديك إرشادي مقبول، وهو شرط لضمان حصول A* على السلوك الأمثل.مع ارشادي غير مقبول، الخوارزمية يستطيع ينتهي الأمر بالقيام بالكثير من العمل غير الضروري

كما يلمحAlbertoPL

يمكنك العثور على إجابة أسرع من خلال المبالغة في التقدير، لكن قد لا تجد أقصر طريق.

في النهاية (إلى جانب الحل الرياضي الأمثل)، يعتمد الحل الأمثل بشدة على ما إذا كنت تفكر في موارد الحوسبة، ووقت التشغيل، وأنواع خاصة من "الخرائط"/مساحات الحالة، وما إلى ذلك.

اجابة طويلة

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

لإعطائك انطباعًا أفضل، أشاركك بعض النتائج المثالية التي أنشأتها بسرعة باستخدام بايثون.تنبع النتائج من نفس خوارزمية A*، ويختلف فقط الاستدلال.تحتوي كل عقدة (خلية شبكية) على حواف لجميع الجيران الثمانية باستثناء الجدران.تكلفة الحواف القطرية sqrt(2)=1.41

توضح الصورة الأولى المسارات التي تم إرجاعها للخوارزمية في حالة مثال بسيطة.يمكنك رؤية بعض المسارات دون المستوى الأمثل من المبالغة في تقدير الاستدلال (الأحمر والسماوي).من ناحية أخرى، هناك العديد من المسارات المثالية (الأزرق والأصفر والأخضر) ويعتمد ذلك على الكشف عن المسار الذي تم العثور عليه أولاً.

تُظهر الصور المختلفة كافة العقد الموسعة عند الوصول إلى الهدف.يُظهر اللون تكلفة المسار المقدرة باستخدام هذه العقدة (مع الأخذ في الاعتبار المسار "المتخذ بالفعل" من البداية إلى هذه العقدة أيضًا؛رياضيًا، إنها التكلفة حتى الآن بالإضافة إلى الاستدلال لهذه العقدة).في أي وقت تقوم الخوارزمية بتوسيع العقدة بأقل تكلفة إجمالية مقدرة (الموصوفة سابقًا).

1.صفر (أزرق)

• يتوافق مع خوارزمية ديكسترا
• تم توسيع العقد:2685
• طول المسار:89.669

2.زي ما تيجي (أصفر)

• تم توسيع العقد:658
• طول المسار:89.669
• https://i.stack.imgur.com/75eFV.png

3.مثالي (أخضر)

• أقصر طريق بدون عوائق (إذا اتبعت الاتجاهات الثمانية)
• أعلى تقدير ممكن دون المبالغة في التقدير (وبالتالي "مثالية")
• تم توسيع العقد:854
• طول المسار:89.669
• https://i.stack.imgur.com/VqMtF.png

4.مانهاتن (أحمر)

• أقصر طريق بدون عوائق (إذا لم تتحرك قطريًا؛بعبارة أخرى:تقدر تكلفة "التحرك قطريًا" بـ 2)
• يبالغ في التقدير
• تم توسيع العقد:562
• طول المسار:92.840
• https://i.stack.imgur.com/gD9t4.png

5.كما يطير الغراب عشر مرات (ازرق سماوي)

• يبالغ في التقدير
• تم توسيع العقد:188
• طول المسار:99.811
• https://i.stack.imgur.com/SZuFH.png