Backtracking¶
Turnpike Problem¶
给定一组点的两两间的距离
- 将距离
排序,最大的距离为 。 - 确定第一个点的位置为 0,则最远的点的位置为
。 - 从大到小选取距离
,只能放在 和 处,进行搜索。若新的点和已经确定的点的距离不在距离集合内,则剪枝。
Minimax Strategy¶
在类似下棋的搜索中,使用 Minimax 策略,最大化自己的利益,同时最小化对手的利益。
α-β Pruning¶
每个节点维护
在搜索过程中,如果继续搜索对当前节点没有意义,可以进行剪枝。