Backtracking

Turnpike Problem

给定一组点的两两间的距离 \(\{d_i\}\)，求这些点的位置。

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

Minimax Strategy

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

α-β Pruning

每个节点维护 \( \alpha \) 和 \( \beta \) 两个值，分别表示当前子树收益的上界和下界。

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