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

shortest_path=reconstruct_shortest_path(parent,start_cell,target_cell) return shortest_path, shortest_distance[target_cell],cell_visits for neighbor,cost in get_neighbors(maze, best_cell): if verbose: print('\nVisiting neighbor cell', neighbor) cell_visits+=1 # first time this neighbor is reached if neighbor not in expansion_candidates and neighbor not in fully_expanded: expansion_candidates.add(neighbor) parent[neighbor] = best_cell # mark the best_cell as this neighbor's parent # update the shortest distance for this neighbor shortest_distance[neighbor] = shortest_distance[best_cell] + cost # this neighbor has been visited before, but a better (shorter) path to it has just been found elif shortest_distance[neighbor] > shortest_distance[best_cell] + cost: shortest_distance[neighbor] = shortest_distance[best_cell] + cost parent[neighbor] = best_cell if neighbor in fully_expanded: fully_expanded.remove(neighbor) expansion_candidates.add(neighbor) # all neighbors of best_cell have been inspected at this point expansion_candidates.remove(best_cell) fully_expanded.add(best_cell) return None, None, None #no solution was foundوكما الحال في الدالة bfs_maze_solver()، تُستخدم الدالة الموضحة بالأعلى كذلك القاموسين shortest_distance و parent لحفظ طول المسار الأقصر من خلية البداية إلى أي خلية أخرى، وحفظ عقدة أصل الخلية في هذا المسار الأقصر. ورغم ذلك، تتبع الدالة astar_maze_solve() منهجية مختلفة لفحص الخلايا وتوسيعها، فهي تستخدم expansion_candidates لتتبع كل الخلايا التي يمكن توسيعها بعد ذلك. في كل تكرار، تُستخدم دالة get_best_candidate() لتحديد أي من الخلايا المرشحة ستوسعها بعد ذلك. بعد اختيار الخلية المرشحة best_cell، تُستخدم حلقة التكرار For لفحص كل الخلايا المجاورة لها. إذا كانت الخلية المجاورة تُفحص للمرة الأولى، فستصبح best_cell عقدة الأصل للخلية المجاورة في المسار الأقصر.2023 - 1447