回溯法之符号三角形问题

问题描述

题目分析

对于符号三角形问题，用n元组x[1:n]表示符号三角形第一行的n个符号，由于我们只有两种符号——"+“或”-"，所以取值是一个二值问题，如果取"+“我们就假设x[i]=1，如果取”-“我们就设x[i]=0。所以这显然是一个解空间为子集树的问题。我们不需要每次都遍历到树的叶节点，可以通过剪枝来节约时间。
明确了解空间以后，我们要确定的就是约束函数。由于”+“和”-“数目相同，且我们的符号三角形有n行，所以总共有n(n+1) / 2个符号，因此每个符号只能有n(n +1) / 4。所以n(n+1)/2如果为奇数的话我们就要淘汰掉这种情况。
我们用sum表示合理的符号三角形的数目。count来统计其中的”+“和”-"，如果是"+"我们将count+1，否则将count+0，最后用count与n(n+1)/4比较即可。
在这里我还是想要说明几个细节:
1.回溯问题我们应该回溯的是什么?
我们应该回溯的是状态，这个状态指的是我们在做了选择之后发生改变的变量，简而言之 就是约束函数约束的变量。这道题里，我们做出了选择,p[1][t]=i,于是我们就会马上让count+i，因为i如果等于0.则为负号，count自然不用加。当i=1时，符号为正号，count+1。所以我们改变的是count，而却count也是约束函数约束到的变量，所以我们在回溯过程中应该将其恢复原来的状态
2.回溯问题有没有更直接清晰的模板？
之前我们说过的子集树或排列树的解空间的模板都是分情况的更细致的模板，但其实回溯法也有一个更直接清晰的模板:

int Backtrack(i)
{
	for(穷举所有能做的选择)
	{
		做选择
		回溯(Backtrack(i+1))
		撤销选择(约束函数约束的变量恢复原状态)
	}
}

还有一些实现上需要注意的地方，在代码里都有详细注释。

代码

#include <iostream>
using namespace std;
class Triangle
{
    friend int Compute(int);//计算符号三角形个数的函数
    private:
        void Backtrack(int i);
        int half,//符号三角形中符号数目的一半
            **p;//符号三角形矩阵
            n,//第一行符号个数
            count;//当前"+"的个数
        long sum;//符号三角形的符号个数(防止符号过多,声明为long类型) 
};
void Triangle::Backtrack(int t)
{
    //可行性约束
    if(t > n)
    {
        sum++;
    }
    //约束函数
    if(count > half || t*(t - 1) / 2 - count > half)
    //判断"+"和"-"是否都超过了一半
    {
        return;
    }
    for(int i = 0;i <= 1;i++)
    {
        //从上往下,最上面是第一行
        //一定要给一个初始值
        p[1][t] = i;
        count += i;
        for(int j = 2;j <= t;j++)
        {
            //这里可能有一些难推导，第t列的这个符号只能影响下面几行t列之前的符号
            //如果当前行为k,下面的行数为j，则t最多可以影响到的列数为t-(j-k)即为t-j+k
            //在一行中即为t-j+1
            p[j][t-j+1] = p[j-1][t-j+1] ^ p[j-1][t-j+2];
            count += p[i][t-j+1];//只能为0或者1
        }
        Backtrack(t + 1);
        //回溯
        //这里的回溯不需要将p[1][t]-=i,因为我们外层是有循环的,所以回到原地后下次循环会重新给p[1][t]一个数值的
        //在子集树中,我们只回溯最终的结果(如装载问题的最优容量和当前重量，这道题目的当前正号数目等),
        //并不会回溯选择的0或者1,因为在回溯回来的时候我们会改变它的
        //回溯的时候我们只找那些约束函数约束的变量来恢复到原状态,如本题的count
        for(int j = 2;j < = t;j++)
        {
            count -= p[j][t - j + 1];
        }
        count -= i;
    }
}
int Compute(int n)
{
    Triangle X;
    X.n = n;
    X.half = n(n+1) / 2;
    X.sum = 0;
    if(X.half % 2 == 1)
        return 0;
    X.half = X.half / 2;
    X.count = 0;
    //二维数组,记录符号三角形
    int **p = new int *[n + 1];
    for(int i = 0;i <= n;i++)
        p[i] = new int [n + 1];
    for(int i = 0;i <= n;i++)
    {
        for(int j = 0;ij<=n;j++)
            p[i][j] = 0;
    }
    X.p = p;
    X.Backtrack(1);
    return X.sum;
}

总结

计算可行性约束需要O(n)的时间（因为1行有n个元素，我们需要对这个n个元素进行依次搜索并回溯，直到i > n才能sum++），而我们的解空间为子集树，结点个数为2^n
所以我们的时间复杂度为O(n2^n)