第5章搜索与回溯算法(C++版)VIP免费

第五章搜索与回溯算法搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。递归回溯法算法框架[一]intSearch(intk){for(i=1;i<=算符种数;i++)if(满足条件){保存结果if(到目的地)输出解;elseSearch(k+1);恢复：保存结果之前的状态{回溯一步}}}递归回溯法算法框架[二]intSearch(intk){if(到目的地)输出解;elsefor(i=1;i<=算符种数;i++)if(满足条件){保存结果;Search(k+1);恢复：保存结果之前的状态{回溯一步}}}【例1】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。【算法流程】1、数据初始化；2、递归填数：判断第i个数填入是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；【参考程序】#include#include#include#includeusingnamespacestd;boolb[21]={0};inttotal=0,a[21]={0};intsearch(int);//回溯过程intprint();//输出方案boolpd(int,int);//判断素数intmain(){search(1);cout<";for(intj=1;j<=20;j++)cout<sqrt(i))return1;elsereturn0;}【例2】设有n个整数的集合｛1,2,…,n｝，从中取出任意r个数进行排列（r#include#includeusingnamespacestd;intnum=0,a[10001]={0},n,r;boolb[10001]={0};intsearch(int);//回溯过程intprint();//输出方案intmain(){cout<<"inputn,r:";cin>>n>>r;search(1);cout<<"number="<#include#includeusingnamespacestd;inta[10001]={1},n,total;intsearch(int,int);intprint(int);intmain(){cin>>n;search(n,1);//将要拆分的数n传递给scout<<"total="<0时，继续递归s+=i;//回溯：加上拆分的数，以便产分所有可能的拆分}}intpr...