Backtracking¶

Turnpike Problem¶

给定一组点的两两间的距离 ${d_{i}}$ ，求这些点的位置。

将距离 ${d_{i}}$ 排序，最大的距离为 $d_{n}$ 。
确定第一个点的位置为 0，则最远的点的位置为 $d_{n}$ 。
从大到小选取距离 $d_{i}$ ，只能放在 $d_{i}$ 和 $d_{n} - d_{i}$ 处，进行搜索。若新的点和已经确定的点的距离不在距离集合内，则剪枝。

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

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

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