Uninformed and Informed Search

### 启发式搜索与非启发式搜索的区别 #### 非启发式搜索非启发式搜索方法依赖于系统的、全面的方式去遍历整个解空间来找到解决方案。这类算法通常遵循严格的逻辑和数学原则，确保能够发现最优解，但代价可能是巨大的计算资源消耗以及时间成本。例如，在树形结构的数据中执行广度优先搜索(BFS)或深度优先搜索(DFS)，这两种方式都会逐层或者沿着一条路径深入直到触及底部再回溯尝试其他分支。 ```python def bfs(graph, start): queue = [start] visited = set() while queue: node = queue.pop(0) if node not in visited: visited.add(node) for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor) return visited ``` 这种方法虽然能保证最终会到达目的地（如果存在的话），但在面对复杂问题时效率低下[^1]。 #### 启发式搜索相比之下，启发式搜索则引入了一种更加灵活的方法论——即通过利用特定领域内的经验法则或其他形式的知识指导搜索过程，从而更快地定位到接近理想的解答位置。这种策略并不总是能找到全局最佳方案，但它能够在合理的时间内给出足够好的近似结果。比如A*算法就是一种典型的带有启发式的图搜索技术，它不仅考虑了当前节点距离起点的实际开销f(n)=g(n)+h(n),其中`g(n)`是从初始状态到节点n的成本估计值；而`h(n)`则是从节点n到目标的一个估算函数。 ```python import heapq def a_star_search(graph, start, goal, h): open_list = [] heapq.heappush(open_list, (0, start)) came_from = {} cost_so_far = {start: 0} while open_list: _, current = heapq.heappop(open_list) if current == goal: break for next_node in graph[current]: new_cost = cost_so_far[current] + graph.edges[(current, next_node)] if next_node not in cost_so_far or new_cost < cost_so_far[next_node]: cost_so_far[next_node] = new_cost priority = new_cost + h(next_node) heapq.heappush(open_list, (priority, next_node)) came_from[next_node] = current path = reconstruct_path(came_from, start=start, goal=goal) return path def reconstruct_path(came_from, start, goal): reverse_path = [goal] at = goal while at != start: at = came_from[at] reverse_path.append(at) return list(reversed(reverse_path)) ```

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

下一篇 Pycharm 设置自定义模块搜索路径