搜索题的调试技巧以及一些附加内容

Posted on 2012-03-22 20:49 Mato_No1 阅读(612) 评论(1)  编辑 收藏 引用 所属分类: 搜索
【背景(神犇不要鄙视)】
本沙茶在搜索题目的调试上已经挂过两次了(NOI2011的game用了2h+木有调出来,还耽误了继续想show的时间,结果被挡在了集训队门外;NOIP2011的mayan,用暴搜都调了2h+,木有调出来,结果惨挂,全国第200名,如果这题AC了就是全国前50名……),为了防止在接下来的比赛中再在这里挂掉,本沙茶决定好好搞一下这个。

【DFS的调试技巧】
如果决定一道题用DFS捉,那么:
(1)如果能套经典模型(当然本沙茶目前只会一个经典模型:DLX),就写经典模型(DLX应该不会写疵的,即使疵了,也很容易调试的囧)
(2)如果不能,上来先写暴搜,并命名为0号版本;
(3)i号版本调试正确之后,再去加剪枝,每次只加一个剪枝(如果时间来不及了,就按照由强到弱或者由好写到难写的顺序来),调对了再加下一个,每加一个都开一个新的版本;
(4)调试时,如果出现的是RE或者死循环,就在出错的状态处停止,并检查其所有的祖先状态(显然这需要记下每次的决策),看看这些决策是否合法;
(5)如果程序正常结束,但结果错误,又分为以下3种情况:
<1>明明有解,输出无解:可以把正解的各个决策一步一步代入,看看程序里面是在哪一步出了问题(明明合法的决策它木有作出),从而方便检查;
<2>输出不合法的解:可以把形成这个不合法解的决策一步一步代入,看看是哪一步出了问题;
<3>输出合法但非最优的解:必然是某些最优性剪枝错误或者最优性判断出了问题,可以直接到这些地方去检查,实在不行也可以把最优解代入检查;
(6)当然,在动态查错之前,要认真地读一遍代码;
(7)有时也可以用分段检查的方法,即把代码中的各个过程或者片段截取下来,将几组小的输入代入,看看执行之后,所有在该片段里改变了值的全局变量是否正确,进而发现这里的错误;
(8)千万不要一下子输出全部的状态!本沙茶在比赛中用的就是这种办法,结果不仅木有查出来,还把自己绕晕掉了,最后时间到了连删printf的时间都木有……事实上,只有在状态总数不太多,且相对关系明了、顺序整齐的时候(比如一般的DP等),可以一下子输出全部状态来检查,否则就不能这么搞;

【BFS的调试技巧】
BFS其实是比DFS要好调得多,因为所有的状态都储存在队列里,因此,可以在状态结点中记下每个点的FA(前趋状态),然后,哪里出了问题,就把前趋状态全部搞出来即可,另外,BFS一般木有“剪枝”这一说(除了判重),且决策过程一般是比较整齐的,因此好调;

【例题】
(1)NOIP2011 mayan(无比痛苦的回忆啊啊……)
不用信WJMZBMR的题解(什么“最小表示法”……),这题其实不用加过多剪枝,只需要加以下2个剪枝即可:
<1>如果某种颜色只剩下1或2个,剪枝;
<2>(这个其实不是剪枝)在决策的时候,对于两个相邻的方块,把左边的往右移与把右边的往左移是等价的,又因为往右移优先,所以在枚举决策的时候,除非某方块左边是空格,否则不要把它往左移;
本题主要是在移动后的消去处理过程(sol0)中比较容易出问题,因此对于这里重点查一下即可,此外,字典序是按照先列后行再移动方向的顺序进行的,不要搞疵;
代码(RQNOJ实测结果:最慢的点1.2s左右):
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int n = 7, m = 5, MAXC = 11, MAXP = 5, INF = ~0U >> 2;
int P, A[n][m], s[MAXP][3], res[MAXP][3], T[n], sum[MAXC];
bool B[n][m], res_ex = 0;
void init()
{
    freopen(
"mayan.in""r", stdin);
    scanf(
"%d"&P); int x, len;
    re(i, m) {len 
= 0while (1) {scanf("%d"&x); if (x) A[len++][i] = x; else break;}}
    fclose(stdin);
}
bool sol0()
{
    re(i, n) re(j, m) B[i][j] 
= 0;
    
int x, len;
    re(i, n) re2(j, 
2, m) if (A[i][j] && A[i][j] == A[i][j - 1&& A[i][j] == A[i][j - 2]) {
        B[i][j] 
= B[i][j - 1= B[i][j - 2= 1; x = j - 3;
        
while (x >= 0 && A[i][j] == A[i][x]) x--;
        re2(k, x
+1, j-2) B[i][k] = 1;
    }
    re(j, m) re2(i, 
2, n) if (A[i][j] && A[i][j] == A[i - 1][j] && A[i][j] == A[i - 2][j]) {
        B[i][j] 
= B[i - 1][j] = B[i - 2][j] = 1; x = i - 3;
        
while (x >= 0 && A[i][j] == A[x][j]) x--;
        re2(k, x
+1, i-2) B[k][j] = 1;
    }
    
bool FF = 0; re(i, n) re(j, m) if (B[i][j]) {FF = 1; A[i][j] = 0;}
    
if (FF) {
        re(j, m) {
            len 
= 0; re(i, n) if (A[i][j]) {T[len++= A[i][j]; A[i][j] = 0;}
            re(i, len) A[i][j] 
= T[i];
        }
    }
    
return FF;
}
void solve(int v)
{
    
if (v == P) {
        re(i, m) 
if (A[0][i]) return;
        res_ex 
= 1; re(i, P) re(j, 3) res[i][j] = s[i][j];
    } 
else {
        re(i, MAXC) sum[i] 
= 0;
        re(i, n) re(j, m) sum[A[i][j]]
++;
        re2(i, 
1, MAXC) if (sum[i] == 1 || sum[i] == 2return;
        
int tmp, len, A0[n][m];
        re(i, n) re(j, m) A0[i][j] 
= A[i][j];
        re(j, m) re(i, n) 
if (A[i][j]) {
            
if (j < m - 1) {
                tmp 
= A[i][j]; A[i][j] = A[i][j + 1]; A[i][j + 1= tmp;
                re(j0, m) {
                    len 
= 0; re(i0, n) if (A[i0][j0]) {T[len++= A[i0][j0]; A[i0][j0] = 0;}
                    re(i0, len) A[i0][j0] 
= T[i0];
                }
                
while (sol0()) ;
                s[v][
0= j; s[v][1= i; s[v][2= 1;
                solve(v 
+ 1); if (res_ex) return;
                re(i0, n) re(j0, m) A[i0][j0] 
= A0[i0][j0];
            }
            
if (j && !A[i][j - 1]) {
                tmp 
= A[i][j]; A[i][j] = A[i][j - 1]; A[i][j - 1= tmp;
                re(j0, m) {
                    len 
= 0; re(i0, n) if (A[i0][j0]) {T[len++= A[i0][j0]; A[i0][j0] = 0;}
                    re(i0, len) A[i0][j0] 
= T[i0];
                }
                
while (sol0()) ;
                s[v][
0= j; s[v][1= i; s[v][2= -1;
                solve(v 
+ 1); if (res_ex) return;
                re(i0, n) re(j0, m) A[i0][j0] 
= A0[i0][j0];
            }
        }
    }
}
void pri()
{
    freopen(
"mayan.out""w", stdout);
    
if (res_ex) re(i, P) printf("%d %d %d\n", res[i][0], res[i][1], res[i][2]); else printf("%d\n"-1);
    fclose(stdout);
}
int main()
{
    init();
    solve(
0);
    pri();
    
return 0;
}

(2) 小木棍(整数分组模型)
经典的DFS剪枝题。需要很多很强的剪枝:
<1>枚举最后形成木棍(以下简称大木棍)的长度P的时候有限制,这个就不说了;
<2>所有相同长度的木棍都要合并,最终所有木棍按照长度递减存在数组里面,在枚举的时候只需枚举这个木棍使用的个数,且从大到小枚举;
<3>为了减少枚举量,要用Dancing Link优化;
<4>很显然,枚举每根大木棍的时候,目前剩下的最长的木棍肯定要至少使用一次,且如果该长度的木棍使用了K次,则以后的所有大木棍都最多只能使用K次(除非该长度的木棍被用完了),这是用字典序保证不重复枚举;
<5>要加上一个强剪枝:如果目前加上一个(只能一个)长度为L的木棍以后,恰好拼成一个完整的大木棍,但是之后失败了,此时就不用再枚举接下来更短的木棍了,因为如果用它们得到了解,则把它们与一个长度L的木棍交换也是可行解;
<6>只要倒数第2根大木棍拼成了,就找到了解,因为剩下的肯定能拼成最后一根;
由于这题的剪枝很多,很繁琐,极易出错,因此写的时候要非常小心,查错也很麻烦囧……

代码(PKU上0ms,UVA上144ms):
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int n = 50, INF = ~0U >> 2;
int P, P0, A[n + 1], L[n + 1], R[n + 1];
bool res_ex;
void prepare()
{
    L[
0= R[0= 0; re1(i, n) if (A[i]) {L[i] = L[0]; R[i] = 0; L[0= i; R[L[i]] = i;}
}
void solve(int dep, int len, int K, int x1)
{
    
if (dep == P0) res_ex = 1else {
        
int len0, s0;
        
if (len == P) {
            
int maxv = L[0];
            s0 
= len / maxv <= A[maxv] ? len / maxv : A[maxv]; if (s0 > x1) s0 = x1;
            len0 
= len - (s0 + 1* maxv;
            rre1(i, s0) {
                
if ((P0 - dep + 1* i < A[maxv]) return;
                A[maxv] 
-= i; if (!A[maxv]) {L[R[maxv]] = L[maxv]; R[L[maxv]] = R[maxv];} len0 += maxv;
                
if (len0) solve(dep, len0, L[maxv], A[maxv] ? i : INF); else {
                    solve(dep 
+ 1, P, 0, x1);
                    
if (i == 1 && !res_ex) {
                        
if (!A[maxv]) L[R[maxv]] = R[L[maxv]] = maxv;
                        A[maxv] 
+= i; return;
                    }
                }
                
if (res_ex) return;
                
if (!A[maxv]) L[R[maxv]] = R[L[maxv]] = maxv; A[maxv] += i;
            }
        } 
else {
            
int i = K;
            
while (i) {
                
if (A[i] && i <= len) {
                    s0 
= len / i <= A[i] ? len / i : A[i];
                    len0 
= len - (s0 + 1* i;
                    rre1(j, s0) {
                        A[i] 
-= j; if (!A[i]) {L[R[i]] = L[i]; R[L[i]] = R[i];} len0 += i;
                        
if (len0) solve(dep, len0, L[i], x1); else {
                            solve(dep 
+ 1, P, 0, x1);
                            
if (j == 1 && !res_ex) {
                                
if (!A[i]) L[R[i]] = R[L[i]] = i;
                                A[i] 
+= j; return;
                            }
                        }
                        
if (res_ex) return;
                        
if (!A[i]) L[R[i]] = R[L[i]] = i; A[i] += j;
                    }
                }
                i 
= L[i];
            }
        }
    }
}
int main()
{
    
int n0, x, sum, maxv;
    
while (1) {
        scanf(
"%d"&n0); if (!n0) breakelse {sum = 0; maxv = 0; re1(i, n) A[i] = 0; res_ex = 0;}
        re(i, n0) {scanf(
"%d"&x); A[x]++; sum += x; if (x > maxv) maxv = x;} prepare();
        re3(i, maxv, sum) 
if (!(sum % i)) {
            P 
= i; P0 = sum / i - 1; solve(0, P, 0, INF);
            
if (res_ex) {printf("%d\n", i); break;}
        }
    }
    
return 0;
}

【附加内容】
在mayan的代码中有一个数组A0,用于在过程中备份A数组,使得它在下面搜索失败之后能及时更新(因为这里的A经历了sol0处理,更新比较麻烦),这种备份数组在很多题里面都有应用,不过要注意,这个数组一定要写成局部的,不能写成全局的!!(本沙茶在比赛的时候就是写成全局的了,结果导致出错查不出来的……)如果怕写成局部的MLE,也可以写成全局的,但是要分层,即对于每个搜索深度(v、dep等变量控制),要开专门的一层,保证搜索过程中各层不互相覆盖。

Feedback

# re: 搜索题的调试技巧以及一些附加内容  回复  更多评论   

2012-03-25 20:57 by 浅栖
2011NOIP参加过的握手。。。想去年我也是暴搜调了不知道多久,最后差点就放弃了。。。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理