造福一下后入

首先是常规的警示后入，主要是退火部分的细节，~~估计没啥用的但是~~。

如果你在退火过程中采用的是随机选取两个位置然后交换，要是没有采用本次答案记得把它换回来，不然你会炸掉。
注意你的 calc 函数，也就是算 $q$ 的那个，要判越界，以及最后的 $cnt$ 别忘了 $\div 2$ 。
注意你的概率判断，是有 $e^{\frac{\Delta f }{T}}$ 的概率接受而不是拒绝！也就是注意你的大于小于号有没有写反。~~总之本人是被坑过的 TAT~~
答案的染色情况要和当前的染色情况一定要分两个数组存，不然你最后输出的是当前染色情况而并非最优，那你就炸了。

接下来我说点让你代码更稳定的方法，用处大不大我不知道啊，~~没用别怪我~~。

在退火过程中，如果你可以较为快速地判断你这次变动之后是否与原来相同的话，如果相同你可以考虑 continue 防止浪费时间。
如果你在退火过程中采用的是随机选取两个位置然后交换，没必要每次交换之后都重新算一次 $p$ ，只需要用常数的时间复杂度枚举你要交换的两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 分别四周的点的情况作加减即可。
注意你初始温度、退火速度的和温度下界的设置，本人采用的是初始温度 $1.0$ 退火速度 $0.99999$ 温度下界 $10^{-15}$ 。注意如果你要使用本人的参数，请你一定执行第 2 条，不然 T 了别来找我。

嗯，最后为了方便大家借鉴，给大家看看我核心的 SA 部分的代码：

CPP

void solSA(){
    LD T=1.0;int nowq=Ans.nq;
    //这边我把 Ans 开了个结构体，nq 是当前 q 的最优值，h 是一个二维数组存染色情况
    while(T>eps){
        int x=rand()%n+1,y=rand()%m+1;
        int x2=rand()%n+1,y2=rand()%m+1;
        if(a[x][y]==a[x2][y2])continue;
        int ord=0,nwl=0;
        //下面用到的 dx 和 dy 均为方向数组
        for(int k=0;k<4;k++)
            ord+=(a[x+dx[k]][y+dy[k]]!=a[x][y]),
            ord+=(a[x2+dx[k]][y2+dy[k]]!=a[x2][y2]);
        swap(a[x][y],a[x2][y2]);
        for(int k=0;k<4;k++)
            nwl+=(a[x+dx[k]][y+dy[k]]!=a[x][y]),
            nwl+=(a[x2+dx[k]][y2+dy[k]]!=a[x2][y2]);
        int newq=nowq-ord+nwl;
        if(newq<=nowq||exp((LD)(nowq-newq)/T)>Probly())nowq=newq;
        //Probly() 函数用于生成一个在 [0,1] 范围内的随机浮点数
        else swap(a[x][y],a[x2][y2]);
        if(nowq<Ans.nq)updAns(nowq);T*=D;
    }return;
}

希望能起点作用喵！

讨论操作

回复

相关推荐

造福一下后入