较好的深搜课件搜索与回溯

搜索与回溯 对于某个问题 如果没有高效的算法 或者用高效的算法解决有一定的困难 我们常用搜索算法来求解 即通过枚举每一种可行的方案来找到题目的答案 深度优先搜索 只要当前枚举到的状态可行 就继续枚举下去 当找到一种方案或者无法继续枚举下去时 就退回到上一状态 退回到上一状态的过程叫做回溯 给定n n 10 求1 2 3 n的全排列个数 如果一个数列包含这n个数 并且这n个数都仅出现一次 符合该条件的所有数列叫做这n个数的全排列 如1 2 3三个元素的全排列为 1 2 31 3 22 1 32 3 13 1 23 2 1 看一个简单的问题 什么是全排列 我们可以用一个布尔数组used来表示每个数字是否用过 用过为true 未用过为false 用ans i 记录第i个位置的数是多少 fori 1tondoifnotused i then 若i未出现过则在第k个位置放ibeginans k i used i true 标记dfs k 1 继续搜索used i false 回溯end end beginread n dfs 1 end programquanpailie varn longint ans array 0 10 oflongint used array 0 10 ofboolean proceduredfs k longint vari longint beginifk nthenbeginfori 1ton 1dowrite ans i writeln ans n exit end A B Proceduresearch k integer beginif到目的地then输出解 exit forI 1to算符种数dobegin保存结果search k 1 恢复到保存结果之前的状态end end 深度优先搜索的一般框架 Proceduredfs k var beginif已找到一种方案thenbeginprint exit end 枚举每种选择if该选择可行thenbegin更改该选择标记dfs k 1 回溯end end A B 例 设有A B C D E五人从事J1 J2 J3 J4 J5五项工作 每人只能从事一项 他们的效益如表所示 求最佳安排使效益最高 分析 每人选择五项工作中的一项 在各种选择的组合中 找到效益最高的一种组合输出 constdata array 1 5 1 5 ofinteger 13 11 10 4 7 13 10 10 8 5 5 9 7 7 4 15 12 10 11 5 10 11 8 8 4 vari max integer g f array 1 5 ofinteger p array 1 5 ofinteger procedurego step t integer vari integer beginifstep 5thenbeginift maxthenbeginmax t g f end exit end fori 1to5doifp i 0thenbeginf step i p i 1 t t data step i go step 1 t t t data step i p i 0 end end beginmax 0 fori 1to5dop i 0 go 1 0 writeln fori 1to5dowrite chr 64 i j g i 3 writeln writeln supply max end 学校放寒假时 信息学竞赛辅导教师有A B C D E五本书 要分给参加培训的张 王 刘 孙 李五位学生 每人只能一本书 教师事先让每个人将自己喜爱的书填写在如下的表中 然后根据他们填写的表来分配书本 希望设计一个程序帮助教师求出所有可能的分书方案 使每个学生都满意 constlike array 1 5 1 5 ofinteger 0 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 name array 1 5 ofstring zhang wang liu sun li varp f array 1 5 ofinteger t integer procedureprint vari integer beginfori 1to5dowrite name i chr 64 f i writeln end proceduretry step integer vari integer beginfori 1to5doif p i 0 and like step i 0 thenbeginf step i p i 1 ifstep 5thentry step 1 elsebeginprint t t 1 end p i 0 end end beginfillchar p sizeof p 0 try 1 writeln t end proceduretry step integer vari integer beginifstep 5thenbeginprint t t 1 exit endfori 1to5doif p i 0 and like step i 0 thenbeginf step i p i 1 try step 1 p i 0 end end beginfillchar p sizeof p 0 try 1 writeln t end forj 1tondoifcan j thenbegincan j false ans i a j dfs i 1 can j true end end beginread n k fori 1tondoread a i fillchar can sizeof can true dfs 1 writeln sdivn end programP1085 vars i j k m n longint ans a array 0 10 oflongint can array 0 10 ofboolean proceduredfs i longint varj longint f boolean beginifi nthenbeginf true forj 1ton 1doifabs ans j ans j 1 kthenbeginf false break end 检验1与2 n 1与niffand abs ans n ans 1 k theninc s exit end A B 有没有更好的做法 我们发现 当我们确定下第一个位置的人与第二个位置的人时 他们的身高可能已经不符合要求了 但我们仍然搜索了下去 我们可以一边搜索一边判断 forj 1tondoifcan j and abs a j ans i 1 k then 若第j个人还没有确定位置并且和上一个人符合要求begincan j false 标记ans i a j dfs i 1 继续搜索can j true 回溯end end beginread n k fori 1tondoread a i fillchar can sizeof can true ans 1 a 1 将第一个人位置固定can 1 false 更改标记dfs 2 writeln s end programP1085 vars i k n longint can array 0 10 ofboolean a ans array 0 10 oflongint proceduredfs i longint varj longint beginifi nthenbeginifabs ans n ans 1 ktheninc s exit end A B 猜猜我是啥 你有n堆石头质量分别为W1 W2 Wn W 100000 现在需要你将石头合并为两部分 使两部分的质量之和最接近 输入 第一行为整数n 1 n 20 表示有n堆石子 第二行n个整数 为每堆石子的质量 输出 一行 只需要输出合并后两部分的质量之和的差 样例输入 样例输出 5358132714 石子合并 beginans maxlongint sum 0 read n fori 1tondobeginread w i sum sum w i end dfs 1 0 writeln ans end programshizihebing varans sum i j k n longint w array 0 20 oflongint functionmin a b longint longint beginifa bthenexit b elseexit a end proceduredfs k tot longint beginif tot 2 sum or k n thenbeginans min ans abs sum tot tot exit end dfs k 1 tot w k 将第k堆石子并入第一部分dfs k 1 tot 将第k堆石子并入第二部分end A B 自然数分解算法 减法 枚举一个数 用n减去这个数 再枚举一个数 再减去这个数 直至减到0 加法 枚举一个数 加上这个数 再枚举一个数 再加上这个数 直至加到n 从大到小枚举 只允许减 加 小于等于last的数 反之则相反 NOIP2009靶形数独 有一个未填满的数独 求这个数独填满后能获得的最大总分数分数计算方法 总分数为每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和 时间限制2s样例输入700900001100005900000200080005020003000000648413000000007002090201060804080504012样例输出2829 一个最简单的想法 我们可以从左上角到右下角枚举每一个未填上的格子 再枚举它可以放哪些数字 将它填上后继续搜索 当所有格子都填上后 计算一下总分 如果总分大于当前最优值就更新最优值这样大约可以得35分 我们还可以对上面的想法进行改进 我们可以先计算出每个格子的选择数先确定可选择数小的格子即先把只有一种选择的格子确定下来再确定有两种选择的格子 从而避免搜索到过多无法得到可行方案的状态这样大约可以得75分 对于这道题 由于数据的原因 如果从右下角到左上角枚举 可以得到90分左右 如果再加上一个叫做卡步的东西 我们可以得到100分 什么是卡步 我们发现搜到一个可行的方案是很快的 时间主要用于更新最优解 卡步就是当执行的步数到达一定值时 若程序还没有结束 那么我们就直接输出搜到的最优解 并退出 这个值很有可能不是最优的 但若继续搜索下去必然会超时 所以我们直接退出 这是在比赛中常用的技巧 如何卡步 最简单的办法就是在过程dfs中加入inc p ifp thenbeginwriteln ans halt end 本题可以用搜索 卡步得到100分 很重要的原因是这道题测试数据的特殊性 如果要使程序能通过任何数据 可以采用位运算加速搜索和Dancing links 但这两种方法在联赛范围内基本不会出现 我们不进行深入讨论 另外还用一种方法可以得到100分 根据当前状态确定每个格子的选择数 我们之前有一个想法是按选择数从少到多搜索 但当我们确定下一个格子的数字后 会影响其它格子的选择 使它们的选择数减少 所以我们可以在搜索的时候计算格子的选择数 从当前选择数最少的格子开始搜索 programsudoku constz array 1 9 1 9 oflongint 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 4 4 4 5 5 5 6 6 6 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 7 7 7 8 8 8 9 9 9 7 7 7 8 8 8 9 9 9 fenshu array 1 9 1 9 oflongint 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 6 6 7 8 8 8 8 8 7 6 6 7 8 9 9 9 8 7 6 6 7 8 9 10 9 8 7 6 6 7 8 9 9 9 8 7 6 6 7 8 8 8 8 8 7 6 6 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 vari j ans t longint map array 0 9 0 9 oflongint hang lie ge array 1 9 1 9 ofboolean x y array 0 81 oflongint c array 0 81 ofboolean procedurecalc 计算总分vari j s longint begins 0 fori 1to9doforj 1to9dos s map i j fenshu i j ifs ansthenans s end proceduredfs k longint varxx yy i min w j p longint beginifk tthenbegincalc exit end min maxlongint fori 1totdoifc i thenbeginw 0 forj 1to9doifhang x i j andlie y i j andge z x i y i j thenbegininc w ifw minthenbreak end ifw minthenbeginp i min w end end 找出当前选择最少的 xx x p yy y p c p false fori 1to9do 枚举填哪个数ifhang xx i andlie yy i andge z xx yy i thenbeginmap xx yy i hang xx i false lie yy i false ge z xx yy i false dfs k 1 hang xx i true lie yy i true ge z xx yy i true map xx yy 0 回溯end c p true 回溯end beginans 1 t 0 fillchar hang sizeof hang true fillchar lie sizeof lie true fillchar ge sizeof ge true fori 1to9doforj 1to9dobeginread map i j ifmap i j 0