16-现实世界的应用

2.4　现实世界的应用

在所有实用软件中，搜索算法都在发挥着作用。某些场合中搜索算法正是核心内容（谷歌搜索、Spotlight、Lucene），在其他场合中它是运用底层数据存储结构的基础。对于某个数据结构应选用正确的搜索算法，了解这一点对于提高性能至关重要。例如，在已排序的数据结构上使用线性搜索而不用二分搜索，其代价就会十分高昂。

A是部署最为广泛的路径搜索算法之一。只有那些对搜索空间进行预计算的算法，才能击败A算法。在盲搜（blind search）的情况下，A算法在所有场景中都还没有被确实击败过，这使得它无论在路线规划中还是在查找解析编程语言的最短路径中都成为一种必备组件。大多数导航类地图软件（如谷歌地图）都使用Dijkstra算法（A是其变体）进行导航。第4章中有关于Dijkstra算法的更多信息。在没有人为干预的情况下，如果游戏中的AI角色要查找从世界的一端到另一端的最短路径，那么它可能会使用A*算法。

更为复杂的搜索算法往往是以广度优先搜索和深度优先搜索为基础的，如一致代价（uniform-cost）搜索和回溯搜索（第3章中将会介绍）。广度优先搜索技术通常足以应对在小规模图中查找最短路径，但由于它和A很相似，因此如果大规模图具备良好的启发式信息，则切换为A也很容易。