3heuristic-search.4.pdf

人工智能英文PPT第3章 Heuristic Search 启发式搜索 启发式搜索就是带有信息的搜索 Heuristic or informed search exploits additional knowledge about the problem that helps direct search to more promising paths. •A heuristic function, h(n), provides an estimate of the cost of the path from a given node to the closest goal state. Must be zero if node represents a goal state. -Example: Straight-line distance from current location to the goal location in a road navigation problem. •Many search problems are NP-complete so in the worst case still have exponential time complexity; however a good heuristic can: