论文部分内容阅读
摘 要：算法设计本是一个自由灵活的思维过程，但是，在算法设计过程中我们会发现，问题可以分类，同类问题的解决方法是类似的。于是，可以对处理类似问题的算法进行归纳，得到解决这一类问题的算法的模式，使用模式可以加快算法设计的过程，提高算法正确率。
关键词：回溯问题;三路模型;汉诺塔
一、 回溯问题与三路模型
回溯问题是常见的一类问题，这种问题的解有很多个，我们需要去发现它的所有的解或者是最优解。解决回溯问题的基本思路就是按一定路径尝试去搜索所有的解，在搜索过程中发现再往前不可能得到这个问题的解，则放弃这条路径并退回上一个步骤继续下一条路径的搜索。处理回溯问题的方法很多，比如递归法、堆栈法、计数法等。
三路模型是堆栈法的一种实现方式，但是将问题的求解过程进行了简化和规范，使问题的解决更加简单。三路模型将每一次处理过程归纳为三个操作，它们分别是入栈、出栈和检查栈顶的操作。操作过程如下图所示：
图1 三路模型示意图
每一次进入循环体之后，首先检查当前状态是否是需要的解，如果是需要的解，则输出结果。状态检查完毕之后就有三个路径可选。一是入栈，即再次加入新的信息，继续往前搜索解;二是出栈，即回溯，倒回到上一个步骤，另外寻找求解路径;三是修改栈顶，相当于先出栈再入栈。可以证明这三个操作是完备的，不会遗漏问题的解。在求解具体问题的时候，只需要思考什么情况下入栈、出栈和修改栈顶即可。
二、 0～1背包问题
（一）问题描述
有一些物品，每个物品有自己的重量和价值，现有一背包用来装这些物品，但是背包能承受的重量有限，求这个背包能装下的物品的最大价值。
（二）三路法求解思路
给每一个物品编号，按编号从小到大的顺序将其放入到背包中，为了保证求解过程中不重复，这里规定新装物品的编号只能比背包中已有物品的编号大。
首先是检查操作，只要包里所装物品的总重量没有超标，且其总价值比前一次的最大价值大，则这是一个解。接下来分析三条路径。
1. 入栈，在此处表示可以继续往背包里面添加物品。
出栈条件：在总的重量没有超过背包能够承受的总重量，而且还有可以选择的物品则可以入栈。
出栈操作：装入新的物品，并在装物品的时候需要累加本次装入物品的重量和价值。
2. 出栈，即本次装载失败，拿出最后装入的物品。
条件：只有在最后裝入的物品是编号最大的物品时才出栈。
操作：在出栈的同时，减去拿出物品的重量和价值，同时意味着再前一次选择的物品已经不能得到新的解了，于是，还需要通过修改栈顶数据的方法，将其修改为它的下一个物品，具体操作参见“修改栈顶”。
3. 修改栈顶，即拿出最后选择的物品，并将其下一个物品放入背包中。
条件：背包中的物品重量总和超重，且最后加入的物品不是最后一个物品。
操作：从背包中拿出最后一次放入的物品，从总重中减去其重量，从总价值中减去其价值，然后加入其下一个物品，累加重量和价值。
三、 汉诺塔
（一）问题描述
在一块铜板装置上，有三根杆（编号A、B、C），在A杆自下而上、由大到小按顺序放置若干个金盘。把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
（二）三路法求解思路
假设有n个盘子，总的求解思路是先将n-1个盘子按照题目要求通过C从A移到B，然后将A上最大的盘子移动到C，最后，再将B上的n-1个盘子按规则通过A移动到C。
为了便于表述，将A称为源，将B称为中介，C称为目的。堆栈的每一个元素为一个记录，记录着每一次的移盘任务信息，任务信息包括源、中介、目的和盘子数量四个项目。
首先是检查操作，当移盘任务的数量为1的时候，我们可以直接移盘，即从源移动到目的。接下来分析三条路径。
1. 入栈，即启动新的移盘任务。
条件：盘子数量大于1的时候，需要继续加入子任务来完成这个任务。
操作：新建一个任务记录，该任务记录的源为最后任务的源，中介为最后任务的目的，目的为最后任务的中介，数量比最后一次移盘任务的数量少1。
2. 出栈，即该移盘任务已完成，撤销任务记录。
条件：当移动任务的盘子数量为1时，才表示该任务被执行。
操作：撤销最后一次记录，对栈顶进行修改，修改过程见下文分析。
3. 修改栈顶，即更改当前任务信息。
条件：上一次任务是出栈操作且还有移动任务没有完成。
操作：将其前一次任务的盘子从源移动到目的，将其源改为其中介，将其中介改为其源，盘子数量减1。
四、 八皇后问题
（一）问题描述
在一个国际象棋的棋盘上放置8个皇后，使它们相互之间不能攻击，即任意两个皇后不能在同一行、同一列、同一对角线和同一反对角线上。
（二）三路法求解思路
堆栈的第i个元素表示皇后在这一行上的位置，即列数。从第一行开始，依次为每一行的皇后选择位置。
首先是检查，检查目前已放置的皇后是否符合题目的要求。接下来分析三个路径。
1. 入栈，即往棋盘放入皇后。
条件：满足题目要求，而且皇后数量小于8。
操作：在该行上为皇后选择位置，放入皇后。
2. 出栈，即取出该行上的皇后。
条件：皇后已移到了该行的最后一列，而且当前不是在第一行上。
操作：拿出在该行上的皇后，并退回到上一行。
3. 修改栈顶，即将最后放入的皇后从所在行的位置移到下一列。
条件：皇后不在该行的最后一列。
操作：将皇后从所在行的位置移到下一列。
三路模型用规范的方式来分析回溯问题，使其处理过程更加清晰简单，重点放到了每一路的条件和操作上，只要分析清楚了各路径的条件和操作，就能保证结果的正确性。但是，在实际问题处理中，这三条路径的关系还是有很大的区别，这也是容易导致错误的地方，需要谨慎对待。
关键词：回溯问题;三路模型;汉诺塔
一、 回溯问题与三路模型
回溯问题是常见的一类问题，这种问题的解有很多个，我们需要去发现它的所有的解或者是最优解。解决回溯问题的基本思路就是按一定路径尝试去搜索所有的解，在搜索过程中发现再往前不可能得到这个问题的解，则放弃这条路径并退回上一个步骤继续下一条路径的搜索。处理回溯问题的方法很多，比如递归法、堆栈法、计数法等。
三路模型是堆栈法的一种实现方式，但是将问题的求解过程进行了简化和规范，使问题的解决更加简单。三路模型将每一次处理过程归纳为三个操作，它们分别是入栈、出栈和检查栈顶的操作。操作过程如下图所示：
图1 三路模型示意图
每一次进入循环体之后，首先检查当前状态是否是需要的解，如果是需要的解，则输出结果。状态检查完毕之后就有三个路径可选。一是入栈，即再次加入新的信息，继续往前搜索解;二是出栈，即回溯，倒回到上一个步骤，另外寻找求解路径;三是修改栈顶，相当于先出栈再入栈。可以证明这三个操作是完备的，不会遗漏问题的解。在求解具体问题的时候，只需要思考什么情况下入栈、出栈和修改栈顶即可。
二、 0～1背包问题
（一）问题描述
有一些物品，每个物品有自己的重量和价值，现有一背包用来装这些物品，但是背包能承受的重量有限，求这个背包能装下的物品的最大价值。
（二）三路法求解思路
给每一个物品编号，按编号从小到大的顺序将其放入到背包中，为了保证求解过程中不重复，这里规定新装物品的编号只能比背包中已有物品的编号大。
首先是检查操作，只要包里所装物品的总重量没有超标，且其总价值比前一次的最大价值大，则这是一个解。接下来分析三条路径。
1. 入栈，在此处表示可以继续往背包里面添加物品。
出栈条件：在总的重量没有超过背包能够承受的总重量，而且还有可以选择的物品则可以入栈。
出栈操作：装入新的物品，并在装物品的时候需要累加本次装入物品的重量和价值。
2. 出栈，即本次装载失败，拿出最后装入的物品。
条件：只有在最后裝入的物品是编号最大的物品时才出栈。
操作：在出栈的同时，减去拿出物品的重量和价值，同时意味着再前一次选择的物品已经不能得到新的解了，于是，还需要通过修改栈顶数据的方法，将其修改为它的下一个物品，具体操作参见“修改栈顶”。
3. 修改栈顶，即拿出最后选择的物品，并将其下一个物品放入背包中。
条件：背包中的物品重量总和超重，且最后加入的物品不是最后一个物品。
操作：从背包中拿出最后一次放入的物品，从总重中减去其重量，从总价值中减去其价值，然后加入其下一个物品，累加重量和价值。
三、 汉诺塔
（一）问题描述
在一块铜板装置上，有三根杆（编号A、B、C），在A杆自下而上、由大到小按顺序放置若干个金盘。把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
（二）三路法求解思路
假设有n个盘子，总的求解思路是先将n-1个盘子按照题目要求通过C从A移到B，然后将A上最大的盘子移动到C，最后，再将B上的n-1个盘子按规则通过A移动到C。
为了便于表述，将A称为源，将B称为中介，C称为目的。堆栈的每一个元素为一个记录，记录着每一次的移盘任务信息，任务信息包括源、中介、目的和盘子数量四个项目。
首先是检查操作，当移盘任务的数量为1的时候，我们可以直接移盘，即从源移动到目的。接下来分析三条路径。
1. 入栈，即启动新的移盘任务。
条件：盘子数量大于1的时候，需要继续加入子任务来完成这个任务。
操作：新建一个任务记录，该任务记录的源为最后任务的源，中介为最后任务的目的，目的为最后任务的中介，数量比最后一次移盘任务的数量少1。
2. 出栈，即该移盘任务已完成，撤销任务记录。
条件：当移动任务的盘子数量为1时，才表示该任务被执行。
操作：撤销最后一次记录，对栈顶进行修改，修改过程见下文分析。
3. 修改栈顶，即更改当前任务信息。
条件：上一次任务是出栈操作且还有移动任务没有完成。
操作：将其前一次任务的盘子从源移动到目的，将其源改为其中介，将其中介改为其源，盘子数量减1。
四、 八皇后问题
（一）问题描述
在一个国际象棋的棋盘上放置8个皇后，使它们相互之间不能攻击，即任意两个皇后不能在同一行、同一列、同一对角线和同一反对角线上。
（二）三路法求解思路
堆栈的第i个元素表示皇后在这一行上的位置，即列数。从第一行开始，依次为每一行的皇后选择位置。
首先是检查，检查目前已放置的皇后是否符合题目的要求。接下来分析三个路径。
1. 入栈，即往棋盘放入皇后。
条件：满足题目要求，而且皇后数量小于8。
操作：在该行上为皇后选择位置，放入皇后。
2. 出栈，即取出该行上的皇后。
条件：皇后已移到了该行的最后一列，而且当前不是在第一行上。
操作：拿出在该行上的皇后，并退回到上一行。
3. 修改栈顶，即将最后放入的皇后从所在行的位置移到下一列。
条件：皇后不在该行的最后一列。
操作：将皇后从所在行的位置移到下一列。
三路模型用规范的方式来分析回溯问题，使其处理过程更加清晰简单，重点放到了每一路的条件和操作上，只要分析清楚了各路径的条件和操作，就能保证结果的正确性。但是，在实际问题处理中，这三条路径的关系还是有很大的区别，这也是容易导致错误的地方，需要谨慎对待。