• 这条要放在最前面,因为学会做一个有胸怀有智慧的人,比单单只学会一两个算法,或者一两门技术要重要的多。无论身在何地,永远都要做最好的自己!

引用开复GG的话:成才者和成功者往往都有拿得起,放得下的胸襟和气魄。也就是,要在五个方面体现出超出常人的能力和品质:

1.务实:学会接受那些自己无法改变的人和事,有勇气和毅力挑战个人的极限,而不怨天尤人

2.宽恕:善于发现别人的优点,也善于接受别人的缺点;我加一点,学会用智慧的耳朵来慎思明辨,学会把看到与自己相左意见的闪光点

3.自律:学会控制自己的情绪,不要让自己的失态影响到别人;我加一点,学会在迥然不同的意见面前,保持冷静智慧的头脑

4.尊重:能够接受,支持和包容别人的不同意见

5.涵养:不过分计较得失成败,不会因一时一地的利益,或一人一事的欲求而自乱方寸

这些话之所以对,不是因为他出自开复GG的文集,而且由于每一位真正成功,或者说做到真正最好的自己的人,都有上面的品质!

  • 问题1:对于两个数a,b,如何判断它们是否存在同为1的位?只用位操作实现。

测试result=((1<<n)-1)&(~(a^b)&a)是否为0即可。~(a^b)中相同位为1,不同位为0,作为掩码&a之后,a只剩下与b相同的位,若与b相同的位为0,则自然为0;若为1,则必然剩下有为1的位。OK,result>0时存在同为1的位,反之不存在。

这样我就实现了O(1)操作来判断两个标志位段是否有交叠!常识性代码

  • 剩下的问题就很简单了,水题而已!我想了下,如果用IB来做的话,代码实现稍微有点麻烦,所以用了个最笨的办法,先求解所有的24点方案,这个没有优化过,测试过很多牌点都有重复!唯一的技巧在于,我用bitset作了一个状态位的标志,这样测试两个方案之间是否有重叠的牌时,我就可以用问题1的解决方法来做了。IB的话,代码会有点麻烦,没想清楚怎么写。
  • 大概框架如下:

do{//有点类似于AB-SSS*的实现,行了这道题目确实有太多水分料!

int pre=depth;

dfs(depth);//for depth-1, depth

}while(pre!=depth);

试题3. 外公的难题
题目叙述:

   Happy老爷爷的外孙Jacky能写会算,聪明绝顶,老爷爷非常喜欢他。Jacky最喜欢算24点了,可是因为他的知识还不够,他只会做加法,减法和乘法,另外也会使用括号。这次外公给他出了一道难题:从N张牌中任选若干张分成M墩( 每墩不超过5张牌),使得每墩的各张牌都可以算出24点。这本来并不困难,但是外公又要求M的值最大,这可难坏了小Jacky。你愿意帮帮他吗?

输入数据
:   
     输入文件puzzle.in 中共有两行,第一行包含一个数n(1<=n<=20),表示牌的张数。第二行有N个数依次为各张牌的点数,每个数为1~10的整数,以空格分开。
输出数据:
     输出文件puzzle.out 中仅有一个数为M的最大值.
输入输出样例:

没啥好说的,水了!

GNU:0.519s,这道题目够简单的了,连优化都不想了!

#include <iostream>
#include <fstream>
#include <math.h>
#include <bitset>
using namespace std;

const int MAXEL=30;
const double ZERO=1e-6;
double dot[MAXEL];
unsigned long stra[MAXEL];
typedef struct SNode{
    unsigned long bits;
    int nums;
}SNode;
SNode slist[MAXEL];
int n, maxM, len;
#define OVERONE(a, b, n) ((((1<<n)-1)&(~(a^b)^a))>0)

//declaration
void dfs(int i);
void stadfs(int i, int total);

//implementation
void dfs(int i){
    if(i==n-1||fabs(dot[i]-24.0)<ZERO){
        if(fabs(dot[i]-24.0)<ZERO){
            bitset<32> cur=stra[i];
            int j=len, key=cur.count();
            for(;j-1>=0&&key<=slist[j-1].nums; j–){
                if(key==slist[j-1].nums&&stra[i]==slist[j-1].bits)
                    return;
                slist[j]=slist[j-1];
            }
            slist[j].bits=stra[i], slist[j].nums=key;
            len++;
        }
        return;
    }
    //foreach item of a and b in  the [i…n-1]
    for(int a=i; a<n; a++){
        for(int b=a+1; b<n; b++){
            double a1=dot[a], b1=dot[b];//why to backup?
            unsigned long str1=stra[a], str2=stra[b];
            //back for b
            dot[i]=dot[b], stra[i]=stra[b];
            //+, b>i, next slot domain
            dot[b]=a1+b1;
            stra[b]=(str1|str2);
            dfs(i+1);
            //plus –
            dot[b]=a1-b1;
            stra[b]=(str1|str2);
            dfs(i+1);
            //reverse –
            dot[b]=b1-a1;
            stra[b]=(str1|str2);
            dfs(i+1);
            //*
            dot[b]=a1*b1;
            stra[b]=(str1|str2);
            dfs(i+1);
            // /
            if(b1!=0.0){
                dot[b]=a1/b1;
                stra[b]=(str1|str2);
                dfs(i+1);
            }
            if(a1!=0.0){
                dot[b]=b1/a1;
                stra[b]=(str1|str2);
                dfs(i+1);
            }
            //recovery for each
            dot[a]=a1, dot[b]=b1;
            stra[a]=str1, stra[b]=str2;
        }
    }
}
void stadfs(int i, int total){//stra[i]
    if(i==len){
        if(total>maxM) maxM=total;
        return;
    }
    for(int k=i; k<len; k++){
        if(k!=i){
            SNode tmp=slist[i]; slist[i]=slist[k]; slist[k]=tmp;
        }
        if(i==0||!OVERONE(slist[i-1].bits, slist[i].bits, len)){//just a minute
            if(total+(len-i)>maxM)
                stadfs(i+1, total+1);
        }
        if(k!=i){
            SNode tmp=slist[i]; slist[i]=slist[k]; slist[k]=tmp;
        }
    }
}

#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif

    //implementation
    cin>>n;
    for(int i=0; i<n; i++) cin>>dot[i];
    len=0;
    dfs(0);
    if(len>0){
        maxM=INT_MIN;
        stadfs(0, 1);
    }
    else maxM=0;
    cout<<maxM<<endl;

    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase

路径寻找问题:

  • 迭代加宽搜索:逐步扩大搜索范围,DFID,IDA*以及IB算法[时间换空间算法,如果要存储所有状态,似乎不现实,而且内存也有限制,因此用多次计算的时间来换取空间状态]。而上面的题目就是一定典型的IB算法题目,只是考虑到无解情况,所以用两次搜索来减少空间,实际上IB框架内,可以用搜索范围参数在范围中用dfs来验证24解是否存在。OK,不说了,我估计写出来不会很理想,可以想象大量的搜索范围内实际上是无解的,人品在分组中不起任何作用!除非数据异常好,但年历回溯对于任何数据都有N!,所以还是一次预处理要好得多。
  • 局部修改法:这个比较重要,但最经典的模型“L-game”本菜还没写出来,惭愧中!构造方法:1。对称性状态合并[L-Game的一个正向状态,等价于逐次旋转90度之后,得到的连续三个状态,因此,我们对一个状态的f估计可以代替其他三个状态,大大减少了总的状态空间。以L-Game为例,相当于K^4->K;2。估价函数的合理抛弃[算符相关计算,当前op1算符和扩展算符op2之间必须存在一定的相关参数,否则做出的决策会影响解的质量]
  • 搜索任务分解1。MinMin过程,以及带参数修正的Realtime-A*算法[和博弈问题的模式比较相似,只是Realtime-A*在撤销状态回溯时,要带上一个修正因子以此来更正上一次的试探搜索];2。分阶段搜索,这个没啥好说的,典型的退化模型就是多项式的动规算法或者带重叠子问题的解答树;3。实际搜索里面,有一种叫“二次搜索”的算法,我可以在第一次搜索时,认为忽略一些比较耗时的基本操作,然后把这些基本操作作为下一次新搜索的状态。[这个很有趣,怎么才算耗时呢,有个估价函数吧!]

约束满足问题[CSP]:

  • 年历回溯算法:朴素的搜索框架,递归版本和迭代版本都差不多;“N后问题”,关键点:搜索顺序结点扩展顺序

但这里有几个非常重要的观念要理解,首先是CSP的算法递进模型,实际上是将问题映射为一个约束图,然后对于一个Xi引出一条解弧,这样随后的扩展过程中,生成的约束弧就可以进行相容性测试,并且不断修正每个解的值域,直到生成最终的!参见CSP相关问题理论.

因此这种朴素的算法就有了如下的递进解决方案:

  • BT->FC[单层约束]->AC3/4[约束扩展]!
  • 在扩展每层结点时,有如下方法:1.MRV[最少剩余值,剩的少,那么很快就失败了];2.最少约束值[约束值少,等价于值域最宽,解的可能性最大]

本菜学习到的思想:在考虑一个问题的时候,正向和反向的两种思路,都是优化的切入点!

  • 限制差异性搜索[Limited Discrepancy Search],是一种基于f的递进修正贪心方案,第一次迭代,我取K=0,好,这是贪心的;第二次呢,那补上第一没走的,让第二节点多走一次[2次],直到后面.纯理论我确实没兴趣,DDS就不说了,可以去查论文.
  • 启发性修补[Heurisic Repair],又是一个典型问题的解决方案,对于N-queen而言,是一个很好的解决方法.但考虑到下一篇,本菜要总结下N-Queen的算法.先打住!

Advertisements