高级人工智能——搜索问题
序言搜索问题的构成：状态空间、后续函数、初始状态和目标测试。解是一个行动序列，将初始状态转换成目标状态。
状态空间状态空间包含了环境中的每一处细节。以吃豆子游戏为例：世界状态：
Agentpositions:120Foodcount:30Ghostpositions:12Agentfacing:NSEW状态数量：
世界状态：120×(230)×(212)×4120 imes(2^{30}) imes(2^{12}) imes4120×(230)×(212)×4状态空间图状态空间图是搜索问题的数学表示。状态空间图中，每个节点对应一个状态，每个状态只出现一次。几乎不在内存中构建完整的状态空间图（太大了），但它是非常有用的。
搜索树根节点对应了初始状态。子节点对应了父节点的后继。节点显示状态，但对应的是从初始状态到该状态的路径。对大多数问题，实际上不会构建整个树。
树搜索拓展出潜在的行动（节点）维护所考虑行动的边缘节点。对边缘节点进一步拓展得到下一步有可能的行动。
一般的树搜索伪代码：
图搜索为了应对图中所示算法检测重复状态、存在两个节点间循环等问题，图搜索应运而生。主要思想：不要扩展一个状态两次
执行：
树搜索+扩展过的状态集(“closedset”)扩展节点之前，检查确保它的状态在之前没有被扩展按节点扩展搜索树，但…如果不是新的状态，忽略；如果是新的，加入closed表如何评价搜索算法：
完备性：当问题有解时，保证能找到一个解最优性：保证能找到最优解时间复杂度空间复杂度所有的搜索算法都是相同的，除了对边缘的处理策略。搜索问题主要包括：无信息搜索、启发式搜索和局部搜索。
1.无信息搜索1.1深度优先搜索（Depth-FirstSearch）策略：DFS用一句话概括就是：“一直往下走，走不通回头，换条路再走，直到无路可走”。以上图为例：
1.从根节点S拓展出3个子节点：d、e和p2.d、e、f三个节点深度相同，首先拓展最左边的d节点，得到b、c、e三个节点3.同理拓展b节点得到a4.此时由于a节点已经无法再拓展且未实现搜索目标，转而对级次深的c节点进行拓展5.最终得到G节点深度优先搜索特性：
完备性：当深度无限时可能无法找到解，例如存在节点间循环最优性：不具备，它找到的解释“最靠左”的解时间复杂度：有可能遍历整个搜索树，也可能很快就找到解，如果搜索树是有限的，则O(b^m)空间复杂度：O(bm)1.2广度优先搜索（BFS)策略：BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索特性：
完备性：一定可以找到解最优性：时间复杂度：O(bd)O(b^d)O(bd)空间复杂度：O(bd)O(b^d)O(bd)深度优先搜索的空间复杂度低于广度优先，广度优先可以保证找到最浅层的解，保证了时间复杂度低于深度优先1.3迭代深入搜索（IteratuveDeepening)结合了DFS的空间优势和BFS的时间优势，对搜索的深度进行了限制，使得在搜索到限制深度后必须开始新的搜索路径。
1.4代价敏感搜索(Cost-SensitiveSearch)给路径设置代价，找到代价最低的路径。
1.5代价一致搜索(UniformCostSearch)参考博客：一致代价搜索（UCS）的原理和代码实现
代价一致搜索的缺点：
在每一个“方向”上进行探索没有关于目标信息1.6总结2.启发式搜索（有信息搜索）启发策略：估计一个状态到目标距离的函数问题给予算法的额外信息，为特定搜索问题而设计
2.1贪婪搜索(GreedySearch)2.2A*搜索判证明A树搜索的最优性？（这个容易出证明题）*参考博客：启发式搜索(InformedSearch)-贪婪算法GBS+A*算法
2.3启发式图搜索的一致性为什么在A*图搜索中强调了启发的一致性？
2.3.1A*图搜索该图可解释为什么A图搜索要强调一致性，A树搜索没有强调一致性。在此图中，由于没有强调启发函数的一致性，虽然h(A)≤actualcostfromAtoG，但是h(A)–h©＞cost(AtoC)，导致在实际搜索中，在经过B节点将C纳入边缘集合后，根据图搜索特性，当轮到A节点拓展时，由于此时C节点已经在closedset中，因而被忽略掉，此时找到的解并非最优解。
2.3.1A*图搜索的最优性Fact1:A算法扩展节点，f值单调增Fact2:对每个状态s,到达s最优的节点先于次优的节点扩展Result:A图搜索是最优的
2.4A*算法总结A*使用后向耗散和前向耗散（估计）A*是完备的、最优的，也是效率最优的（可采纳的/一致的启发函数）启发式函数设计是关键:常使用松弛问题3.局部搜索参考博客：局部搜索（爬山法+模拟退火+遗传算法）
树搜索在边缘集合中保留未探索的替代路径（确保完备性）。局部搜索：改进单一选项直到不能再改善为止新的后继函数：局部改变通常更快，内存使用更有效（但不完备、次优）