High-Performance Domain-Independent Heuristic Search

点击翻译按钮获取中文摘要

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.