跳转至

Backtracking

Turnpike Problem

给定一组点的两两间的距离 {di},求这些点的位置。

  1. 将距离 {di} 排序,最大的距离为 dn
  2. 确定第一个点的位置为 0,则最远的点的位置为 dn
  3. 从大到小选取距离 di,只能放在 didndi 处,进行搜索。若新的点和已经确定的点的距离不在距离集合内,则剪枝。

Minimax Strategy

在类似下棋的搜索中,使用 Minimax 策略,最大化自己的利益,同时最小化对手的利益。

α-β Pruning

每个节点维护 αβ 两个值,分别表示当前子树收益的上界和下界。

在搜索过程中,如果继续搜索对当前节点没有意义,可以进行剪枝。