搜索求解策略

盲目搜索和启发式搜索
- 所谓盲目搜索( blind search)是指在对特定问题不具有任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索，它能快速地调用一个操作算子。
- 所谓启发式搜索（ heuristic search）则是考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态，提高搜索效率。
- 盲目搜索中，由于没有可参考的信息，只要能匹配的操作算子都需运用，从而搜索出更多的状态，生成较大的状态空间显示图；
- 启发式搜索中，运用一些启发信息，只采用少量的操作算子，生成较小的状态空间显示图，就能搜索到一个解，但是每使用一个操作算子便需做更多的计算与判断。启发式搜索一般要优于盲目搜索，但不可过于追求更多的甚至完整的启发信息。

简单问题求解智能体算法

function SIMPLE PROBLEM SOLVING AGENT(percept) returns an action
	persistent: seq , an action sequence, initially empty
							state, some description of the current world state
							goal, a goal, initially null
							problem, a problem formulation
							action, the most recent action, initially none
	state ← UPDATE STATE state, percept
	if seq is empty then
		goal ← FORMULATE GOAL state
		problem ← FORMULATE PROBLEM state, goal
		seq ← SEARCH problem
		if seq = failure then return a null action
	action ← FIRST seq
	seq ← REST seq
	return action

人工智能领域中，搜索求解算法可以应用在海量数据的搜索、计算中，假设有以下一张公路图：

罗马尼亚部分公路图

解决最短路径问题

采用Graph Search

每个路径在每个阶段的前一步基础上加以扩展，在第三阶段时，最北部的Oradea已经陷入死循环。

采用Tree Search

function TREE-SEARCH(problem) returns a solution, or failure
	initialize the frontier using the initial state of problem
	loop do
		if the frontier is empty then return failure
		choose a leaf node and remove it from the frontier
		if the node contains a goal state then return the corresponding solution
		expand the chosen node, adding the resulting nodes to the frontier

该 frontier(亦称open list): 一种数据结构, 用于存储所有的叶节点。

在 frontier上扩展节点的过程持续进行, 直到找到一个解、或没有其它状态可扩展。

无信息搜索（盲目搜索）

无信息搜索称作盲目搜索，意味着该搜索策略没有超出问题定义的状态以外的附加信息。

做的事情就是生成后继结点，并且区分是目标状态还是非目标状态。

宽度优先搜索
深度优先搜索
一致代价搜索

回溯法

算法用三张表来保存状态空间中的不同性质结点：

路径状态( path states)表PS
保存当前搜索路径上的状态。如果找到了目的,PS就是解路径上的状态有
序集。
新的路径状态( new path states)表NPS
新的路径状态表。它包含了等待搜索的状态,其后裔状态还未被搜索到,即未被
生成扩展。
不可解状态( no solvable states)表NSS

回溯是状态空间搜索的一个基本算法。各种图搜索算法,包括深度优先、宽度优先、最好优先搜索等,都有回溯的思想
- 用新的路径状态表(NPS)使算法能返回(回溯)到其中任一状态。
- 用不可解状态表(NSS)来避免算法重新搜索无解的路径。
- 在路径状态表(PS)中记录当前搜索路径的状态,当满足目的时可以将它作为结果返回。
- 为避免陷入死循环必须对新生成的子状态进行检查，看它是否在该三张表中。
递归性质

一致代价搜索

策略：拓展最低代价的未拓展结点。
实现：队列，按路径代价排序，最低优先。

function UNIFORM-FIRST-SEARCH(problem)returns a solution, or failure
	node ← a node with STate=problem.INITIAL-STATE, PATH-TEST=0
	frontier ← a priority queue ordered by PATH-CoSt, with node as the only element
	explored ← an empty set
	loop do
		if EMPTY? (frontier) then return failure
		node ← POP(frontier) /*chooses the lowest-cost node in frontier */
		if problem.GOAL-TEST(node.STATE) then return solution(node)
		add node state to explored
	for each action in problem.Actions(node.State) do
		child ← child-NODE(problem, node, action)
		if child.State is not in explored or frontier then
			frontier INSerT(child, frontier)
		else if child.STAtE is in frontier with higher PaTH-Cost then
			replace that frontier node with child