文章目录
  1. 回溯算法
  2. 收费公路重建

回溯算法

对于一些问题，每一步均存在许多的尝试，并没有一种确定的解决方案，即未到最后一步之前，并不知道所做选择是否可行。

这时，有一种处理的算法是每一步先作出当前的可行选择，然后进入下一步，下一步同理；若直到最后一步依然可行，则得到一个解决方案；

否则，即在一连串的选择下到达某一步后没有可做的选择，于是撤销上一步的选择并尝试上一步其他的选择，这一过程即回溯；

回溯算法的基本框架就是尝试选择并在无解后回溯直到找到可行方案或在尝试了所有方案之后无解。

收费公路重建

X轴上N个点组成的集合$V=\{v_{1}, …, v_{N}\}$，其中每对点的距离组成的集合$D=\{|u-v||u,v\in V \ \textrm{and}\ u\neq v\}$；由$V$显然是很容易得到$D$的，而由$D$却不容易重建出$V$。

不妨设D中元素已排序，V中最小元素置于0处；显然，可置$v_{N}$于$\textrm{max}(D)$处，以及$v_{N-1}$于$\textrm{max}(D-\{v_{N}\})$，并从D中移除$v_{N}, v_{N-1}, v_{N}-v_{N-1}$；

进入循环：依然取D中的最大值d，当前未确定点有两种可选位置：d与$v_{N}-d$；

  • 若选择的位置与所有已确定点的距离都在D中(从D中移除这些距离)，则考虑下一个未确定点的位置；
  • 否则，若还有其他位置可选择，选择另一位置，再考察选择的位置与所有已确定点的距离是否都在D中，若是，从D中移除这些距离，并考虑下一个未确定点的位置；
  • 否则，只能回溯；撤销上一步的选择并尝试上一步其他的选择；

直到D为空表明找到一个可行解；或者尝试所有选择之后无解退出。