خوارزميات البحث المستنيرة - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

على سبيل المثال، تبدأ خوارزمية البحث بأولوية العمق (DFS) عند عقدة الجذر بالشجرة أو المخطط وتتوسع حتى تصل للعقدة الأعمق التي لم تُفحص. ويستمر الأمر بهذه الطريقة حتى تستنفد الخوارزمية مساحة البحث بأكملها بعد فحص كل العقد المتاحة. ثم تُخرج الحل الأمثل الذي وجدته أثناء البحث. فالحقيقة أن خوارزمية البحث بأولوية العمق (DFS) تتبع دومًا هذه القواعد ولا يمكن ضبط استراتيجيتها بصرف النظر عن نتائج البحث، وهذا ما يجعلها خوارزمية غير مستنيرة.ومثال آخر ملحوظ على هذا النوع من الخوارزميات هو خوارزمية البحث بأولوية العمق التكراري المتعمق (Iterative Deepening Depth-First Search - IDDFS) (التي يمكن اعتبارها مزيجًا بين خوارزميتي البحث بأولوية العمق (DFS) والبحث بأولوية الاتساع (BFS))، فهي تستخدم استراتيجية العمق أولاً للبحث في جميع الخيارات الموجودة في النطاق الكامل بصورة متكررة حتى تصل إلى عقدة محددة.--- SECTION: خوارزميات البحث المستنيرة Informed Search Algorithms --- Informed Search Algorithmsعلى النقيض من خوارزميات البحث غير المستنيرة، تستخدم خوارزميات البحث المستنيرة المعلومات حول المشكلة ومساحة البحث لتوجيه عملية البحث. والأمثلة على هذه الخوارزميات تشمل:--- SECTION: الدالة الاستدلالية (Heuristic Function) --- هي الدالة التي تُصنّف البدائل في خوارزميات البحث عند كل مرحلة فرعية استنادًا إلى تقديرات استدلالية مبنية على البيانات المتوفرة لتحديد الفرع الذي ستسلكه.--- SECTION: خوارزمية البحث بأولوية الأفضل (A* search) --- تستخدم دالة استدلالية لتقدير المسافة بين كل عقدة من العقد المرشحة والعقدة المستهدفة. ثم توسع العقدة المرشحة بالتقدير الأقل. إن فعالية خوارزمية البحث بأولوية الأفضل (A* search) مرتبطة بجودة دالتها الاستدلالية. على سبيل المثال، إذا كنت تضمن أن الاستدلال لن يتجاوز المسافة الفعلية إلى الهدف، فبالتالي ستعثر الخوارزمية على الحل الأمثل. بخلاف ذلك، قد لا يكون الحل الناتج من الخوارزمية هو الأفضل.--- SECTION: خوارزمية ديكسترا (Dijkstra's Algorithm) --- توسع العقدة بناء على أقصر مسافة فعلية إلى الهدف في كل خطوة. ولذلك، على النقيض من خوارزمية البحث بأولوية الأفضل، تحسب خوارزمية ديكسترا (Dijkstra) المسافة الفعلية ولا تستخدم التقديرات الاستدلالية. وبينما يجعل هذا خوارزمية ديكسترا أبطأ من خوارزمية البحث بأولوية الأفضل، إلا أن ذلك يعني ضمان العثور على الحل الأمثل دومًا (ممثلاً بالمسار الأقصر من البداية حتى الهدف).--- SECTION: خوارزمية تسلق التلال (Hill Climbing) --- تبدأ بتوليد حل عشوائي، ثم تحاول تحسين هذا الحل بصورة متكررة بإجراء تغييرات بسيطة تُحسّن من دالة استدلالية محددة. وبالرغم من أن هذه المنهجية لا تضمن إيجاد الحل الأمثل، إلا أنها سهلة التنفيذ وتتميز بفعالية كبيرة عند تطبيقها على أنواع معينة من المشكلات.الخلايا ذات اللون البنفسجي هي الخلايا التي تم فحصها، والخلية ذات اللون الأخضر هي موضع البدء، والخلية ذات اللون الأحمر هي موقع الهدف، بينما الخلايا ذات اللون الأصفر تمثل المسار الذي تم العثور عليه.--- SECTION: شكل 2.16: حل المتاهة نفسها باستخدام خوارزمية البحث بأولوية الأفضل وخوارزمية ديكسترا --- شكل 2.16: حل المتاهة نفسها باستخدام خوارزمية البحث بأولوية الأفضل وخوارزمية ديكسترا--- VISUAL CONTEXT --- **DIAGRAM**: شكل 2.16: حل المتاهة نفسها باستخدام خوارزمية البحث بأولوية الأفضل وخوارزمية ديكسترا Description: The figure displays two grid-based maze diagrams, illustrating the pathfinding process of two different search algorithms: Dijkstra's Algorithm and A* search. Both diagrams represent the same maze problem.Each grid consists of cells with various colors indicating their state: - Purple cells: Represent cells that have been examined by the algorithm. - Green cell: Indicates the starting position of the search. - Red cell: Marks the target or goal position. - Yellow cells: Show the path that was found by the algorithm from the start to the goal. - Black cells: Represent obstacles or impassable areas within the maze. - White cells: Represent traversable empty spaces.The left diagram, labeled 'خوارزمية ديكسترا (Dijkstra's Algorithm)', shows a path found from a green starting cell (bottom-left) to a red target cell (middle-right). A significant number of purple cells are visible, indicating a broader exploration of the maze.The right diagram, labeled 'خوارزمية البحث بأولوية الأفضل (A* search)', shows a path found for the same maze problem. Compared to Dijkstra's Algorithm, this diagram shows fewer purple (examined) cells, suggesting a more efficient search process in finding the path from the green start cell (bottom-left) to the red target cell (middle-right). Key Values: Purple cells: examined, Green cell: start, Red cell: target, Yellow cells: found path, Black cells: obstacles, White cells: traversable space Context: This visual element demonstrates the operational differences and relative efficiencies of Dijkstra's Algorithm and A* search, both informed search algorithms, in solving a pathfinding problem within a maze. It visually highlights how A* search, by using a heuristic function, can explore fewer nodes to find a path compared to Dijkstra's, which explores based on actual shortest distance.