| 标题 | 回溯法在计算机程序设计中的应用 |
| 范文 | 裴南平 毕传林 摘要：回溯法是计算机程序设计中经常使用的一种算法。为了在更好的理解和应用回溯法，从人们熟知的穷举法入手，层层展开，逐步过渡到回溯法，并分析回溯法中扩展、回溯、调整三个关键步骤，理解回溯法的运行过程，建立回溯法算法，从而使用回溯法解决程序设计中的实际问题。 关键词：回溯法；穷举法；算法模型 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）31-0262-03 Application of Backtracking Method in Computer Programming PEI Nan-ping， BI Chuan-lin （Jiujiang Vocational and Technical College， Jiujiang 332007， China） Abstract： Backtracking is one of the most frequently used programming algorithms in computer programming. In order to better understand and use backtracking in the program design. We start with the exhaustive method and gradually use backtracking to implement it， We analyzed three key steps of extension， backtracking and adjustment， establish backtracking algorithm model and use backtracking in program design. Key words： backtracking method； exhaustive method； algorithm model 回溯法，又称试探法，是计算机程序设计中经常使用的一种算法，在实际中，有着广泛的应用。但是对于初学者又是一个比较难于理解的高级算法，如何在计算机程序设计中得心应手的使用回溯法呢？我们从大家很容易理解的穷举法展开，逐步过渡到回溯法的实现，详细分析回溯法中中扩展、回溯、调整等三个关键步骤，帮助程序员设计人员理解回溯法的运行过程，建立回溯法算法模型，并在实际程序设计使用此方法。 1 回溯法模型 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。 用回溯法求解问题规模有n层的所有解，其中m（0<=m<=n-1）是当前求解问题的层数。算法模型如下： m=0； /* 当前从第0层开始 */ 设置第0层的初始数据； while（1） if（第m层数据没有越界 && 当前规模m符合解的所有条件） if（m==n-1） /* 已达到问题要求解的规模 */ { 输出一个解； 调整第m层到下一个数据； } else { /* 当前还没有达到问题要求解的规模 */ m++； /*扩展到下一层 */ 设置第m层初始数据； } else if（第m层数据越界） { if（m==0） /* 穷举完毕，跳出循环结束程序 */ break； m—； /* 回溯到上一层 */ 调整第m层到下一个数据； } else 调整第m层到下一个数据； /* 当前数据没有越界 */ 该算法模型对于有经验的程序员是不难理解的，但对于初学者就有点茫然了，其动态运行过程更难想象。下面用一个简单的示例，先用容易理解的穷举法解决，逐步递推，过渡到回溯法的思路。 2 程序举例 问题： 從1至k的自然数字中取n个数字，组合成一个新的数值，输出所有的组合数值。例如：k=5，n=3也就是从1至5中5个数字取3个数字，其所有的组合数如下： 123 124 125 132 134 135 142 …… 512 513 514 521 523 524 531 532 534 541 542 543。共60个解。 为了描述方便，下面所有程序设定k=8，n=5。当然可以修改程序中的常量为任意值。首先使用穷举法来解决这个问题。 3 最简单的穷举法程序 k=8，n=5。从1至8中取5个数字，输出所有的组合数值。程序如下： #include #define K 8 #define N 5 void main（） { int a0，a1，a2，a3，a4； int total； /*解的总数 */ total=0； for（a0=1；a0<=K；a0++） for（a1=1；a1<=K；a1++） for（a2=1；a2<=K；a2++） for（a3=1；a3<=K；a3++） for（a4=1；a4<=K；a4++） if（a1！=a0&&a2！=a0&&a2！=a1&&a3！=a0&&a3！=a1&&a3！=a2&&a4！=a0&&a4！=a1&&a4！=a2&&a4！=a3）
{ total++； printf（"第%d个解： "，total）； printf（"%d%d%d%d%d＼n"，a0，a1，a2，a3，a4）； } printf（"解的总数=%d＼n"，total）； } 从1至8中取5个数字，每个数字的范围都是1至8，因为每个数字只能取一次，所以取得的5個数字互不相同。程序中一个数字从1至8一层循环，5重循环包含了所有的取值。这个穷举法的程序是很好理解的，其运行过程就是从11111至88888之间的所有的5位数值排列组合中输出5位数字互不相同的数值。不过程序中有一些肯定不是解的排列组合，例如a0=1，a1=1时，由于a0和a1取的数字相同，一个数字不能取二次，后面a2、a3、a4三层循环不需要运行，其排列组合肯定不是解。 4 用数组元素作为循环变量的穷举法程序 #include #define K 8 #define N 5 void main（） { int a[N]； int total； /*解的总数 */ total=0； for（a[0]=1；a[0]<=K；a[0]++） for（a[1]=1；a[1]<=K；a[1]++） if（a[1]==a[0]） continue； else for（a[2]=1；a[2]<=K；a[2]++） if（a[2]==a[0]||a[2]==a[1]） continue； else for（a[3]=1；a[3]<=K；a[3]++） if（a[3]==a[0]||a[3]==a[1]||a[3]==a[2]） continue； else for（a[4]=1；a[4]<=K；a[4]++） if（a[4]==a[0]||a[4]==a[1]||a[4]==a[2]||a[4]==a[3]） continue； else { total++； printf（"第%d个解： "，total）； printf（"%d%d%d%d%d＼n"，a[0]，a[1]，a[2]，a[3]，a[4]）； } printf（"解的总数=%d＼n"，tota l）； } 这个程序与上一个没有多大差别，之所以定义数组元素作为循环变量是为后面采用回溯法程序进行设计。 穷举法是应用最广的算法，可以解决很多问题，也是容易理解和掌握的算法，但也有一些不足之处。受语言编译系统的限制，循环嵌套的重数不能太多；即使没有限制，循环嵌套重数太多，代码书写也无法层次展开。这对于规模较大，层数较多的问题就无法使用穷举法。本文讨论的自然数1至k中取n个数，n超过6用穷举法就不适合了，这是可以采用回溯法。 回溯法其实是一种变化的穷举法。从某种意义说，所有的算法都是穷举法，都是利用计算机强大快速的计算能力处理所有的情况。回溯法尤其明显，下面将要给出的回溯法程序与现在分析的穷举法程序思路和运行过程几乎一模一样。为了对应理解，将本程序几个关键的地方用回溯法的术语描述一下。 从1至k中取n个数字，取一个数字一层，问题的规模有n层，分别是第0层、第1层、第2层、...、第n-1层。 n层规模对应n重循环。 a[0]控制的循环是第0层，a[0]保存的值是从1至k中取的第1个数字； a[1]控制的循环是第1层，a[1]保存的值是从1至k中取的第2个数字； a[2]控制的循环是第2层，a[2]保存的值是从1至k中取的第3个数字； ...... a[n-1]控制的循环是第n-1层，a[n-1]保存的值是从1至k中取的第n个数字，这一层是最后一层； 本层循环进入下一层循环，回溯法称为“扩展”； 本层循环结束，回退到上一层循环，回溯法称为“回溯”； 本层循环if语句判断循环变量（本层取的数字）与上几层循环变量相同，取值非法，continue控制循环变量加1，继续下一次循环，回溯法称为“调整”。 5 回溯法程序 #include #define K 8 #define N 5 int a[N]； /* 从1至K中取N个自然数，保存到数组a的N个元素中 */ int total； /* 解的总数 */ void output（） /*输出一个解 */ { int i； printf（"第%d个解： "，total）； for（i=0；i printf（"%d"，a[i]）； printf（"＼n"）； } int right（int m） /* 判断第m层是否符合条件，是返回1，否则返回0。 */ { int i； /* 判断第m层取的数字与前面取的数字是否相同 */ for（i=0；i if（a[i]==a[m]） return 0； return 1；
} void search（） /* 回溯法搜索所有解 */ { int m； m=0； /* 当前从第0层开始 */ a[m]=1； /* 设置第0层初始取的数字从1开始 */ while（1） if（a[m]<=K && right（m）==1） /*第m層数字没有越界并且规模m符合条件*/ if（m==N-1） /* 已经达到要求解的规模 */ { total++； /* 解的总数加1 */ output（）； /* 输出一个解 */ a[m]++； /*调整第m层数字到下一个数字 */ } else { m++； /* 扩展到下一层 */ a[m]=1； /*设置第m层初始数字从1开始 */ } else if（a[m]>=K） /* 第m层数字超过K越界 */ { if（m==0） /* 穷举完毕，跳出循环结束程序 */ break； m—； /* 回溯到上一层 */ a[m]++； /* 调整第m层数字到下一个数字 */ } else a[m]++； /* 没有越界，调整第m层数字到下一个数字 */ } void main（） { total=0； printf（"求解开始，请稍候。＼n"）； search（）； printf（"解的总数=%d＼n"，total）； printf（"求解结束。＼n"）； } 为了突出回溯法的核心部分，也为以后解决复杂问题铺垫，程序分解成几个函数。函数output（）是输出一个解；函数right（int m）是判断当前第m层的规模是否符合解的所有的条件，也就是当前所有的取值是否合法；程序回溯法的主体部分也设计成一个函数search（），这里只解析回溯法的核心部分，其他的细枝末节就不再赘述。 函数search（）的运行过程基本与上面穷举法程序一模一样，虽然表面是一个单重循环，其实是n层循环嵌在其中。m是当前的层数，首先m=0，从第0层开始循环；当前第m层取的数字没有超过k越界，并且当前第m层规模所有取的数字合法，m++，进入到下一层，也就是“扩展”，当m到了n-1最后一层，就不需要扩展，当前是一个合法的解，输出这个解后，a[m]++，当前层取下一个数字，也就是“调整”。否则，当前层取的数字超过k越界，m—，退回到上一层，调整该层取的数字，也就是“回溯”，如果已经退回到第0层，就不能再回溯，这时已经将所有取的数字排列组合穷举完毕，跳出死循环，结束程序。如果当前层取的数字没有超过k越界，就调整到下一个数字。 结合上面穷举法程序运行的过程，理解本程序运行的过程，明确“扩展”、“回溯”、“调整”等几个关键术语的意思。再与本文开始给出的回溯法模型融会贯通，就可以建立算法模型，解决各类程序设计中的复杂问题。 参考文献： [1] 聂华. 基于四皇后问题的回溯法求解及算法实现[J]. 电子测试， 2013（9）. [2] 谢玉庚. 用回溯法编程求解爱因斯坦谜题[J]. 电脑与电信， 2016（10）. [3] 田翠华， 等. 深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J]. 河北北方学院学报：自然科学版， 2013（6）. [4] 王防修. 回溯法在物流车动态导航中的应用[J]. 武汉轻工大学学报， 2017（6）. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。