High-Performance Domain-Independent Heuristic Search

高性能领域独立启发式搜索

• 批准号: 46246-2012
• 负责人: Holte, Robert
• 金额: $ 3.06万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=521739
• 关键词: 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.

“状态空间搜索”问题最常见的例子是GPS导航：一个人在某个位置，需要找到一条通往不同位置的路径。当代理需要在游戏地图中找到从一个地方到另一个地方的路径时，许多电脑游戏中都会出现类似的问题。魔方等拼图游戏就是另一个例子。在这里，拼图的不同排列类似于地图中的位置，而改变拼图排列的移动类似于连接地图中各个位置的路段。目标是相同的-找到一条路径(移动序列)，将拼图从最初的排列改变为特定的所需排列。有许多重要的现实问题可以归结为状态空间搜索问题。例如，物流问题，如包裹提货和递送路线，以及制造问题，如在制造工厂可用机器的情况下，找到最便宜或最快的方法来制造或组装给定的产品。