文档介绍：合肥学院
计算机科学与技术系
1、问题分析和任务定义
题目:已知有3个容量分别为3kg,5kg和8kg且没有刻度的酒瓶3kg和5kg的瓶子均装满了酒。而8kg的瓶子为空。现要求仅用这3个酒瓶将这些酒均分为两个4kg,并分别装入5kg和8kg的瓶子中。
若要完成题目的要求,首先需要选择一个数据结构表示酒杯数,有3个酒杯并且通过子函数可以输入容器的容量,由题意可知输入的酒杯的容量分别为3、5、8,起始状态下酒杯的装酒数为3、5、0,最终经过转换变为0、4、4。其中每个酒杯的装酒数不得超过容器的容量,可以采取回溯递归的思路。每经过一次转换就覆盖前面的状态,直至最终变为需要的状态为止。
2、数据结构的选择和概要设计
模型描述:由于涉及状态之间的转化,因此可以用图模型进行求解。把每次可分的状态抽象为一个图结点,按照图的有关知识去求解。
本题采用邻接表法存储图的各个顶点信息,然后用深度优先搜索遍历的方法,得到所有的解。整个程序的实现较简单,属于图应用的范畴。因此在遇到求解搜索路径的问题时,我们不妨从图模型的角度去考虑问题,把有关问题抽象为图模型。通过图模型去思考该类问题地解法可能会更简单。因此要深刻理解图方面的知识,尤其是图的深度优先搜索和图的广度优先搜索的应用。
提供的思路为回溯算法的设计方法:回溯是一种系统的搜索问题解答的方法(常见的是求解迷宫老鼠的问题);其过程主要有3个步骤:
(1)首先要为问题定义一个解空间,这个解空间包含问题的解(可能是最优解)。
(2)组织解空间以便能被容易的搜索,同时所搜方法要能够避免移动到不可能产生解得子空间。
(3)定义了解空间的组织方法,这个空间即可按深度优先的方法从开始结点。
从扩展结点可移动到一个新结点,如果能从当前的当前的结点移动到一个新结点,那么这个新结点将变成一个活结点和新的扩展结点,原扩展结点就可以压入堆栈中,但仍是一个活结点。如果不能移动到一个新结点,当前的扩展结点就是一个死结点,那么就只能返回到最近被考察的活结点(回溯,依据堆栈),这个活结点就变为新的扩展结点。
按照这种方法进行搜索,直到找到出口为止,或者是栈空。由于堆栈中始终包含从入口到当前位置的路径,如果最终找到了出口
,那么堆栈中保留的位置值所示的路径就是所要求的问题解之一;如果最终栈空,则表示不存在求解的路径。
也就是当我们找到所有的答案或者回溯了所有的活结点时,搜索过程结束。
回溯算法的解空间可以是图、树、矩阵等数据结构。
设计本题算法的构思如下:
(1)为搜索除符合条件的简单路径,需要按深度优先搜索方式进行遍历。因此,求解算法应是深度遍历算法的变形形式,因而也是递归是形式的算法。
(2) 由于要求遍历序列中的各结点按次序构成一条简单路径,因此,本算法与深度遍历算法有明显的不同:并非任意选择的起点和访问次序都能得到解。而本题的起点和终点是确定的。
(3)既然要在求解过程中进行试探,则需要记录试探的中间状态; 某顶点是否在当前试探路径中,已经试探的各顶点和当前试探顶点的信息。将所用的变量及有关参数设置如下:
用邻接链表存储所得图的结构,链表用两个结构体表示,(struct arc_node ,struct vex_node),其中每个链表的头保存在一个数组中。
用布尔数组visited[MAX_status]表示各状态顶点是否在当前路径中(初始状态全为false).
用栈stack存储当前路径中的各顶点。
(4)既然是试探型求解,则需要对当前顶点v0的每个邻接点进行试探(程序中用s[v0].next表示),试探由v0经s[v0].next往下是否可以得到解,每个s[v0].next都有可能成功(指现在可以放在路径上,这包括暂时的和最终的)与失败的(指状态转化不能完成),,对此应分别做不同的处理:
若试探成功,则应将s[v0].next放在路径中,。然后再由其往下求解。
若不成功,则应恢复s[v0].next的用关信息,以使s[v0].next在试探其他路径中成为可选的试探点。
(5)为了能求出解以及所有可能的解,需要做如下的工作:
选择路径:本题中的起点已经限定,即start_vex={3,5,8}
搜索路径:从v往下搜索时,应依次选择v的所有不在当前路径中的邻接点往下搜索。
为此,需要有这方面的保证:应在试探某顶点之后并在换下一个试探顶点的前恢复该顶点的有关状态,以使其重新成为可选择的顶点。
(6)由以上讨论得本算法的基本思想:
当访问的到顶点状态v==end_vex(最终状态)时,则说明已经求得一解,因此可输出结果,并结束本次算法,继续求解其他可能的解的情况。
若v!=