在本章中，我们将看到关于状态空间的信息是如何能够防止算法在黑暗中跌跌撞撞的。
1.有信息的搜索策略
我们要考虑的通用算法叫做“最佳优先搜索”（名字古老而不太准确）。它一般是将TREE-SEARCH和GRAPTH-SEARCH结合起来，它要扩展的节点是基于评价函数f（n）来决定的。
注意：评价函数有时不能真正的评价优劣，这将将搜索引入歧途。
BEST-FIRST-SEARCH算法有一整个家族，其中不同的方法是使用不同的评价函数，这些算法的一个关键点为启发函数（heuristic function），标记为h（n）：
h（n）=从节点n到目标节点的最低耗散路径的耗散值。
1.1贪婪最佳优先搜索
贪婪最佳优先搜索，从名字可以知道贪婪算法的思想。每次搜索扩展节点的时候，试图扩展离目标节点最近的节点，因此它只用启发函数f（n）=h（n）来评价节点。
例子：寻路问题--在一个国家中寻找由城市A到城市B最近的路线。当然，你有一副地图。路线结果为从A城市到B城市所要经过的城市的顺序列表。小路神马就不考虑了。
贪婪最佳优先搜索首先会列出从A出发能直接到达的所有城市， 并计算每一个能直接到达的城市距离和B的距离，然后选择最近的那个城市作为从A出发所到达的第一个城市，然后依次类推，直至到达城市B。
该搜索方法很简单，简单到明显有很多缺点：不能保证最优，不具有完备性，如果不注意重复可能会出现震荡的情况……但它毕竟让我们迈出了第一步，坏的东西总比没有的好。
1.2A*搜索：最小化总的估计解耗散
它把到达节点的耗散g（n）和从该节点到目标节点的耗散h（n）结合起来进行评价。
f(n) = g(n) + h(n)
该搜索算法很合理、很优秀。以至于我不知道该怎么摘录《人工智能：一种现代方法》中的文字、或者利用自己的问题来形容。具体分析请见《人工智能：一种现代方法》中内容。
1.3储存限制的启发式搜索
A*算法减少储存/空间复杂度的办法就是把迭代深入的思想用在启发式搜索上。我们称之为迭代深入A*算法或者IDA*算法。IDA*算法和典型的迭代深入算法最主要的区别就是，所用的截断值不是搜索深度，而是耗散值f = g + h。IDA*对很多单位耗散问题都适用，但在实数耗散值的时候会出现困难（具体见《人工智能：一种现代方法》习题3.11）。以下考虑两种储存限制搜索算法，RBFS和MA*。
function RECRSIVE-BEST-FIRST-SEARCH(problem) returns a solution, or failure
RBFS(problem,MAKE-NODE(INITIAL-STATE[problem])，∞)
function RBFS(problem,node,f_limit) returns a solution, or failure and a new f_cost limit
if GOAL-TEST[problem](state) then return node
successors <--- EXPAND(node,problem)
if successors is empty then return failure,∞
for each s in successors do
f[s] <--- max(g(s)+f(s),f[node])
repeat
best <--- the lowest f-value node in successors
if f[best] > f_limit then return failure, f[best]
alternative <--- the second lowest f-value among successors
result, f[best] <--- RBFS(problem,best,min(f_limit,alternative))
if result ≠failure then return resultRBFS的特点可以说是“一步一回头”，它会通过“alternative <--- the second lowest f-value among successors”来记录与当前节点相平行层次的次优节点值，当向下搜索，当前最优点的后继的评价函数值大于次优解时，放弃当前最优解，转而向次优解。但上述代码有一点问题，应该在最后“if result ≠failure then return result”之后加上“best <--- alternative, remove the lowest f-value node in successors”。将舍弃的最优解从successors中删除，repeat才有意义，否则repeat会重复循环而失去了筛选最优解的意义。
IDA*和RBFS的优点是空间复杂度底，缺点是……太低了……IDA*只保留一个数字：当前的f耗散值。RBFS保留的多一些。为了充分利用内存，由此改进出了两个算法，MA*（储存限制A*）和SMA*（简化MA*）。SMA*和A*一样会扩展最佳节点，直至内存放满为止，但当内存放满之后，它会像RBFS一样遗忘一个最差的节点，并将它备份到父节点。当其他所有路径比被遗忘的节点都差的时候，SMA*才会利用那个节点重新生成子树。具体算法略（原书中也省略了，比较复杂，原文是“完整的算法在这里浮现太复杂了！”）。
2.启发函数
如何设计一个启发函数？
首先设计一个松弛问题，即降低了限制的问题。然后设计该松弛问题的最优解。该最优解的耗散值，是一个可采纳的启发函数。当设计了多个启发函数时，可以采用如下公式：
h(n) = max{h1(n),h2(n),...,hm(n)}
可采纳的启发式也可以通过给定问题的子问题的最优解的耗散得到。模式数据库就是储存每个可能的子问题的实例的精确耗散。这样，每个搜索的开销就分摊到了每个子问题上。这里也可以采取上述最大值原则。
总结：设计启发函数方法有松弛问题法和子问题法（不限于这两种），综合启发函数的方法有最大值法和平均数法（不限于这两种）。
3.超越经典搜索算法
3.1 局部搜索和最优化问题
在搜索问题中，如果到目标的路径无关紧要，那么将引出不关心路径的算法。局部搜索算法从单独的一个当前状态（而不是多条路径）出发，通常只移动到与之相邻的状态。典型情况下，搜索的路径是不保留的，虽然局部搜索算法不是最优化的，但是它有两个关键的优点：（1）只用很少的内存，通常是一个常数。它们经常能够在不适合或者不能用系统化算法的很大的或者无限的状态空间中找到合理的解。除了找到目标，局部搜索算法对于解决纯粹的最优化问题很有用，其目标是根据一个目标函数找到最佳的状态。
3.1.1爬山法搜索
function HILL-CLIMBING(problem) returns a state that is local maximum
inputs:problem, a problem
local variables:current, a node
neighbor,a node
current <--- MAKE-NODE(INITIAL-STATE[problem])
loop do
neighbor <--- a higest-valued successor of current
if VALUE[neighbor] =< VALUE(current) then return STATE[current]
current <--- neighbor爬山搜索算法，节点的后继中，如果存在目标函数的值大于当前节点的，移动到该后继节点，如此循环。最终会返回一个局部最大值。该搜索算法的最大缺点是：局部最大值不一定是全局最大值。
3.1.2模拟退火算法
function SIMULATED-ANNEALING(problem,schedule) returns a solution state
inputs:problem, a problem
schedule, a mapping from time to "temperature"
local variables:current, a node
next, a node
T, a "temperature" controlling the probability of downward steps
current <--- MAKE-NODE(INITISL-STATE[problem])
for t <--- 1 to ∞ do
T <--- schedule[t]
if T = 0 then return current
next <--- a random selected successor of current
ΔE <--- VALUE[next] - VALUE[current]
if ΔE > 0 then current <--- next
else current <--- next only with probability e^(ΔE/T)
模拟退火算法和爬山搜索算法很像，不同之处在于（1）模拟退火算法的后继是随机选取的，而爬山算法是选择目标函数最大且大于当前目标节点值的。（2）模拟退火算法最终的返回的时刻由函数schedule[t]来决定，而不是由后继达到某种状态来决定的。（3）当后继的目标函数值大于当前节点的目标函数值时，两者都会将节点移动到后继，但当后继的值小于当前节点时，模拟退火算法按照一定的概率（e^(ΔE/T)）来确定是否将节点移动到后继节点。
3.1.3局部剪枝搜索
局部剪枝搜索记录k个状态，而不是一个状态。局部剪枝搜索由k个随机的生成的状态开始，每一个步都生成k个状态的所有后继，如果其中有一个是目标状态，那么搜索就停止，否则从所有生成的后继中选择k个最佳的后继，如此重复。
注意：它和爬山算法很类似的一点就是，很容易将某一个一步较差的节点剪枝，即使这个节点的后继表现很好。如果一个状态的后继很好，而其他k-1个状态的后继都不好，那么所有的机会就都集中到了这个节点后面，那么搜索就变得单一没有多样性。这和重新开始k次随机搜索是不同的，局部剪枝搜索中信息在这k个并的搜索之间传递。这个算法的一个改进是随机剪枝搜索。
3.1.4遗传算法
function GENETIC-ALGORITHM( population, FITNESS-FN) returns an individual
inputs: population, a set of individuals
FITNESS-FN, a function that measures the fitness of an individual
repeat
new_population <--- empty set
for a <--- 1 to SIZE(popuitition) do
x RANDOM-SELECTION(populatio, FITNIESS-FN)
y RANDOM-SELECTION(popuLtion, FITNEss-FN)
child <--- REPRODUCE(x, y)
if (small random probability) then child <--- MUTATE( child)
add child to new_population
population <--- new_population
until some individual is fit enough, or enough time has elapsed
return the best individual in population, according to FITNESS-FN
-------------------------------------------------------------------------------------
function REPRODUCE(x, y) returns an individual
inputs: x,y, parent individuals
n <--- LENCTII(x)
c <--- random number from 1 to n
return APPEND(SUBSTRING(x, 1, c),SUBSTRING(y, c + 1, n))
3.2连续空间的局部搜索
（1）微分方程
（2）离散化
3.3非确定动作搜索
对非确定动作，通过构造与-或树来描述。以一个自动除尘器对含有多个房间的屋子进行打扫为例。该屋子中所有房间之间都是相邻的，以九宫格排布，除尘器在房屋之间可以相互自由移动。除尘器可以以LEFT、RIGHT、UP、DOWN来行动。它可以执行SUCK来除尘。在某个房间里执行SUCK时，如果房间里有灰尘，SUCK动作将清除所有灰尘，偶尔还有可能将相邻放假的灰尘一并清除；如果房间里没有灰尘，那么它有时候会在房间里释放一些灰尘。
我们使用与-或树来描述整个可能的清理过程。
在房间里执行动作时，只是选择一个动作，动作之间是互斥的，我们将搜索时只用考虑一个后继的节点成为或节点；当执行一个动作时，可能会有两种情况，我们在搜索时必须同时考虑两种情况，我们将这种节点称为与节点。具体参见《artificial intelligence a modern approach V3》page135。与节点域或节点组成搜索树，称之为与-或树。
与-或树的一个搜索算法如下
function AND-OR-GRAM-SEARCH(problem) returns a conditional plan, or failure
OR-SEARCH(problem.INITIAL-STATE, problem,[ ])
function OR-SEARCH(state, problem, path) returns a conditional plan., or failure
if problem.GOAL-TEST(state) then return the empty plan
if state is on path then return failure
for each action in problem.ACTIONS(state) do
plan <--- AND-SEARCH(RESULTS(state, action), problem, [state | path])
if plan ≠ failure then return [action | plan]
return failure
function AND-SEARCH(states, problem, path) returns a conditional plan, or failure
for each s_i in states do
plan_i <--- OR-SEARCH(s_i, problem, path)
if plan_i = failure then return failure
return [if s_1 then plan_1, else if s_2 then plan_2, else ... if s_n-1 then plan_n-1, else plan_n]
3.4部分观测
解决部分观测的关键概念在于置信状态，它是在给出动作序列和到目前为止的感知情况下，表征智能体对其所处物理状态的信度。置信状态通俗的说，就是智能体所有可能的物理的状态的集合。
3.4.1无观测的搜索
和常识相反，无观测搜索大多数情况下是可解的，而且具有重要的实际意义。首先是不依赖传感器，当传感器发生故障的时候，这是相当重要的。第二是传感器成本太高或者无法使用传感器的情况。
为了解决无观测问题，我们在置信状态空间中搜索，而不是在物理状态空间中搜索。需要注意的是，在置信状态空间中，是完全可观测的，因为智能体知道它处于哪一个置信状态。而且结构也只是一个动作序列，因为没有感知，所以没有和前面使用与-非树时一样的通过输入改变动作的部分了。
假定潜在的物理问题P可以通过以下定义：ACTIONp,RESULTp,GOAL-TESTp,STEP-COSTp。那么我们可以通过按照如下所述来定义相应的无感知问题：
对确定性动作：b' = RESULT(b,a) = {s':s'= RESULTp(s,a) and s∈b}
其中b'是转移之后的置信状态，b为转移之前的置信状态，a为转移发生的动作。
生成新的置信空间的过程称为预测：b' = PREDICTp(b,a)
对非确定性动作：
通过置信状态来搜索无疑仍旧是一个笨办法……稍稍的改进搜索是，首先假定一个状态为初始状态，然后搜索出一个可行方案，将方案应用到另一个状态为初始状态的环境下，如果方案能够成立，则应用于第三个状态为初始状态的环境下，否则返回原点重新寻找一个方案，直至找到一个能够满足所有初始状态的方案。
3.4.2有观测的搜索
在有观测的搜索当中，ACTIONS、STEP-COST和GOAL-TEST同无观测搜索一致，转移模型Transition Model则稍显复杂。我们将在特定动作下由一个置信状态到下一个置信状态的转移划分为三个阶段。
b'' = UPDATE(b',o) = {s : o=PERCEPT(s) and s∈b'}
将这三步合起来就是：
3.5在线搜索智能体和未知环境
到目前为止，我们一直在使用离线搜索算法，它在涉足真实世界之前先计算出解决方案，之后执行。与之相反，在线搜索智能体计算与行动交错进行。首先它采取一个行动，然后再观测，通过观测值再计算出下一步行动动作。在线搜索对未知环境问题至关重要，同时对常规问题也很重要，它可以使智能体的计算集中于已经发生的事情上，而不是可能发生但最终没有发生的事情上。当环境未知时，智能体面临探索问题。
3.5.1在线搜索问题
在线搜索问题是必须通过执行动作来完成的，而不能仅仅通过计算得到答案。我们假定一个确定并且完全可观测的环境。但是智能体只能知道如下信息：
注意：智能体不能决定RESULT（s，a），除非它处于s状态且执行了a动作，它才能知道结果。
最后，智能体肯那个拥有一个启发函数h（s），用于评估从当前状态到目标状态的距离。我们把在线搜索的路径耗散和如果已知环境寻找到路径的耗散的比值称为竞争比。当搜索路径中有“死胡同”时，竞争比为无穷大。为简单起见，我们假设搜索空间是安全搜索的，也就是说没有“死胡同”。
3.5.2在线搜索智能体
function ONLINE-DFS-AGENT(s�) returns an action
inputs: s', a percept that identifies the current state
persistent: result , a table indexed by state and action, initially empty
untried, a table that lists, for each state, the actions not yet tried
unbacktracked, a table that lists, for each state, the backtracks not yet tried
s, a, the previous state and action, initially null
if GOAL-TEST(s'�) then return stop
if s'� is a new state (not in untried) then untried[s�]←ACTIONS(s�)
if s is not null then
result [s, a]←s�'
add s to the front of unbacktracked[s'�]
if untried[s�'] is empty then
if unbacktracked[s�] is empty then return stop
else a←an action b such that result [s�, b] = POP(unbacktracked[s�])
else a←POP(untried[s�])
s ←s�'
return a
以上为使用深度优先搜索策略的在线搜索算法。
3.5.3在线局部搜索
深度优先策略能够应用于在线搜索，是因为其展开节点策略的局部性，不必回溯去展开所有的状态的后继节点以便搜索。与此类似，爬山算法也有着良好的局部性。事实上，由于爬山算法保存了当前状态值，它已经是一个在线搜索算法了。但最简单的爬山算法并不适用于在线局部搜索。首先它会是智能体处于启发函数值最大或最小的地方，但不会到新的地方去，这样无法到达目的地。其次它随机开始的特性不适用于在线搜索，因为智能体不能让自己突然移动到任何位置。一下为一个改进后的使用爬山策略的在线局部搜索算法。
3.5.3学习
智能体起初对环境一无所知，但随着其对环境的探索，它会逐渐生成对环境的地图，这就是学习。在采用启发式的情况下，其记录每个位置的耗散，也是一种学习。
4.总结
本章主要讲解了以下内容。
