回溯法在计算机程序设计中应用.docVIP

回溯法在计算机程序设计中应用 　　摘要：回溯法是计算机程序设计中经常使用的一种算法。为了在更好的理解和应用回溯法，从人们熟知的穷举法入手，层层展开，逐步过渡到回溯法，并分析回溯法中扩展、回溯、调整三个关键步骤，理解回溯法的运行过程，建立回溯法算法，从而使用回溯法解决程序设计中的实际问题。 　　关键词：回溯法；穷举法；算法模型 　　中图分类号：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