High-Performance Domain-Independent Heuristic Search

最熟悉的“状态空间搜索”问题的例子是GPS导航：一个人在某个位置，需要找到通往另一个位置的路径。类似的问题也出现在许多电脑游戏中，当一个代理需要在游戏地图中找到从一个地方到另一个地方的路径时。像魔方这样的谜题是另一个例子。在这里，谜题的不同排列类似于地图上的位置，改变谜题排列的移动类似于连接地图上位置的路段。目标是相同的——找到一条路径（移动序列），将谜题从最初的排列改变为特定的期望排列。现实世界中有许多重要的问题可以归结为状态空间搜索问题。例子包括物流问题，如包裹提取和交付路线，以及制造问题，如找到最便宜或最快的制造或组装给定产品的方法，给定制造工厂中可用的机器。

The most familiar example of a "state space search" problem is GPS navigation: a person is at some location and needs to find a path to a different location. A similar problem occurs in many computer games, when an agent needs to find a path from one place to another in the game map. Puzzles, like Rubik's Cube, are another example. Here the different arrangements of the puzzle are analogous to the locations in a map and the moves that change the puzzle's arrangement are analogous to the road segments that connect locations in a map. The objective is the same - to find a path (sequence of moves) that changes the puzzle from its initial arrangement to a specific desired arrangement. There are many important real-world problems that can be cast as state space search problems. Examples include logistics problems, such as parcel pickup and delivery routing, and manufacturing problems, such as finding the least expensive, or fastest, way to manufacture or assemble a given product, given the machines available in the manufacturing plant.