نهائية
في الطابور
الحواف المفحوصة

  • الحالية
  • في الطابور
  • نهائية
  • المسار
  • تقدير بخط مستقيم
النقر على عقدة يحدد

مزيد عن بحث A*

بحث A*

يجد بحث A* أقصر مسار من البداية إلى الهدف، مثل خوارزمية ديكسترا، لكنه يعرف تقريبًا أين يقع الهدف. تحصل كل عقدة على تقدير للمسافة المتبقية، وهو الخط المستقيم إلى الهدف، ويواصل البحث دائمًا من العقدة ذات أصغر مجموع للمسافة حتى الآن والتقدير. انقر على عقدة لتبدأ منها، واختر هدفًا، وتقدّم خطوة بخطوة لترى البحث يتجه نحو الهدف ويترك زوايا كاملة من الرسم البياني دون أن يمسّها. اضغط «تشغيل» لمشاهدة البحث، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. انقر على عقدة لتجعلها البداية؛ وحوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى لتجعلها الهدف. الرقم على كل حافة هو طولها، والرقم على كل عقدة هو مسافتها حتى الآن، والخط المتقطع هو تقدير المسافة المتبقية بخط مستقيم. والصف أسفل الرسم البياني هو الطابور، الأدنى درجةً أولاً، مع درجة كل عقدة: المسافة حتى الآن مضافًا إليها التقدير. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

كيف يعمل

  1. انقر على عقدة لتجعلها البداية. حوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى لتجعلها الهدف.
  2. اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع في البحث.
  3. راقب الدرجات في الطابور والتقدير المتقطع بخط مستقيم. وفي النهاية، قارن عدد العقد التي احتاجها A* بخوارزمية ديكسترا.

كيف يعمل بحث A*

أعطِ البداية المسافة 0 وضعها في طابور. لكل عقدة في الطابور درجة: مسافتها حتى الآن مضافًا إليها تقدير المسافة المتبقية. كرّر: خذ العقدة ذات أدنى درجة، واجعل مسافتها نهائية. إن كانت هي الهدف، فتوقف. وإلا، فلكل جار لم يصبح نهائيًا، أضف طول الحافة إلى مسافة العقدة؛ فإن كان الناتج أقصر من مسافة الجار حتى الآن، فاخفضها، وتذكّر العقدة طريقًا إليه، وضع الجار في الطابور بدرجته الجديدة.

لماذا يجب ألا يكون التقدير أطول من اللازم

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

الأسئلة المتداولة

ما بحث A*؟

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

ما الدالة الاستدلالية المقبولة؟

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

هل A* أسرع من خوارزمية ديكسترا؟

عادةً نعم، حين تحتاج إلى الطريق إلى هدف واحد ولديك تقدير جيد: يجعل A* عددًا أقل من العقد نهائيًا، لأن العقد البعيدة عن الهدف تحصل على درجات عالية. وبتقدير 0 يفعل تمامًا ما تفعله خوارزمية ديكسترا. وخوارزمية ديكسترا هي الخيار الأفضل حين تحتاج إلى المسافات إلى كل العقد.

أين يُستخدم A*؟

في ألعاب الفيديو لتحريك الشخصيات حول العوائق، وفي مخططات المسارات، وفي تخطيط حركة الروبوتات، وفي برامج حل الألغاز مثل لغز الـ15، حيث يحسب التقدير بُعد البلاطات عن أماكنها.

هل يُرسل الرسم البياني إلى أي مكان؟

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

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر