منهجية البحث بأولوية الاتساع (BFS) - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

تتبع الدالة منهجية البحث بأولوية الاتساع (BFS) للبحث في كل الخيارات في العمق الحالي قبل الانتقال إلى مستوى العمق التالي. وتستخدم هذه المنهجية مجموعة واحدة تسمى visited وقائمة تسمى to_expand. تتضمن المجموعة الأولى كل الخلايا التي فحصت مرة واحدة على الأقل من قبل الخوارزمية، بينما تتضمن القائمة الثانية كل الخلايا التي لم توسع بعد، مما يعني أن الخلايا المجاورة لم تفحص بعد. تُستخدم الخوارزمية كذلك قاموسين shortest_distance و parent، يحفظ الأول منهما طول المسار الأقصر من خلية البداية إلى كل خلية أخرى، بينما يحفظ الثاني عقدة الخلية الأصل في المسار الأقصر. بمجرد الوصول إلى الخلية الهدف وانتهاء البحث، سيخزن المتغير shortest_distance[target_cell] طول الحل والذي يمثل طول المسار الأقصر من البداية إلى الهدف. يستخدم المقطع البرمجي التالي دالة bfs_maze_solver() لحل المتاهة الصغيرة 3x3 الموضحة بالأعلى:start_cell=(2,0) # start cell, marked by a star in the 3x3 maze target_cell=(1,2) # target cell, marked by an "X" in the 3x3 maze solution, distance, cell_visits=bfs_maze_solver(start_cell, target_cell, small_maze, get_accessible_neighbors, verbose=True)print('\nShortest Path:', solution) print('Cells on the Shortest Path:', len(solution)) print('Shortest Path Distance:', distance) print('Number of cell visits:', cell_visits)Expanding cell (2, 0) Visiting neighbor cell (1, 0)Expanding cell (1, 0) Visiting neighbor cell (0, 0) Visiting neighbor cell (0, 1) Visiting neighbor cell (2, 0)Expanding cell (0, 0) Visiting neighbor cell (0, 1) Visiting neighbor cell (1, 0)Expanding cell (0, 1) Visiting neighbor cell (0, 0) Visiting neighbor cell (0, 2) Visiting neighbor cell (1, 0) Visiting neighbor cell (1, 2)Shortest Path: [(2, 0), (1, 0), (0, 1), (1, 2)] Cells on the Shortest Path: 4 Shortest Path Distance: 3 Number of cell visits: 102023 - 1447