# 搜索算法

# 1. 提出问题

# 1. 起点和终点

是我们状态空间的初始状态(s0)和目标(goal)

# 2. 动作

在状态s0时，也就是 ARAD，可以有三条路作为选择，即当前状态下可行的动作有三个{a1,a2,a3...}

# 3. 边界

边界是我们当前已经探索到的最远的端点

# 4. 已探索区域

不包括边界的，所有已经探索过的状态

# 5. 未探索区域

未探索区域里面包含了目标

# 6. 单步开销

从一个状态s经过动作 a，转移到s' 所需要的开销

# 7. 路径总开销

# 2. 搜索算法

# 1. 搜索算法族

符号表

伪代码

Tree.Search(problem p ) return path
frontier = {path(p.init)}
loop:
    #如果边界集中已无状态
    if frontier is empty : return fail
    # 挑选边界集中的元素
    path = remove.choice(frontier)
    #移动到该路径的终点（新状态）
    s = path.end
    #检查新状态是否是终点
    if goal test (s): return path
    #如果没到终点，对于当前状态下的每一个可行动作
    for a in p.Actions(s):
        #把下一个状态添加到边界集中
        add [path + a >Result(s,a)]
        to frontier 

# 2. 选路算法

在上面的伪代码中，关键步骤是选路的方法 remove.choice(frontier) 如何进行选路决定了算法的走向

首先，将状态 s0（Arad）先从边缘中移除，并且基于状态 s0，找到可行的动作{a1,a2,a3}，也就是三条路径，并将其终点（Result(s0,an)）加入到边缘集中。

arad----zerind
arad----sibiu
arad---timisoara

这三条路实际上是等价的，也就是只需要一步，假设我们随机选一条路，到 sibiu

此时状态转移到 sibiu，接下来的关键步骤即扩展我们的探索集，也就是按照如下算法，添加新的路径到边界集中

 for a in p.Actions(s):
    #把下一个状态添加到边界集中
    add [path + a >Result(s,a)]
    to frontier 

首先要考虑的一点是 p.Action(s)到底是哪些？

这个问题进行一些转换可以变为：假设我们站在 sibiu ，可以有几条路来选？

答案是四条：

sibiu ---- arad
sibiu ---- fagaras
sibiu ---- rimnicu vilcea
sibiu ---- oradea

但是我们需要考虑到老路径：add [path + a >Result(s,a)] (即我们是如何到达该状态的动作也要包含)

因此实际路径就是

arad ---- sibiu ---- arad
arad ---- sibiu ---- fagaras
arad ---- sibiu ---- rimnicu vilcea
sibiu ---- oradea

如下图，树搜索其实就是在空间中不断叠加树状结构，因此难以避免重复

# 3. 图搜索

为了避免重复，我们必须要记录已经探索过的路径

将树状结构按层级，分成已探索,边缘,未探索三个集合。

function Graph.Search(problem ) :
frontier = {[initial]};explored={}
loop:
    #如果边界集中已无状态
    if frontier is empty : return fail
    # 挑选边界集中的元素
    path = remove.choice(frontier)
    #移动到该路径的终点（新状态）
    s = path.end; add s to explored
    #检查新状态是否是终点
    if s is a goal:return path
    #如果没到终点，对于当前状态下的每一个可行动作
    for a in actions:
        #把下一个状态添加到边界集中
        add [path + a ->Result(s,a)]
        to frontier 
        Unless Result(s,a) in frontier or explored

如果利用的是图搜索，去掉重复路径，当前有如下路径可供选择

arad---- zerind (checked)
arad---- sibiu  (checked)
arad ---- sibiu ---- fagaras
arad ---- sibiu ---- rimnicu vilcea
arad ---- sibiu ---- oradea
arad ---- timisoara --- lugoj 

然后选择哪一点呢？

由于是宽度优先，所以选择最短路径，arad---- zerind 或者arad---- timisoara都可以

假设选择到 zerind

接下来如何选择？

在状态 zerind 时，action 有两个

zerind --- oradea （无法添加，因为 oradea已经属于 frontier）
zerind --- arad （无法添加，因为 arad 已经属于 explored）

所以当前路径为

arad---- zerind (checked)
arad---- sibiu  (checked)
arad ---- sibiu ---- fagaras
arad ---- sibiu ---- rimnicu vilcea
arad ---- sibiu ---- oradea
arad ---- timisoara --- lugoj 

接下来如何选择？

arad---- zerind (checked)
arad---- sibiu  (checked)
arad ---- sibiu ---- fagaras
arad ---- sibiu ---- rimnicu vilcea
arad ---- sibiu ---- oradea
arad ---- timisoara --- lugoj 

此时最短路径为arad---- timisoara

当处于状态timisoara时，action 有一个（到 timisoara）

timisoara --- lugoj 

将其加入路径表

arad---- zerind (checked)
arad---- sibiu  (checked)
arad---- timisoara  (checked)

arad ---- sibiu ---- fagaras
arad ---- sibiu ---- rimnicu vilcea
arad ---- sibiu ---- oradea
arad ---- timisoara --- lugoj 

至此，我们还有3条 cost 为2 的路径可以探索

移动到 fagaras 之后，action 有

fagaras --- sibiu （无法添加，因为 sibiu已经属于 explored）
fagaras --- bucharest

此时虽然看上去已经到终点了，但实际上不是。 一个节点只有在 remove的时候才会去进行检测，加入 frontier 时不会。除非我们有一些假设：

1. 我们使用宽度优先算法
2. 没有cost为2.5的路径

此时我们可以在加入时就进行检测，但是如果我们期望获得真实长度最短的路径，此时的结果可能不是最佳的。

# 4. 最小耗散优先算法

目的：找到总耗散最小的路径

开始时仍然是3个 action

arad---- zerind (75)
arad---- sibiu  (140)
arad---- timisoara  (118)

选择 cost 最小的路径，我们移动到 zerind

arad---- zerind (75)---oradea (71+75=146)
arad---- sibiu  (140)
arad---- timisoara  (118)

arad---- zerind (75)---oradea (71+75=146)
arad---- sibiu  (140)
arad---- timisoara  (118)

选择 cost 最小的路径，我们移动到 timisoara

arad---- zerind (75)---oradea (71+75=146)
arad---- sibiu  (140)
arad---- timisoara  (118) --lugoj(118+111=229)

选择最短路径，到达 sibiu，添加 action

arad---- zerind (75)---oradea (71+75=146)
arad---- sibiu  (140)(checked)
arad---- sibiu  (140)---fagaras(140+99=239)
arad---- sibiu  (140)---rimnicu vilcea(140+80=220)
arad---- timisoara  (118) --lugoj(118+111=229)

选择最短路径，到达 oradea，没有可添加的 action

arad---- zerind (75)---oradea (71+75=146)(checked)
arad---- sibiu  (140)(checked)
arad---- sibiu  (140)---fagaras(140+99=239)
arad---- sibiu  (140)---rimnicu vilcea(140+80=220)
arad---- timisoara  (118) --lugoj(118+111=229)

选择最短路径，到达 rimnicu vilcea，没有可添加的 action

arad---- zerind (75)---oradea (71+75=146)(checked)
arad---- sibiu  (140)(checked)
arad---- sibiu  (140)---fagaras(140+99=239)
arad---- sibiu  (140)---rimnicu vilcea(140+80=220)(checked)
arad---- timisoara  (118) --lugoj(118+111=229)

选择最短路径，到达 rimnicu vilcea，添加 action

arad---- zerind (75)---oradea (146)(checked)
arad---- sibiu  (140)(checked)
arad---- sibiu  (140)---fagaras(140+99=239)
arad---- sibiu  (140)---rimnicu vilcea(220)(checked)
arad---- timisoara  (118) --lugoj(118+111=229)
arad---- sibiu  (140)---rimnicu vilcea(220)---pitesti(220+97=317)
arad---- sibiu  (140)---rimnicu vilcea(220)---craiova(220+146=366)

选择最短路径，到达 lugoj，添加 action

arad---- zerind (75)---oradea (146)(checked)
arad---- sibiu  (140)(checked)
arad---- sibiu  (140)---fagaras(140+99=239)
arad---- sibiu  (140)---rimnicu vilcea(220)(checked)
arad---- timisoara  (118) --lugoj(229)(checked)
arad---- sibiu  (140)---rimnicu vilcea(220)---pitesti(220+97=317)
arad---- sibiu  (140)---rimnicu vilcea(220)---craiova(220+146=366)
arad---- timisoara  (118) --lugoj(229)---mehadia(299)

选择最短路径，到达 lugoj，添加 action

arad---- zerind (75)---oradea (146)(checked)
arad---- sibiu  (140)(checked)
arad---- sibiu  (140)---fagaras(239)(checked)
arad---- sibiu  (140)---rimnicu vilcea(220)(checked)
arad---- timisoara  (118) --lugoj(229)(checked)
arad---- sibiu  (140)---rimnicu vilcea(220)---pitesti(220+97=317)
arad---- sibiu  (140)---rimnicu vilcea(220)---craiova(220+146=366)
arad---- timisoara  (118) --lugoj(229)---mehadia(299)
arad---- sibiu  (140)---fagaras(239)---bucharest(239+211=450)

虽然终点已经被添加到了边缘集，但是搜索仍然需要继续。

选择最短路径，到达 mehadia，添加 action

arad---- zerind (75)---oradea (146)(checked)
arad---- sibiu  (140)(checked)
arad---- sibiu  (140)---fagaras(239)(checked)
arad---- sibiu  (140)---rimnicu vilcea(220)(checked)
arad---- timisoara  (118) --lugoj(229)(checked)
arad---- timisoara  (118) --lugoj(229)---mehadia(299)(checked)
arad---- sibiu  (140)---rimnicu vilcea(220)---pitesti(220+97=317)
arad---- sibiu  (140)---rimnicu vilcea(220)---craiova(220+146=366)
arad---- sibiu  (140)---fagaras(239)---bucharest(239+211=450)
arad---- timisoara  (118) --lugoj(229)---mehadia(299)---drobeta(374)

选择最短路径，到达 pitesti，两个 action，到 craiova 的耗散更大所以放弃，到 buchares

最后我们得到了一条更短的路径

arad---- sibiu  (140)---rimnicu_vilcea(220)---pitesti(317)---bucharest(418)
arad---- sibiu  (140)---fagaras(239)---bucharest(450)

以此类推，我们还需要将其他边缘集中的节点也再检查一遍，此处不再赘述，因为没有更好的路径了。

# 5. 算法比较[^1]

注:是否最优，表示是否能够确保找到最短路径 注:是否完备，表示是否能够确保完成算法

虽然深度优先储存空间最小，但是如果考虑无穷大的场景，它可能会沿着一条边一直寻找，如果目标在其他边则永远无法找到。

# 6. 贪婪最佳搜索

优先考察里目标最近的路径

困局:当在起点和终点之间有障碍时，可能导致结果不是最佳的