📄 النص الكامل للصفحة
وكما هو متوقع، أخطأت أداة الحل في البحث بأولوية الاتساع (BFS solver) في عرض المسار السابق نفسه بالضبط، على الرغم من أن التكلفة تساوي 7. ومن الواضح أنه ليس المسار الأقصر. ويرجع ذلك إلى الطبيعة غير المستنيرة لخوارزمية البحث بأولوية الاتساع (BFS)، حيث لا تأخذ الخوارزمية الأوزان بعين الاعتبار عند تحديد الخلية المقرر توسيعها في الخطوة التالية؛ لأنها تطبق ببساطة منهجية البحث بالعرض نفسها والتي تؤدي إلى المسار نفسه الذي وجدته الخوارزمية في الإصدار غير الموزون (Unweighted Version) من المتاهة. القسم التالي يصف طريقة معالجة نقطة الضعف هذه باستخدام خوارزمية البحث بأولوية الأفضل (A* search)، وهي خوارزمية مستنيرة وأكثر ذكاءً تضبط سلوكها وفقاً للأوزان المحددة، وبالتالي يمكنها حل المتاهات باستخدام الانتقالات الموزونة (Weighted Transitions) والانتقالات غير الموزونة (Unweighted Transitions).--- SECTION: استخدام خوارزمية البحث بأولوية الأفضل في حل ألغاز المتاهة --- استخدام خوارزمية البحث بأولوية الأفضل في حل ألغاز المتاهة--- SECTION: Using A* Search to Solve Maze Puzzles ---
Using A* Search to Solve Maze Puzzlesكما في خوارزمية البحث بأولوية الاتساع (BFS)، تفحص خوارزمية البحث بأولوية الأفضل (A* search) خلية واحدة في كل مرة بفحص كل خلية مجاورة يمكن الوصول إليها. فبينما تستخدم خوارزمية البحث بأولوية الاتساع (BFS) منهجية بحث عمياء بأولوية العرض لتحديد الخلية التالية التي ستفحصها، تفحص خوارزمية البحث بأولوية الأفضل (A* search) الخلية التي يكون بينها وبين الخلية المستهدفة أقصر مسافة محسوبة بواسطة الدالة الاستدلالية (Heuristic Function). يعتمد التعريف الدقيق للدالة الاستدلالية على التطبيق. في حالة ألغاز المتاهة، توفر الدالة الاستدلالية تقديراً دقيقاً لمدى قرب الخلية المرشحة إلى الخلية المستهدفة. يضمن الاستدلال المطابق عدم المبالغة في تقدير (Overestimate) المسافة الفعلية إلى الخلية المستهدفة مثل: عرض مسافة تقديرية أكبر من المسافة الحقيقية إلى الهدف. وبالتالي ستجد الخوارزمية أقصر مسار محتمل لكل من المخططين الموزون (Weighted) وغير الموزون (Unweighted). إذا كان الاستدلال يبالغ في بعض الأحيان في تقدير المسافة، ستستخدم خوارزمية البحث بأولوية الأفضل (A* search) حلاً، ولكن قد لا يكون الأفضل. الاستدلال المحتمل الأبسط الذي لن يؤدي إلى المبالغة في تقدير المسافة هو دالة بسيطة تعطي دوماً مسافة تقديرية قدرها وحدة واحدة.def constant_heuristic(candidate_cell:tuple, target_cell:tuple):
return 1على الرغم من أن هذا الاستدلال شديد التفاؤل، إلا أنه لن يقدم أبداً تقديراً أعلى من المسافة الحقيقية، وبالتالي سيؤدي إلى أفضل حل ممكن. سيتم تقديم استدلال متطور يمكنه العثور على أفضل حل بشكل سريع في هذا القسم لاحقاً.تستخدم الدالة التالية دالة استدلالية معطاة للعثور على الخلية التي يجب توسيعها بعد ذلك:def get_best_candidate(expansion_candidates:set,
shortest_distance:dict,
heuristic:Callable):
winner = None
# best (lowest) distance estimate found so far. Initialized to a very large number best_estimate= sys.maxsize for candidate in expansion_candidates:
# distance estimate from start to target, if this candidate is expanded next2023 - 1447--- VISUAL CONTEXT ---
**DIAGRAM**: شكل 2.22: الاستدلال الثابت
Description: A simple graph diagram showing three circular nodes connected by edges. The nodes are labeled (1,0), (0,0), and (0,1). Node (1,0) is connected to (0,0) by an edge labeled '1'. Node (0,0) is connected to (0,1) by an edge labeled '1'.
Data: The diagram illustrates a small graph with three nodes and two edges, each edge having a weight of 1. It represents a pathfinding scenario.
Key Values: Node (1,0), Node (0,0), Node (0,1), Edge weight 1
Context: This diagram visually represents the concept of a constant heuristic, where each step or transition has a uniform estimated cost (here, 1), as discussed in the context of the A* search algorithm.
🎴 بطاقات تعليمية للمراجعة
عدد البطاقات: 5 بطاقة لهذه الصفحة
لماذا تفشل خوارزمية البحث بأولوية الاتساع (BFS) في إيجاد أقصر مسار في المتاهات الموزونة؟
الإجابة: تفشل خوارزمية BFS في إيجاد أقصر مسار في المتاهات الموزونة لأنها لا تأخذ الأوزان بعين الاعتبار عند تحديد الخلية التالية للتوسع، بل تطبق منهجية البحث بالعرض فقط، مما يؤدي إلى نتائج مشابهة للإصدار غير الموزون.
الشرح: خوارزمية BFS مصممة للبحث عن أقصر مسار في الرسوم البيانية غير الموزونة. في المتاهات الموزونة، يمكن أن يكون المسار الذي يبدو أقصر ظاهرياً (من حيث عدد الخطوات) ليس هو الأقصر من حيث التكلفة الإجمالية بسبب اختلاف أوزان الانتقالات.
تلميح: فكر في ما لا تراعيه خوارزمية BFS بشكل أساسي عند اختيار الخطوة التالية، خصوصاً عندما توجد تكاليف مختلفة.
ما هي الخاصية الأساسية التي تميز خوارزمية البحث بأولوية الأفضل (A* search) عن خوارزمية BFS في حل المتاهات؟
الإجابة: تتميز خوارزمية A* search بأنها خوارزمية مستنيرة وتضبط سلوكها وفقاً للأوزان المحددة باستخدام دالة استدلالية (Heuristic Function) لتقدير المسافة إلى الخلية المستهدفة، بينما تستخدم BFS منهجية بحث عمياء.
الشرح: استخدام الدالة الاستدلالية يسمح لـ A* بتقييم أي خلية مرشحة هي الأقرب إلى الهدف بناءً على تقدير، مما يوجه البحث بشكل أكثر كفاءة نحو الحل بدلاً من استكشاف جميع الاحتمالات بنفس المستوى من الأولوية كما تفعل BFS.
تلميح: ما الذي يجعل خوارزمية A* 'ذكية' أو 'مستنيرة' عند اتخاذ قراراتها مقارنة بـ BFS؟
ما هو الهدف من استخدام الدالة الاستدلالية (Heuristic Function) في خوارزمية البحث بأولوية الأفضل (A* search)؟
الإجابة: الهدف هو توفير تقدير دقيق لمدى قرب الخلية المرشحة إلى الخلية المستهدفة، مما يساعد الخوارزمية على تحديد الخلية التي يجب توسيعها في الخطوة التالية بشكل أكثر فعالية.
الشرح: بدون الدالة الاستدلالية، ستتصرف A* مثل BFS. الدالة الاستدلالية الجيدة تقرب A* من إيجاد أقصر مسار بسرعة عن طريق استبعاد المسارات الواعدة بشكل أقل.
تلميح: فكر في دور 'التقدير' أو 'التخمين' في توجيه مسار البحث نحو الهدف.
ما هو الشرط اللازم للدالة الاستدلالية في خوارزمية A* لضمان إيجاد أقصر مسار محتمل؟
الإجابة: يجب أن يكون الاستدلال مطابقاً (Admissible)، مما يعني أنه لا يبالغ أبداً في تقدير المسافة الفعلية إلى الخلية المستهدفة (أي يعطي تقديراً أقل أو يساوي المسافة الحقيقية).
الشرح: إذا بالغت الدالة الاستدلالية في تقدير المسافة، فقد تقود A* إلى اختيار مسار يبدو واعداً ظاهرياً ولكنه في الواقع أطول من مسار آخر لم يتم استكشافه بشكل كافٍ. الاستدلال المطابق يضمن عدم تفويت المسار الأقصر.
تلميح: ما هي 'الخطأ' الذي يمكن أن ترتكبه الدالة الاستدلالية ويمنع A* من العثور على أفضل حل؟
اذكر مثالاً لدالة استدلالية بسيطة يمكن استخدامها في خوارزمية A* لضمان عدم المبالغة في تقدير المسافة.
الإجابة: دالة استدلالية بسيطة تعطي دوماً مسافة تقديرية قدرها وحدة واحدة (1)، بغض النظر عن موضع الخلية المرشحة أو الخلية المستهدفة. يمكن تمثيلها كالتالي: `def constant_heuristic(candidate_cell:tuple, target_cell:tuple): return 1`
الشرح: حتى لو كانت المسافة الفعلية هي صفر، فإن تقدير 1 لا يبالغ. هذا الاستدلال 'متفائل' ولكنه يضمن فعالية A* في إيجاد الحل الأفضل، وإن كان قد يتطلب توسيع عدد أكبر من الخلايا مقارنة باستدلالات أكثر تطوراً.
تلميح: ما أبسط قيمة تقديرية يمكن إسنادها والتي لن تتجاوز أبداً المسافة الفعلية؟