利用人工智能解决的一个重要问题就是搜索问题，此文陈述了如何将搜索问题进行合理化定义分析和搜索策略。
一、搜索问题
1、常见的搜索问题案例
（1）传道士和恶魔问题
（2）8问题
2、问题定义
通常而言，一个搜索问题要包含以下条件：
- 初始状态
- 一系列的行为，将状态转换为下一个状态
- 目标状态
- 行为损失函数
换而言之，搜索问题实际上就是行为引导的状态转换的问题，我们需要寻找的是状态转换的路径/整个状态转换的过程中的最小花费。
二、搜索策略
1、深度优先
2、广度优先
3、启发式搜索
A* search
https://blog.csdn.net/tjssehaige/article/details/8515755
4、极大极小搜索(Minimax search)
极大极小搜索是一种基于当前状态推测出对于我方最有利，对对方最不利的行动。
（1）算法思想
首先假设存在博弈双方，自身为max，对方为min。在一个决策树中对节点进行评估。
- 展开一个决策树，奇数层为max层，偶数层为min层。
- 对每一个终端（叶子）节点计算效用值
- 选取一个还未进行评估并且其子节点全被评估过的节点。如果没有这样的节点，评估结束。
- 如果选择的节点在min层，则选取其子节点的最小值作为自己的值；如果选择的节点在max层，则选取其子节点的最大值作为自己的值。返回第三步。
以上图为例：
- I = 0，J =7
- F = 5，G = 8
- B = 3， C = 4
所以最终A能得到最好的结果是4。
（2）改良
在决策树的深度很深的时候，决策的时间通常会特别的长。针对这个问题，需要对两个方面进行优化：
- 部分树搜索：对不需要搜索的部分进行剪枝
- 评估函数用启发评估函数代替效用函数
A、启发式评估函数
函数需要满足：
-
快速的函数计算时间
-
计算效果与效用函数一致
-
函数真正反映获胜的可能
在大多数情况下，使用线性模型来表示启发式评估函数：
f(x) = w1x1+w2x2+… + wnxn
其中x是决策的特征，w是该特征的权重。这些可以通过对先验知识进行学习获得
B、alpha-beta剪枝算法：
alpha-beta是一种剪枝生成partial search tree的算法，通过不计算某些子枝来增快计算速度。根据计算的顺序不同，分为left-to-right-alpha-beta和right-to-left-alpha-beta。
https://www.7forz.com/3211/
以从左向右为例：
- 赋予顶层节点初始alpha = - ∞ ， beta = + ∞
