搜索算法-DFS再探究

搜索算法之DFS再探究YangzhengMiddleSchool深度优先搜索算法（DFS）深度优先搜索是实现搜索的一种策略深度优先搜索的基本思想：为了求得问题的解，先选择一种可能情况不断向前探索，一旦发现选择错误，则退回一步重新选择，然后继续向前探索简单来说就是“一条路走到底，不通再掉头”深度优先搜索最基本的算法实现方式就是采用递归回溯YangzhengMiddleSchool全排列问题设有n个整数的集合{1,2,…,n}，从中任意取出r个数进行排列（rn），试列出所有的排列。n=4，r=3时的搜索树12341213144212313214241212413414342141342343143241431…………234234123342423231312YangzhengMiddleSchool例题1数字游戏有这么一个游戏：写出一个1～N的排列a[i]，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：31244367916最后得到16这样一个数字。现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列a[i]。若答案有多种可能，则输出字典序最小的那一个。YangzhengMiddleSchool例题1数字游戏【输入文件】输入文件bds.in的第1行为两个正整数n，sum。【输出文件】输出文件bds.out包括1行，为字典序最小的那个答案。【样例输入】416【样例输出】3124【数据规模与约定】对于40%的数据，n≤7；对于80%的数据，n≤10；对于100%的数据，n≤12，sum≤12345，且保证一定有解。YangzhengMiddleSchool例题1数字游戏思路：枚举初始排列，状态数：n!计算最后的数字，复杂度：O(n^2)最终复杂度O(n!*n^2)N=12时，复杂度≈6*10^10，超时！YangzhengMiddleSchool例题1数字游戏思路：设排列为a[1],a[2],…,a[N]，经过一系列累加得到了最后的答案sum，既然是累加，设：sum=c[1]*a[1]+c[2]*a[2]+……+c[n]*a[n]求c[i]，设a[i]=1，其他a均为0，模拟计算一次，就可以得到a[i]被累加了几次，即得到了c[i]。1000010000100001100110011001102112011331YangzhengMiddleSchool例题1数字游戏可以发现，其实最后系数为杨辉三角第N层的系数111121133114641例如N=5，最初的排列为ABCDEsum=A*1+B*4+C*6+D*4+E*1解题步骤：1、计算杨辉三角第N层的系数b[1..n]2、枚举初始排列a[1..n]，状态数：n!3、计算sum(a[i]*b[i]){i∈1..n}，复杂度：O(n)最终复杂度O(n!*n)N=12时，复杂度≈10^9YangzhengMiddleSchool关于搜索的关键词对象状态转移边界剪枝方向YangzhengMiddleSchool例题2小木棍有一些等长的木棍，被切成一些已知长度的小木棍（最长50），求最小可能原长。小木棍的个数不超过60。YangzhengMiddleSchool例题2小木棍搜索方法：先假设一个长木棍的长度，再试着用小木棍一根根地拼，看看能不能拼出来。搜索对象1：长木棍O(50*N)搜索对象2：小木棍O(N!)总复杂度：O(50*N*N!)≈2.5*10^85YangzhengMiddleSchool例题2小木棍搜索状态怎么表示，如何转移？对于搜索对象1：长木棍长度状态：直接定义一个变量orglen转移：枚举范围：最长小木棍长度小木棍总长YangzhengMiddleSchool例题2小木棍对于搜索对象2：小木棍状态：dfs(curnum,rest,f)curnum：目前正在拼第几根长木棍rest：当前的长木棍还剩多长没拼f：从第几根小木棍开始尝试转移：1、rest=0dfs(curnum+1,orglen,1)2、第i根小木棍可用dfs(curnum,rest-a[i],i+1)边界：1、curnum=长木棍数量并且rest=0，返回true2、找不到任何一根小木棍=rest，返回falseYangzhengMiddleSchool例题2小木棍剪枝1：长木棍应满足什么条件？为所有小木棍总长度的因数。剪枝2：长木棍有最小值吗？显然最小值为小木棍的最大长度。YangzhengMiddleSchool例题2小木棍剪枝3：如何定一个搜索顺序能加快搜索？将小木棍从长到短排序，短的木棍使用更灵活，所以先放长的小木棍较好，否则一开始就用完短的小木棍再放长的小木棍就不好放了。剪枝4：在还原长木棍时，第1根放什么，能确定吗？显然，最长的那根小木棍肯定要放进去，那么作为第1根，如果这都搜不出来那么肯定就无解了。YangzhengMiddleSchool例题2小木棍剪枝5：长度相同的木棍可以做什么优化？如果有多根长度为x的小木棍，现在放x搜不出结果，那么这些再把另一个x放进去肯定也搜不出结果来。剪枝6：如果当前放的是最长的那一根小木棍，他正好与前面放置的小木棍拼出了一根长木棍，但是搜下去却找不到一种可行方案，那么？不继续进行搜索！放弃尝试更短的小木棍。YangzhengMiddleSchool例题3间隔排列有2N个木块，每个木块标上1到N的自然数中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木块之间要间隔i个其它木块。比如N=3时，下面就是一个可行的排列：3，1，2，1，3，2。编程实现，对给定的N(n=40)，求出一个可行排列给出的输入数据保证能找到可行的排列YangzhengMiddleSchool例题3间隔排列搜索策略：排列：O((2N)!)，没有很好的剪枝回溯：O((2N)!)，在回溯过程中进行剪枝广搜：空间需求大，另本题并非求最优解采用回溯（深搜）策略，在深搜过程中减少搜索分支YangzhengMiddleSchool例题3间隔排列搜索思路1对象：自然数1~N状态：dfs(K)，K为木块序号，表示尝试在第K木块上标上1~N的自然数转移：K2N，找到解，搜索结束找到一个可标在第K个木块的数dfs(K+1)找不到可标在第K个木块的数回溯dfs(K-1)，查找下一个可标在第K-1个木块的数字YangzhengMiddleSchool例题3间隔排列搜索思路1剪枝：因为两个相同数字i的间隔为i，所以若数字i第一次标在第K个木块中，则必定K+i+1个木块也应标上数字i。dfs(K)中只搜索第一次标的的数字，dfs(K)实际只需嵌套N层若i+K+12*N，则i可以剪枝，因为i第二次标注已经超过木块数在dfs(K)中，数字从N到1进行尝试。因为大数字的选择余地比较小YangzhengMiddleSchool例题3间隔排列搜索思路2对象：木块1~2N状态：dfs(Num)，Num为数字序号，表示尝试在1~2N的木块中查找可以标上数字Num的木块转移：NumN，找到解，搜索结束找到可标上Num的木块dfs(Num+1)找不到可标上Num的木块回溯dfs(Num-1)，为Num-1换一个位置YangzhengMiddleSchool例题3间隔排列搜索思路2剪枝：若尝试将数字Num第一次标在第K个木块中，应该同时标在第K+Num+1个木块上，减少后续的dfs(Num)中对木块的搜索搜索可标注木块时，范围从第1~2*N-Num-1块先尝试大数字dfs(Num)的状态改为从N开始•Num=0，找到解，搜索结束•找到可标上Num的木块：dfs(Num-1)•找不到可标上Num的木块：回溯dfs(Num+1)，为Num+1换一个位置YangzhengMiddleSchool例题3间隔排列运行效果对比N从小到大搜索从大到小搜索30.00s0.00s70.01s0.00s110.01s0.00s150.01s0.01s160.17s0.00s198.15s0.00s2010.43s0.01s2730s0.00s3230s0.00s4030s0.00sYangzhengMiddleSchool例题4数独数独是一款能开发智力的游戏，其规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。7126358652714851367292456375624113729519754866783519859423YangzhengMiddleSchool7126358652714851367292456375624113729519754866783519859423例题4数独712469358365287194498513672924156837576398241183724965121975486647832519859641723YangzhengMiddleSchool例题4数独明显，这是一道深搜的题目搜索对象：空白格子、数字1-9状态：9*9矩阵转移：在某一空白格子，搜到可填数字，更新9*9矩阵边界：没有空白格子填充完成某一个空白格子搜索不到合适数字回溯YangzhengMiddleSchool例题4数独剪枝：某一格没有可填的数字，剩下格子也不用搜索了方向按格子坐标顺序？模拟人的思维，先易后难！先填可选择数字少的7126358652714851367292456375624113729519754866783519859423YangzhengMiddleSchool例题4数独搜索顺序数组sz[i][j]i：0~81，待填的空白格子数j：0、1，空白格子坐标2，格子可填数字的数量搜索顺序数组排序（一边排序一边更新）设待排序区间为sz[a]~sz[b]查找最小的sz[i][2]，sz[i]sz[a]在sz[a+1]~sz[b]中查找与sz[a]在同一列或同一行或同一区域的格子sz[j]，将sz[j][2]值减1YangzhengMiddleSchool例题4数独在程序需维护的几个状态col[i][j]：第i列中，数字j是否可用row[i][j]：第i行中，数字j是否可用block[i][j]：第i区域中，数字j是否可用7126358652714851367292456375624113729519754866783519859423colrowblockYangzhengMiddleSchool例题4扩充靶形数独每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。完成一个给定的数独，而且要争取更高的总分数。总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。YangzhengMiddleSchool例题4扩充靶形数独与数独类似，难点在于需要找出所有的填充方案。剪枝？设已经找到最大分数为max当前已经填充的格子分数和为cur未填充的格子最大可能分数和为rest若cur+restmax则剪枝操作代价太大！YangzhengMiddleSchool例题4扩充靶形数独搜索顺序分值越大的越先搜索？按照分值大小来搜索，目的是为了依据分数来剪枝，但剪枝的操作代价太大反正都必须一搜到底，分值大小对减少搜索没有意义可选择的数字越少越先搜索可大大减少搜索树的分支YangzhengMiddleSchool例题4扩充靶形数独搜索顺序数组sz[i][j]i：0~81，待填的空白格子数j：0、1，空白格子