【毕业设计】回溯法解决n色方柱问题的算法设计与分析

下步在构成的图中，找出个特殊子图。

个子图表示叠置的哥立方体的前侧面与背侧面，另子图表示叠置的个立方体的左侧面与右侧面。

这两个子图应满足下述性质。

每个子图有条边，且每个立方体恰好条边。

个子图没有公共边。

子图中每个顶点的度均为。

对于图中的图，找出满足要求的两个子图如图所示。

给子图的每条边个方向，使每个顶点有条出边和条入边。

有向边得始点对应于面和左面有向边的终点对应于背面和右面。

图给出的满足要求的解如下。

上述算法的关键是找满足性质和的子图。

用回溯法。

实验数据与结果实验输入文件实验输出结果参考文献王晓东计算机算法设计与分析第版电子工业出版社附录二维数组存储个立方体各面的颜色，存储解，每个立方体找次，每个立方体找次每个立方体只有条边找到解取下条边回溯找到个解由输出。

找下条未用边开始顶点找下个立方体执行算法的主要函数如下中国传媒大学学年第学期计算机算法设计与分析课程计算机算法设计与分析题目回溯法解决色方柱问题的算法设计与分析学生姓名学号班级学院任课教师回溯法解决色方柱问题的算法设计与分析摘要对于计算机科学来说，算法的概念是至关重要的。

算法是系列解决问题的清晰指令，也就是说，能够对定规范的输入，在有限时间内获得所要求的输出。

为了充分理解算法分析的思想，利用算法思想解决实际问题，所以用回溯法解决书上习题色方柱问题。

关键字计算机算法回溯法色方柱回溯法背景回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按种顺序逐枚举和检验。

当发现当前候选解不可能是解时，就选择下个候选解倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。

如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的个解。

在回溯法中，放弃当前候选解，寻找下个候选解的过程称为回溯。

扩大当前候选解的规模，以继续试探的过程称为向前试探。

回溯法的基本思想确定了解空间的组织结构后，回溯法就从开始结点根结点出发，以深度优先的方式搜索整个解空间。

这个开始结点就成为个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至个新结点。

这个新结点就成为个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。

换句话说，这个结点不再是个活结点。

此时，应往回移动回溯至最近的个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

问题描述设有立方体，每个立方体的每个面用红黄蓝绿等种颜色之染色。

要把这个立方体叠成个方形柱体，使得柱体的个侧面的每侧均有种不同的颜色。

试设计个回溯算法，计算出个立方体的种满足要求的叠置方案。

例如第行有个正整数表示给定的立方体个数和颜色数均为。

第行是个大写字母组成的字符串。

该字符串的第个字符代表第种颜色。

接下来的行中，每行有个数，表示立方体各面的颜色。

立方体各面的编号如图所示上图中表示前面，表示背面，表示左面，表示右面，表示顶面，表示底面。

相应的表示前面，表示背面，表示左面，表示右面，表示顶面，表示底面。

算法分析此问题中，立方体的每对相对的面得颜色是要考察的关键因素。

将每个立方体表示为有个顶点的图。

图中每个顶点表示种颜色。

在立方体每对向对面的顶点建连条边。

例如，图是图所示的个立方体所相应的子图。

将上述子图合并，并标明每条边来自哪个立方体如图所示。

下步在构成的图中，找出个特殊子图。

个子图表示叠置的哥立方体的前侧面与背侧面，另子图表示叠置的个立方体的左侧面与右侧面。

这两个子图应满足下述性质。

每个子图有条边，且每个立方体恰好条边。

个子图没有公共边。

子图中每个顶点的度均为。

对于图中的图，找出满足要求的两个子图如图所示。

给子图的每条边个方向，使每个顶点有条出边和条入边。

有向边得始点对应于面和左面有向边的终点对应于背面和右面。

图给出的满足要求的解如下。

上述算法的关键是找满足性质和的子图。

用回溯法。

实验数据与结果实验输入文件实验输出结果参考文献王晓东计算机算法设计与分析第版电子工业出版社附录二维数组存储个立方体各面的颜色，存储解