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

تنجح خوارزمية البحث بأولوية الاتساع (BFS) في إيجاد المسار الأقصر بعد فحص 10 خلايا. يمكن تصوير عملية البحث المطبقة بخوارزمية البحث بأولوية الاتساع (BFS) بسهولة عند تصوير المتاهة بالتمثيل المستند إلى مخطط. المثال التالي يعرض متاهة 3x3 وتمثيلها بالمخطط:يتضمن تمثيل المخطط عقدة واحدة لكل خلية غير مشغولة. توضح القيمة على العقد إحداثيات خلية المصفوفة المقابلة. ستظهر حافة غير موجهة من عقدة إلى أخرى في حال كانت الخلايا المقابلة يمكن الوصول إليها من خلال الانتقال من واحدة إلى الأخرى. إحدى الملاحظات المهمة حول خوارزمية البحث بأولوية الاتساع (BFS) هي أنه في حالة المخططات غير الموزونة (Unweighted Graphs) يكون المسار الأول الذي تحدده الخوارزمية بين خلية البداية وأي خلية أخرى هو المسار الذي يتضمن أقل عدد من الخلايا التي تم فحصها. وهذا يعني أنه إذا كانت كل الحواف في المخطط لها الوزن نفسه، أي كان لكل الانتقالات من خلية إلى أخرى التكلفة نفسها، فإن المسار الأول الذي تحدده الخوارزمية إلى عقدة محددة يكون هو المسار الأقصر إلى تلك العقدة. ولهذا السبب، تتوقف دالة البحث bfs_maze_solver() عن البحث، وتعرض نتيجة المرة الأولى التي فحصت فيها العقدة المستهدفة.ومع ذلك، لا يمكن تطبيق هذه المنهجية على المخططات الموزونة (Weighted Graphs). المثال التالي يوضح إصداراً موزوناً (Weighted Version) لتمثيل مخطط متاهة 3x3:--- SECTION: شكل 2.21: المتاهة ومخططها الموزون --- شكل 2.21: المتاهة ومخططها الموزون في هذا المثال، يكون وزن كل الحواف المقابلة للحركات الرأسية أو الأفقية (جنوبًا، شمالاً، غربًا، شرقًا) يساوي 1. ومع ذلك، يكون وزن كل الحواف المقابلة للحركات القطرية (جنوبية غربية، جنوبية شرقية، شمالية غربية، شمالية شرقية) يساوي 3. في هذه الحالة الموزونة، سيكون المسار الأقصر هو [(2,0), (1,0), (0,0), (0,1), (0,2), (1,2)]، بمسافة إجمالية: 1+1+1+1+1=5.يمكن ترميز هذه الحالة الأكثر تعقيدًا باستخدام الإصدار الموزون من الدالة ()get_accessible_neighbors الموضحة بالأسفل.def get_accessible_neighbors_weighted(maze: np.ndarray, cell: tuple, horizontal_vertical_weight: float, diagonal_weight: float):2025 - 1447--- VISUAL CONTEXT --- **DIAGRAM**: تمثيل متاهة 3x3 ومخططها غير الموزون Description: A diagram showing an unweighted graph representation of a 3x3 maze and its corresponding grid. The graph nodes are labeled with (row, column) coordinates: (1,0), (0,0), (1,2), (2,0), (0,1), (0,2). Edges connect adjacent accessible cells. The 3x3 grid shows the maze layout, with shaded cells representing obstacles. A star symbol marks the cell (2,0) as the start point, and an 'X' symbol marks the cell (1,2) as the target. Data: The graph visually represents the connectivity between accessible cells in the maze. The grid provides a visual context of the maze structure. Key Values: Nodes: (1,0), (0,0), (1,2), (2,0), (0,1), (0,2), Start point: (2,0), Target point: (1,2), Grid dimensions: 3x3 Context: Illustrates the concept of representing a maze as an unweighted graph for pathfinding algorithms like Breadth-First Search (BFS).**DIAGRAM**: شكل 2.21: المتاهة ومخططها الموزون Description: A diagram showing a weighted graph representation of the same 3x3 maze and its corresponding grid. The graph nodes are labeled with (row, column) coordinates: (1,0), (0,0), (1,2), (2,0), (0,1), (0,2). Edges connecting horizontally or vertically have a weight of 1. Edges connecting diagonally have a weight of 3. The 3x3 grid is identical to the unweighted version, with shaded cells as obstacles, a star at (2,0) as the start, and an 'X' at (1,2) as the target. Data: The graph visually represents the connectivity and associated costs (weights) for movements between accessible cells in the maze. The grid provides a visual context of the maze structure. Key Values: Nodes: (1,0), (0,0), (1,2), (2,0), (0,1), (0,2), Edge weight (horizontal/vertical): 1, Edge weight (diagonal): 3, Start point: (2,0), Target point: (1,2), Shortest path: [(2,0), (1,0), (0,0), (0,1), (0,2), (1,2)], Total path weight: 1+1+1+1+1=5, Grid dimensions: 3x3 Context: Demonstrates how edge weights can be assigned to represent different movement costs in a maze, leading to a weighted graph problem. This is used to explain pathfinding in weighted graphs where the shortest path is determined by the sum of edge weights.