logo资料库

计算机算法设计与分析学习心得.doc

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：0.10M 资料格式：doc 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    计算机算法设计与分析小论文 ——回溯法精髓 计算机科学系 06 级（1）班 李元锁 学号：20061081135 摘要： 计算机算法设计与分析课程已经结束 ，为了充分理解算法分析的 思想，能利用算法思想解决实际问题，而回朔法是算法分析中的精华， 所以充分体现课程的真正目的特写此论文。 关键字：回溯法，着色 回溯法背景： 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的 限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候 选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不 满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的 规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要 求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解， 寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续 试探的过程称为向前试探。 1、回溯法的一般描述 可用回溯法求解的问题 P，通常要能表达为：对于已知的由 n 元组（x1， x2，…，xn）组成的一个状态空间 E={（x1，x2，…，xn）∣xi∈Si ， i=1，2，…，n}，给定关于 n 元组中的一个分量的一个约束集 D，要
    求 E 中满足 D 的全部约束条件的所有 n 元组。其中 Si 是分量 xi 的定 义域，且 |Si| 有限，i=1，2，…，n。我们称 E 中满足 D 的全部约 束条件的任一 n 元组为问题 P 的一个解。 解问题 P 的最朴素的方法就是枚举法，即对 E 中的所有 n 元组逐一地 检测其是否满足 D 的全部约束，若满足，则为问题 P 的一个解。但显 然，其计算量是相当大的。 我们发现，对于许多问题，所给定的约束集 D 具有完备性，即 i 元组 （x1，x2，…，xi）满足 D 中仅涉及到 x1，x2，…，xi 的所有约束 意味着 j（jj。因此，对于约束集 D 具有完备性的问题 P， 一旦检测断定某个 j 元组（x1，x2，…，xj）违反 D 中仅涉及 x1， x2，…，xj 的一个约束，就可以肯定，以（x1，x2，…，xj）为前 缀的任何 n 元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题 P 的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题， 利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题 P 的 n 元组的状态空间 E 表示成一棵高为 n 的带权 有序树 T，把在 E 中求问题 P 的所有解转化为在 T 中搜索问题 P 的所 有解。树 T 类似于检索树，它可以这样构造：
    设 Si 中的元素可排成 xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi， i=1，2，…，n。从根开始，让 T 的第 I 层的每一个结点都有 mi 个儿 子。这 mi 个儿子到它们的双亲的边，按从左到右的次序，分别带权 xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照这 种构造方式，E 中的一个 n 元组（x1，x2，…，xn）对应于 T 中的一 个叶子结点，T 的根到这个叶子结点的路径上依次的 n 条边的权分别 为 x1，x2，…，xn，反之亦然。另外，对于任意的 0≤i≤n-1，E 中 n 元组（x1，x2，…，xn）的一个前缀 I 元组（x1，x2，…，xi）对 应于 T 中的一个非叶子结点，T 的根到这个非叶子结点的路径上依次 的 I 条边的权分别为 x1，x2，…，xi，反之亦然。特别，E 中的任意 一个 n 元组的空前缀（），对应于 T 的根。 因而，在 E 中寻找问题 P 的一个解等价于在 T 中搜索一个叶子结点， 要求从 T 的根到该叶子结点的路径上依次的 n 条边相应带的 n 个权 x1，x2，…，xn 满足约束集 D 的全部约束。在 T 中搜索所要求的叶 子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入， 即依次搜索满足约束条件的前缀 1 元组（x1i）、前缀 2 元组（x1， x2）、…，前缀 I 元组（x1，x2，…，xi），…，直到 i=n 为止。 在回溯法中，上述引入的树被称为问题 P 的状态空间树；树 T 上任意 一个结点被称为问题 P 的状态结点；树 T 上的任意一个叶子结点被称 为问题 P 的一个解状态结点；树 T 上满足约束集 D 的全部约束的任意 一个叶子结点被称为问题 P 的一个回答状态结点，它对应于问题 P 的 一个解。
    2、回溯法的方法 对于具有完备约束集 D 的一般问题 P 及其相应的状态空间树 T，利用 T 的层次结构和 D 的完备性，在 T 中搜索问题 P 的所有解的回溯法可 以形象地描述为： 从 T 的根出发，按深度优先的策略，系统地搜索以其为根的子树中可 能包含着回答结点的所有状态结点，而跳过对肯定不含回答结点的所 有子树的搜索，以提高搜索效率。具体地说，当搜索按深度优先策略 到达一个满足 D 中所有有关约束的状态结点时，即“激活”该状态结 点，以便继续往深层搜索；否则跳过对以该状态结点为根的子树的搜 索，而一边逐层地向该状态结点的祖先结点回溯，一边“杀死”其儿 子结点已被搜索遍的祖先结点，直到遇到其儿子结点未被搜索遍的祖 先结点，即转向其未被搜索的一个儿子结点继续搜索。 在搜索过程中，只要所激活的状态结点又满足终结条件，那么它就是 回答结点，应该把它输出或保存。由于在回溯法求解问题时，一般要 求出问题的所有解，因此在得到回答结点后，同时也要进行回溯，以 便得到问题的其他解，直至回溯到 T 的根且根的所有儿子结点均已被 搜索过为止。 例如在组合问题中，从 T 的根出发深度优先遍历该树。当遍历到结点 （1，2）时，虽然它满足约束条件，但还不是回答结点，则应继续深 度遍历；当遍历到叶子结点（1，2，5）时，由于它已是一个回答结 点，则保存（或输出）该结点，并回溯到其双亲结点，继续深度遍历； 当遍历到结点（1，5）时，由于它已是叶子结点，但不满足约束条件，
    故也需回溯。 3、回溯法的一般流程和技术 在用回溯法求解有关问题的过程中，一般是一边建树，一边遍历该树。 在回溯法中我们一般采用非递归方法。下面，我们给出回溯法的非递 归算法的一般流程： 在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用 非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈 来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和 回溯过程。 问题描述 ： 对一张地图，可以用不超过 4 种颜色对其填色，使得相邻的区域 填上不同的颜色。现在我们就来模拟这一填色过程，输入一张行政区 地图，用 4 种颜色对其填色，要求相邻的行政区域内没有相同的颜色， 给出所有的填色方案，并统计方案的个数。 数据描述 ： 首先考虑如何存储行政区地图，由于邻接矩阵能更好地描述 各行政区之间的关系，我们采用邻接矩阵 G 来存储地图。邻接矩阵 G 可以用二维数组表示；另设一维数组 color[i]记录第 i（i=0...n-1） 个行政区所填的颜色，分别取值为：{1(红),2(黄),3(蓝),4(绿)}；数据 描述如下： int G[n][n]; int color[n+1];
    算法描述： 该问题的实现是从第一个行政区到最后一个行政区依次填 色的过程，如果采用递归的算法，可以简单描述如下： trycolor(&color[],i){ Void // 设前 i-1 个行政区已经填好颜色，现对第 i 个行政区用递归法 填色； for (c=1;c<=4;c++) {对第 i 个行政区填上 c 颜色；检查其合法性； if （合法） if （i
    当前区域确定了所填的颜色； if (当前结点是最后一个区域) {打印一种填色方案；if (所填颜色是 4) 回溯到上一个结点 继续填色；} else 下一个结点设为当前结点； else if (所填颜色是 4) 回溯到上一个结点；} while（所有的结果都试探完）； 现在的问题是：如何确定合法的填色？设前 i-1 个行政区已经填好 颜色，现对第 i 个行政区填色 c，通过邻接矩阵的定义，我们可以分 析出这样的结论： for (k=0;k<=i-1;k++) (color[k]*G[i][k]==c) if {i 与第 k 个结点相邻并同色，c 是不合法的}； 所以我们可以用 color[k]*G[i][k]！=color[i]来确定当前 color[i]的颜色是合法的。 如何回溯？如果对当前结点，从颜色 1 到颜色 4 都不合法，则要退 到上一个结点重新填色，如果上一个结点也填了 4 种颜色，就继续后 退；这就是回溯的思想。 源程序： #include #define n 10 int G[n][n]={{1,1,0,1,0,1,0,0,0,0},
    {1,1,1,1,0,0,0,0,0,0}, {0,1,1,1,1,0,0,0,0,0}, {1,1,1,1,1,1,1,0,0,0}, {0,0,1,1,1,0,1,0,0,0}, {1,0,0,1,0,1,1,1,0,0}, {0,0,0,1,1,1,1,1,0,1}, {0,0,0,0,0,1,1,1,1,1}, {0,0,0,0,0,0,0,1,1,1}, {0,0,0,0,0,0,1,1,1,1}}; void backtrack(int color[],int *i) /*回溯过程*/ {if (*i>0) while (color[*i]==4) (*i)--; } int check(int color[], int *i) /*检查是否合 法*/ {int k,b; b=1; for(k=0;k<=*i-1;k++) if (color[k]*G[*i][k]==color[*i]) b=0; if (b) else return return 1; 0; }
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料