搜索算法实例应用综述优化策略案例场景农夫在过河问题中找到最优过河策略在国际象棋游戏中如何选择最优国际象棋策略罗马尼亚休假问题八数字问题扫地机器人求解方程极值地图着色(csp问题)
概要
检索算法实际上是根据初始条件和扩展规则构建“解树”，寻找符合目标状态的节点的过程。
将具体问题抽象为图论的模型——树，搜索算法使用的第一步是构建搜索树。
初始状态对应于根节点，目标状态对应于目标节点。 完成检索的过程是找到从根节点到目标节点的路径，找到最优解。
优化策略(1)减少节点数量，思想：尽量减少生成的节点数量
)自定义回溯边界。 思想：定制回溯边界条件，砍下无法得到最优解的子树
主要有盲目搜索、启发式搜索、游戏搜索
案例场景找出并解决农户过河问题中的最优过河策略：通过宽度搜索、形式化状态空间，以元组形式表达空间状态形式，通过加入限制条件，考查所有可行方案，从中找出最优解决方案。
优化：采用双向宽搜索，可以从目标状态出发，逆向搜索。
在国际象棋游戏中，如何选择和解决最佳国际象棋策略：游戏探索、深度、广度探索。 国际象棋对战游戏多为游戏搜索。 其中以零和游戏为主。 通过迭代搜索构建搜索树，得到结果。
优化：状态空间多，搜索树庞大。 通过剪枝算法去除不需要的扩展节点，减少迭代深度和计算幅度，同时采用更好的评估函数可以减少计算。
罗马尼亚假期问题解决：深度、广度搜索、启发式搜索。 各城市节点作为搜索树的一个状态节点，可以遍历整个搜索树得到结果，但时间空间复杂度太高。
优化：利用启发式搜索，可以通过xjj距离测量状态节点的好坏，从而在每一步得到尽可能最优的状态节点，并以最快的速度收敛到目标。
八数字问题解决：宽搜索、启发式搜索、csp算法。 最典型的是回溯算法，遍历构建整个搜索树，但时空开销较大，可以进行精细改进。
优化：进行剪枝，将整个棋盘表示为一个矩阵，标记每次放下皇后时棋盘上皇后可以攻击的位置，每次放下皇后时，检查剩下的行和列能否继续放下皇后，如果某行在皇后的攻击范围内，下一步通过增加判决函数，可以有效减少无效的搜索分支，提前判断棋盘的可配置位置。 提高算法的效率。
扫地机器人寻路(深度有限，扫地机器人属于人机交互类，现实世界中存在状态空间，具体表现为脏不脏，根据机器人的动作状态前后左右移动进行吸尘。 可进行深度有限的检索
求解方程极值的求解：群体智能搜索算法、粒子群、蚁群、遗传算法。 将方程的各解表示为一个个体。 由方程给出评价函数，通过迭代求得最优解。
地图着色(csp问题)解决：禁忌搜索、回溯搜索。 这种问题有很多制约条件，具体表现为图像块和块之间的颜色制约，问题有很多变数，应对有很多值域。 可以通过限制状态，或者追溯到状态矛盾之后来解决。