Search Problem
一些基本概念
Agent
一个实体，可以获取环境信息，以及做出基于环境的行动
state
大概就是字面意思，状态
initial state 即初始状态
actions
基于当前状态的一些选择
Actions(state) transition model
用于描述 action 后的状态结果
Result(state,action) state space
包含所有可能状态的集合
goal test
用于检测是否达到目标状态的一种方法
path cost
每个给定路径的数字成本
通常都想要 cost 尽量小
solution
能够让初始状态变为目标状态的一系列动作
optimal solution
最优的解决方案，cost 最低
Solving Search Problem
node
一种数据结构，可以用于记录状态、父节点、动作、路径成本
策略
基本策略
- 初始化 frontier：起始时，frontier 仅包含初始状态（搜索树的根）。
- 迭代搜索：
如果 frontier 为空，则说明没有找到目标状态，返回“无解”。
取出 frontier 中的一个节点进行处理。
如果该节点是目标状态，则返回解答。
否则，扩展该节点的子节点，并将它们加入 frontier，继续搜索。
这里的 frontier 可以理解为“搜索边界”
优化策略
1. 初始化：
• frontier 仅包含初始状态。
• explored set 为空。
2. 迭代搜索：
• 如果 frontier 为空，则说明没有找到目标状态，返回“无解”。
• 取出 frontier 中的一个节点进行处理。
• 如果该节点是目标状态，则返回解答。
• 否则，将该节点加入 explored set。
• 扩展该节点的子节点：
• 仅当子节点不在 frontier 和 explored set 里时，才加入 frontier。
Stack
由于这里的策略，我们选择 stack（堆栈）这种数据结构
它的特点是 LIFO，先进后出
搜索方法
DFS 深度优先
刚刚给的优化策略其实就是 DFS，采用 Stack，先进后出
也就是先把一条路上搜索完，才换到另一条路
BFS 广度优先
queue
这里采用队列，特点是 FIFO，先进先出
这里是先把一个 node 上所有可能的下一个 node 搜完，才继续到下一层 node
Greedy Best First Search （贪心）
这是已知信息的搜索，上面的 dfs 与 bfs 都是未知信息的搜索
贪心算法会优先想（它认为）最接近目标的节点扩展，通过启发式函数估计
heuristic(n)然而，由于 h 函数无法做到完美地评估，总会有一种情况让贪心因为仅仅关注眼前利益而选择了错误的路线
A* Search
A*在贪心的基础上，引入了
g(n) 代表达到某个节点的 cost这里通过计算
h(n)+ g(n) 来评价是否是最低的成本最优条件
1. 可采纳性（Admissibility）：
• 启发式函数 h(n) 永远不会高估从节点 n 到目标节点的实际代价。
• 形式化定义：
其中 h^(n) 是从 n 到目标的真实最优代价。
• 直观理解：
• 如果启发式函数高估了代价，A* 可能会走错误的路径，导致搜索不到最优解。
• 例如，在地图路径搜索中，如果启发式函数是欧几里得距离，它不会高估实际路径长度，因此是可采纳的。
2. 一致性（Consistency）/ 单调性（Monotonicity）：
• 对于所有节点 n 及其后继节点 n^{\prime} （假设从 n 到 n^{\prime} 的步长代价为 c ），应满足：
• 直观理解：
• 一致性确保了 A* 在扩展某个节点 n 后，不会导致估计代价比实际代价更小，从而避免了回溯和不必要的重新计算。
Adversarial Search 对抗式搜索
Minimax
这里给出了一种新的方法，用于井字棋这个游戏（具体名字我忘了），但是我感觉和 adversarial 的思想很像，或者就是接着上面讲的
基本组成
- S₀: Initial state (in our case, an empty 3X3 board)
- Players(s): a function that, given a state s, returns which player’s turn it is (X or O).
- Actions(s): a function that, given a state s, return all the legal moves in this state (what spots are free on the board).
- Result(s, a): a function that, given a state s and action a, returns a new state. This is the board that resulted from performing the action a on state s (making a move in the game).
- Terminal(s): a function that, given a state s, checks whether this is the last step in the game, i.e. if someone won or there is a tie. Returns True if the game has ended, False otherwise.
- Utility(s): a function that, given a terminal state s, returns the utility value of the state: -1, 0, or 1.
伪代码
这里就是 min 方和 max 方相互博弈，选择对自己最优的那个 state，做出相应的 action
max 希望自己的 score 最大化，min 希望对方的 score 最小化
如，对于 max，可以用以下的tree 来表示
Alpha-beta pruning （Alpha-beta 剪枝）
这里对于minimax 做了一些优化，减少了一些不必要的计算，和 tree 这个说法相符合，叫做剪枝 prune
大概就是先遍历完一个 branch，在下一个 branch 中，如果一旦有 小于等于 / 大于等于 上一个 node 的 leaf，就停止计算和搜索，换到下一个 branch
因为由于 min 和 max 的设定，接下来的 leaf 即使算出来了也用不上
Depth-limited Minimax
由于对于复杂的情况，计算和存储量太大了，这里便对层数做一个限制
