第十七关——搜索优化

  • 拓扑排序

定义：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序(Topological Sort),是将G中所有顶点排成一个线性序列,使得对图中任意一对顶点u和v,若＜u,v＞∈E(G),则u在线性序列中出现在v之前。通常将这样的线性序列称为满足拓扑次序(Topolgical Order)的序列,简称拓扑序列。

算法流程：

  1. 建立空的拓扑序列a

  2. 预处理出所有点的入度deg[i]，期初把所有入度为0的点加入队列

  3. 取出队头结点x，把x加入拓扑序列a的末尾

  4. 对于从x出发的每条边（x,y），把deg[y]减1.若degp[y]=0，则把y入队

  5. 重复直到队列为空，此时a为所求拓扑序列

#include<bits/stdc++.h>
const int N=10001;
using namespace std;
int n,m,a[N],ver[N],next[N],head[N],tot,deg[N],cnt; 
void add(int x,int y){//领接表存图，添加一条有向边 
    ver[++tot]=y;next[tot]=head[x];head[x]=tot;deg[y]++;
}
void top(){
    queue<int> q;
    for(int i=1;i<=n;i++)
    if(deg[i]==0)q.push(i);
    while(q.size()){
        int x=q.front();q.pop();
        a[++cnt]=x;
        for(int i=head[x];i;i=next[i]){
            int y=ver[i];
            if(--deg[y]==0)q.push(y);
        }
    }
}
int main()
{
    cin>>n>>m;//点数、边数 
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    top();
    for(int i=1;i<=cnt;i++)
    cout<<a[i];
    return 0;
 }
View Code

  • 迭代加深

首先深度优先搜索k层，若没有找到可行解，再深度优先搜索k+1层，直到找到可行解为止。由于深度是从小到大逐渐增大的，所以当搜索到结果时可以保证搜索深度是最小的。这也是迭代加深搜索在一部分情况下可以代替BFS（还比BFS省空间）。

前提：题目一定要有解，否则会无限循环下去。

当有一类问题需要做广度优先搜索，但却没有足够的空间，而时间却很充裕，碰到这类问题，我们可以选择迭代加深搜索算法。

比如有这样一类题让你在这类题里面找到最小的解就可以。(通常情况下迭代加深搜索的题都是有解，只是解的大小问题)，怎么样写这个呢？其实就是深搜控制了深度，搜索历程就是先搜索深度为1的所有情况，看看能不能达到最终目标，如果能达到最终目标，结束搜索。如果不能继续增加可以搜索的深度，但是前面所有的搜索的结果不会被保存，下一次深度加1继续从头开始搜虽然看起来好像干了很多重复的事情，其实不是的，当你搜索第k的深度的时候，前面k-1深度的所有情况都不值得一提。这也就是为什么迭代加深不会像广搜一样超出内存，并且时间上并不比广搜慢太多。

  • 搜索剪枝

DFS 的时间复杂度特别高。通常都不会是正解，所以一般都只能骗一部分的分，所以剪枝就是为了骗更多的分。

下面为dfs的一个模板，然后后面的几种具体剪枝方法会根据此模板修改

int ans = 最坏情况, now;  // now为当前答案
void dfs(传入数值) {
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

ans 可以是解的记录，那么从当前解与已有解中选最优就变成了输出解。

这里，最常用的剪枝分为搜索优化顺序、排除等效冗杂、记忆化搜索、最优性剪枝、可行性剪枝。

剪枝思路：

  极端法：考虑极端情况，如果最极端（最理想）的情况都无法满足，那么肯定实际情况搜出来的结果不会更优了。

  调整法：通过对子树的比较剪掉重复子树和明显不是最有“前途”的子树。

  数学方法：比如在图论中借助连通分量，数论中借助模方程的分析，借助不等式的放缩来估计下界等等。

搜索顺序优化

在一些问题中，搜索树的各层次，各分支之间的顺序不是固定的，有时调换顺序会使时间复杂度相对减少

排除等效冗杂

在搜索过程中，如果我们能够判定搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么便只需要对一条子树进行搜索。

记忆化搜索

记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回，就相当于标记一个节点是否被访问过。

模板：

int g[MAXN];  //定义记忆化数组
int ans = 最坏情况, now;
void dfs f(传入数值) {
  if (g[规模] != 无效数值) return;  //或记录解，视情况而定
  if (到达目的地) ans = 从当前解与已有解中选最优;  //输出解，视情况而定
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}
int main() {
  ... memset(g, 无效数值, sizeof(g));  //初始化记忆化数组
  ...
}

 例题：摆渡车//886

#include<bits/stdc++.h>
using namespace std;
int read()//快读 
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,m,t[505],f[505][505];//f[i][j]第i个人等待j的时间 
//因为0<=st-t[i]<=m，因此可以记忆化，把这个作为状态的第二维 
int solve(int i,int st)//记忆化搜索。i：第i个人，st：开始时间st 
{
    if(i==n+1)//所有人都上车了 
    return 0;//便不再有等待时间了 
    if(st<t[i])//如果现在的时间没有人，就到下一个人的到达时间 
    return solve(i,t[i]);
    //这一句和上一句的顺序不能换,不然数组越界会RE    
    if(f[i][st-t[i]])//记忆化 
    return f[i][st-t[i]];
    int sum=0,j=i;//j从i开始 
    //车等人 即车到的时间在这个人的后面 
    while(j<=n && t[j]<=st)//车一到,该上的人就上,就不再等了 
    sum+=t[j++];//这里j++所以下面是j,而再下面是j+1 
    int best=st*(j-i)-sum+solve(j,st+m);//i到j这一段的再加上后面的(可以看做是一个累加过程) 
    //人等车 即人到的时间在车的后面
    for (;j<=n;j++)//让车再等一下,多加后面的人上车 
    {//j一直枚举到n,连把人等完 
        sum+=t[j];
        best=min(t[j]*(j-i+1)-sum+solve(j+1,t[j]+m),best);
    }
    return f[i][st-t[i]]=best;
}
int main()
{
    //memset(f,-1,sizeof(f));
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        t[i]=read();
    sort(t+1,t+n+1);//显然从小到大按照时间排序更好算 
    printf("%d",solve(1,0));
    return 0;
}
View Code

可行性剪枝

可行性剪枝也叫上下界剪枝，其是指在搜索过程中，及时对当前状态进行检查，若发现分支已无法到达递归边界，就执行回溯。

即该方法判断继续搜索能否得出答案，如果不能直接回溯。

就好比我们在道路上行走，如果远远看到前方已经是一个死胡同了，就应该立即折返，而不是走到路的尽头再返回。

模板：

int ans = 最坏情况, now;
void dfs(传入数值) {
  if (当前解已不可用) return;
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

例题：靶形数独//1056//洛谷1074

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 11
#define MOD 123
#define E 1e-6
using namespace std;
int g[N][N];
int grade[10][10]{
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6},
};
int area[10][10]{
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
};
struct Node{
    int x;
    int y;
}point[N*10];
int vis_x[N][N],vis_y[N][N],vis_g[N][N];
int vis[N*10];
int n,sum;
void dfs(int k)
{
    if(k>n)//当确定的数字个数大于未填入的数字总数时
    {
        int cnt=0;
 
        for(int i=1;i<=9;i++)//记录分值
            for(int j=1;j<=9;j++)
                cnt+=g[i][j]*grade[i][j];
 
        sum=max(sum,cnt);//取最大分值
 
        return;
 
    }
 
    int w=INF,temp;
    for(int i=1;i<=n;i++)//确定搜索的起点
        if(!vis[i])
        {
            int ww=0;
            for(int j=1;j<=9;j++)
                if( !vis_x[point[i].x][j] && !vis_y[point[i].y][j] && !vis_g[area[point[i].x][point[i].y]][j] )
                    if(++ww==w)
                        break;
            if(ww<w)
            {
                w=ww;
                temp=i;
            }
        }
 
 
    vis[temp]=1;
    int x=point[temp].x;
    int y=point[temp].y;
 
    for(int i=1;i<=9;i++)//枚举每一层可能的状态
        if( !vis_x[x][i] && !vis_y[y][i] && !vis_g[area[x][y]][i] )//如果当前数字在整个图的横向纵向小区域内未出现过
        {
            g[x][y]=i;
            vis_x[x][i]=1;
            vis_y[y][i]=1;
            vis_g[area[x][y]][i]=1;
 
            dfs(k+1);
 
            vis_x[x][i]=0;
            vis_y[y][i]=0;
            vis_g[area[x][y]][i]=0;
        }
 
    vis[temp]=0;
}
int main()
{
    n=0;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++)
        {
            cin>>g[i][j];
            if(g[i][j])//如果当前点填入数字
            {
                vis_x[i][g[i][j]]=1;//标记该行
                vis_y[j][g[i][j]]=1;//标记该列
                vis_g[area[i][j]][g[i][j]]=1;//标记整张图
            }
            else//如果当前点未填入数字
            {
                /*记录未填入数字*/
                n++;
                point[n].x=i;
                point[n].y=j;
            }
        }
 
    sum=-1;
    dfs(1);
    cout<<sum<<endl;
    return 0;
}
View Code

最优性剪枝

在最优化问题的搜索过程中，若当前花费的代价已超过当前搜索到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案，此时可以停止对当前分支的搜索进行回溯。

模板：

int ans = 最坏情况, now;
void dfs(传入数值) {
  if (now比ans的答案还要差) return;
  if (到达目的地) ans = 从当前解与已有解中选最优;
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

 例题：宝藏//洛谷3959

#include <cstdio>
//基础的头文件
#include <algorithm>
//给sort开的头文件
#define INF 1917483645
using namespace std;

int vis[20], lev[20], d[20];
//vis : 已经访问过的点
//lev : 点距离初始点的距离
//d : 通过此点可以达到的点数
int c[20][20], tar[20][20];
//c : 费用
//tar ：存下每个点能到的点
/*为什么要特意存下每个点到的点？
答案其实并不困难，加快访问速度*/

int ans = INF, tmp, tot, cnt, n, m, p;
//ans : 最终的答案
//tmp : 最优解剪枝用
//tot : dfs储存中间答案的用具
//cnt ：现在已经访问过的点数
//n : 点数
//m : 边数
//p : sort用品

inline bool cmp(int a, int b) {
    return c[p][a] < c[p][b];
    //按照费用给每个点能到的点排序
}

inline void dfs(int num, int node) {
    for(int i = num; i <= cnt; i ++) {
        //由第几个被访问的点来扩展
        if(tot + tmp * lev[vis[i]] >= ans) return;
        //最优性剪枝，如果当前解加上理论最小的费用都比中途的答案高
        //那么这次搜索一定不是最优解
        for(int j = node; j <= d[vis[i]]; j ++)
        //下一步扩展谁
        if(!lev[tar[vis[i]][j]]) { //用lev同时充当标记，有lev代表已访问
            cnt ++; //多添加一个点
            vis[cnt] = tar[vis[i]][j]; //记录这个点
            tmp -= c[vis[cnt]][tar[vis[cnt]][1]]; //理论最小的更新
            tot += c[vis[i]][vis[cnt]] * lev[vis[i]]; //加上当前的影响
            lev[vis[cnt]] = lev[vis[i]] + 1; //因为从vis[i]拓展，故lev一定为其 + 1
            dfs(i, j + 1); //继续从i枚举, 注意到tar[i][1 ~ j]已全部访问，下一次从j + 1尝试访问
            tot -= c[vis[i]][vis[cnt]] * lev[vis[i]]; //回溯
            lev[vis[cnt]] = 0; //回溯
            tmp += c[vis[cnt]][tar[vis[cnt]][1]]; //回溯
            cnt --; //回溯
        }
        node = 1; //剪枝别剪错了，i枚举玩下次还要从1枚举
    }
    if(cnt == n) { //已经访问了n个点，更新答案
        if(tot < ans) ans = tot;
        return;
    }
}

int main() {
    int u, v, w;
    scanf("%d%d", &n, &m); //读入n, m
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
    c[i][j] = INF; //初始赋无限大，方便后面的操作
    for(int i = 1; i <= m; i ++) {
        scanf("%d%d%d", &u, &v, &w); //这个w先暂时存起来
        //因为发现m = 1000 远> n * n，所以要剪掉一些边
        if(c[u][v] < w) continue; //w不能更新c[u][v]
        if(c[u][v] == INF) //第一次更新c[u][v]，统计u,v的出度
        tar[u][++ d[u]] = v, tar[v][++ d[v]] = u;
        c[u][v] = c[v][u] = w;
    }
    for(int i = 1; i <= n; i ++) {
        p = i; //sort排序cmp
        sort(tar[i] + 1, tar[i] + 1 + d[i], cmp);
        tmp += c[i][tar[i][1]]; //因为每个点总要扩展一条边，
        //因此我们把最小的边找出来,作为最优性剪枝
        //不仅如此，因为边越小作为最终解的可能性越大
        //实际上在一定程度上优化了程序
    }
    for(int i = 1; i <= n; i ++) {
        tot = 0; cnt = 1; //赋初值
        vis[1] = i; //第一个就选i
        tmp -= c[i][tar[i][1]]; //i的最优性剪枝的影响要去掉
        //因为剪枝的时候是以还未访问和还未将被访问的点为基础的
        //不去掉剪枝就是错误的
        lev[i] = 1; //赋值
        dfs(1, 1); //只有一个点，也肯定是从1枚举
        lev[i] = 0; //回溯
        tmp += c[i][tar[i][1]];
    }
    printf("%d", ans);
    return 0;
}
View Code

  • 爬山算法

爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图所示：假设A点为当前解，爬山算法搜索到B点这个局部最优解就会停止搜索，因为在B点无论向那个方向小幅度移动都不能得到更优的解。但其实全局最优解为D 

  • 模拟退火算法

退火的概念

在热力学上，退火（annealing）现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」，quenching）时，会导致不是最低能态的非晶形。 

如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。

似乎，大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。

模拟退火（Simulate Anneal）的概念

模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。我们知道贪心算法是一个很方便写的算法，但是它也有很大的局限性：不一定是全局最优解。这个时候我们跳脱出来，就有可能跳出这个‘坑’，最终找到全局最优解，而‘跳出来’的步骤就是模拟退火的精髓。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以下图为例，模拟退火算法在搜索到局部最优解B后，会以一定的概率接受向右继续移动。也许经过几次这样的不是局部最优的移动后会到达B 和C之间的峰点，于是就跳出了局部最小值B。

模拟退火的主要步骤

模拟退火算法新解的产生和接受可分为如下四个步骤：

第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若ΔT<0则接受S′作为新的当前解S，否则以概率exp(-ΔT/T)接受S′作为新的当前解S。

第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 

模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 

即：

  1. 先初始化温度，当前解和当前答案

  2. 如果温度小于最终温度，跳7；否则跳3

  3. 重复执行4~5步L次

  4. 由当前解生成一个临时的新解，并计算新的答案

  5. 判断是否接受该临时解，接受则更新解和答案，不接受则回退到上个解

  6. 降温，跳2

  7. 结束

对于差解的判断和 这个解有多差 以及 当前温度 有关，解越差我们越不想要它，接受它的概率就小一些；贪心往往会在开始的时候陷入局部最优解，我们就要在开始的时候跳出局部最优，也就是通过走向较差的解，所 以开始的时候接受差解的概率要大一些，快结束的时候我们需要稳定在当前的最优解，接受差解的概率就小一些，所以我们模拟物理的退火原理，温度从高逐渐降低，对于接受差解概率的计算公式e^(delta/T)来说，新解答案的差异值为分子delta，是个负数（如果正数取负就行），答案越差，delta绝对值越大，指数越小，概率也越小；温度越低，指数越小，概率也越小，这就符合了我们求解的需要。

这样就可以写出伪代码了：

T=100;delt=0.98;
while(T>0)
for k = 1 --> L
S'=trans(S,k,T);
∆t=C(S')-C(S)
if (∆t<0)S=S';
else if (rand(0,1)<exp(-∆t/C(S)))S=S'
end
if (满足结束状态)exit
T=T×delt
end

　　

Metropolis（蒙特卡洛）准则　　

1953年Metropolis提出了这样一个重要性采样的方法，即设从当前状态i生成新状态j，若新状态的内能小于状态i的内能即(Ej<Ei)，则接受新状态j作为新的当前状态；否则，以概率   exp[-(Ej-Ei)/kT]   接受状态j，其中k为Boltzmann常数，这就是通常所说的Metropolis准则。

根据Metropolis（蒙特卡洛）准则，粒子在温度T时趋于平衡的概率为exp(-ΔE/(kT))，其中E为温度T时的内能，ΔE为其改变数,k为Boltzmann常数。Metropolis准则常表示为

　　

根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为p(dE)，表示为: 

   　　　　　　 

其中: k是波尔兹曼常数，值为k=1.3806488(13)×10−23，

　　　　  exp表示自然指数，

　　　　  dE<0

                dE/kT<0

                p(dE)函数的取值范围是(0,1)。满足概率密度函数的定义。

其实这条公式更直观意思就是：温度越高，出现一次能量差为p(dE)的降温的概率就越大；温度越低，则出现降温的概率就越小。
在实际问题中，这里的“一定的概率”的计算参考了金属冶炼的退火过程。假定当前可行解为x，迭代更新后的解为xnew，那么对应的“能量差”定义为： Δf=f(xnew)−f(x).

其对应的“一定概率”为： 
  　　　　　　

注：在实际问题中，可以设定k=1。因为kT可以等价于一个参数 T。如设定k=2、T=1000，等于直接设定T=2000的效果。

模拟退火的优缺点

模拟退火算法（simulated annealing，SA）是一种通用概率算法，用来在一个大的搜寻空间内寻找问题的最优解。

优点：能够有效解决NP难问题、避免陷入局部最优解。

          计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。

          模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；

　　　模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率收敛于全局最优解的全局优化算法；

　　　模拟退火算法具有并行性

缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。

　　　由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。

　　　（1)如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢；

 　　　 (2)如果降温过程过快，很可能得不到全局最优解。

适用环境：组合优化问题。模拟退火一般用于求解最优解，而且一般比较适合于小数据的最优解和大数据的近似最优解

const double delta=...; //调一个适合自己的降温参数
int calc(){
    //用dp，最短路，贪心，模拟等算法求出当前解。
}
int SA(){
    int T=...;  //初始温度
    int T0=...;  //最终温度
    while(T>T0){
        //对于序列，枚举两个数并进行交换，得出当前解
        //对于坐标，随机生成一个点进行计算
        //对于网格图，随机枚举两个格点进行交换
        //...
        if(当前解优于最优解)  更新最优解
        else if(一定概率不接受)  //还原之前的状态
        T*=delta;  //模拟降温过程
    }
}
int main(){
   srand(time(0));srand(rand());srand(rand());
   /*主程序*/
}
#include <stdio.h>
#include <math.h>
#include <time.h>
#include<stdlib.h>
#define num 30000 //迭代次数
double k=0.1;
double r=0.9; //用于控制降温的快慢
double T=2000; //系统的温度，系统初始应该要处于一个高温的状态
double T_min =10;//温度的下限，若温度T达到T_min，则停止搜索
//返回指定范围内的随机浮点数
double rnd(double dbLow,double dbUpper)
{
    double dbTemp=rand()/((double)RAND_MAX+1.0);
    return dbLow+dbTemp*(dbUpper-dbLow);
}
double func(double x)//目标函数
{
    return x*(x-1)+1;
}
int main()
{
    double best=func(rnd(0.0,10));
    double dE,current;
    int i;
    while( T > T_min )
    {
        for(i=0;i<num;i++)
        {
        //用当前时间点初始化随机种子，防止每次运行的结果都相同
        time_t tm;
        time(&tm);
        unsigned int nSeed=(unsigned int)tm;
        srand(nSeed);
        current=func(rnd(0.0,10));
        dE = current - best ;
        if ( dE < 0 ) //表达移动后得到更优解，则总是接受移动
        best = current ;
        else
        {
            // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也越大
            if ( exp( dE/(T*k) ) > rnd( 0.0 , 1.0 ) )
                best = current ;
        }
        }
        T = r * T ;//降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
    }
    printf("最小值是 %f
",best);
    return 0;
}

例题：宝藏//3959

  • 维护一个序列和一个值，前者是生成当前最优解的方案，后者是当前最优解
  • 序列是1~n的一个排列，它的含义是，按照每个节点的下标从小到大，贪心地按照这个顺序拓展出来一个生成树，这个序列的第一个就是树根（题目中的免费点）
  • 在退火过程中，通过随机交换的方法，把生成局部最优解的序列随机化，用新的序列的check
  • check过程中，始终遵循一个原则：对于一个新的结点，优先置为边权*深度最小的结点的儿子，如果有多个相同最小权值结点，那么置为深度最低的结点的儿子，如果仍有多个，那么置为其中编号最小的结点的儿子。

考虑这样的一种情况，我们已经完成了1 4 3 5的构造，现在正有一个2尚未加入生成树，结点6有且只有一条关联边：<2,6>=5。

显然，让2作3的儿子是当前的最优解。

由于这里生成树的特性，结点可以直接接在任何一个结点下面，对于任意结点，在当前的解不更差的情况下，深度尽量低不会带来后续更差的解。

对于最后一条关于“编号”的决策，就算当前不是最优解，也可以通过顺序不同的生成，很大概率check到其他等价方案。

#include<bits/stdc++.h>
using namespace std;
const int maxn=12+5;
int n,m;
int d[maxn][maxn];
int line[maxn];

void pre_rand(){srand(time(NULL));}

void read(){
    cin>>n>>m;
    memset(d,0x3f,sizeof(d));
    for(int i=1;i<=n;++i) d[i][i]=0;
    for(int i=1;i<=m;++i){
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        d[u][v]=d[v][u]=min(d[u][v],w);
    }
    for(int i=1;i<=n;++i) line[i]=i;
}

inline int sum(int l[maxn]){
    int dep[maxn];
    int res=0;
    dep[l[1]]=0;
    for(int i=2;i<=n;++i){
        int tmp=INT_MAX,rt;
        for(int j=1;j<i;++j) if(d[l[j]][l[i]]!=0x3f3f3f3f and tmp>(dep[l[j]]+1)*d[l[j]][l[i]]){
            //寻找最少花费 
            tmp=(dep[l[j]]+1)*d[l[j]][l[i]];
            rt=l[j];
        }
        else if(d[l[j]][l[i]]!=0x3f3f3f3f and tmp==(dep[l[j]]+1)*d[l[j]][l[i]] and dep[l[j]]<dep[rt]){
            //在最小花费的意义上找到最低深度 
            rt=l[j];
        }
        if(tmp==INT_MAX) return INT_MAX;
        res+=tmp,dep[l[i]]=dep[rt]+1;
    }
    return res;
}

int ans=1e9;

void solve(){
    double t=2000.0;
    int l[maxn];memcpy(l,line,sizeof(line));
    while(t>1e-14){
        int now[maxn]; memcpy(now,l,sizeof(l));
        int a,b;
        do{
            a=rand()%n+1,b=rand()%n+1;
        }while(a==b);
        swap(now[a],now[b]);
        int _ans=sum(now);
        int delta=_ans-ans;
        if(delta<0) ans=_ans,memcpy(l,now,sizeof(now)),memcpy(line,l,sizeof(l));//line=l=now;
        else if(exp(-delta/t)*RAND_MAX>rand()) memcpy(l,now,sizeof(now));//l=now;
        t*=0.996;
    }
}

void print(){
    cout<<ans;
}

bool cheat(){if(n==1){cout<<0;return true;} return false;}

int main(){
    pre_rand();
    read();
    if(cheat()) return 0;
    solve(),solve(),solve(),solve();
    print();
    return 0;
}
View Code

例题：城堡//洛谷2538

 大概题意：

你有n个点，其中m个点是特殊点，定义一个点的dist为距它最近的特殊点到它的距离。你可以将这剩下n−m个点中的不超过k个点变成特殊点，使得所有dist的最大值最小。2≤n≤50,di​≤106,0≤m≤n−k

#include<bits/stdc++.h>
#define P pair<int,int>
const double putdown = 0.997;
const int inf = 0x3f3f3f3f;
using namespace std;
const int N = 55;
int city[N],head[N],ans = inf,n,m,k,ri[N],dist[N],no_city[N],cnt = -1,need_city = 0;
bool vis[N];
struct EDGE{
    int to;
    int next;
    int w;
}e[N<<1];
void add(int x,int y,int d)
{
    e[++cnt].to = y;e[cnt].next = head[x];e[cnt].w = d;head[x] = cnt;
    e[++cnt].to = x;e[cnt].next = head[y];e[cnt].w = d;head[y] = cnt;
}
struct node{
    int pos;
    int dist;
    bool operator <(const node& S)const{
    return dist>S.dist;
    }
};

void solve()
{
    priority_queue<node> q;
    memset(dist,0x3f,sizeof(dist));
    memset(vis,false,sizeof(vis));
    for(int i = 1;i <= m;i++)
    {
        dist[city[i]] = 0;
        q.push((node){city[i],dist[city[i]]});
    }
    for(int i = 1;i <= k;i++)
    {
        dist[no_city[i]] = 0;
        q.push((node){no_city[i],dist[no_city[i]]});
    }
    
    while(!q.empty())
    {
        int x = q.top().pos;
        q.pop();
        //cout<<x<<endl;
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x];~i;i = e[i].next)
        {
            int y = e[i].to;
            if(e[i].w<dist[y]-dist[x])
            {
                dist[y] = dist[x] + e[i].w;
                q.push((node){y,dist[y]});
            }
        }
    }
//    for(int i = 1;i <= n;i++)
//    {
//        cout<<dist[i]<<endl;
//        system("pause");
//    }
}
void EA()
{
    int res = inf;
    double T = 2000;
    while(T > 1e-10)
    {
        int x = (rand()%k)+1;
        int y = (rand()%(need_city - k))+k+1;
        swap(no_city[x],no_city[y]);
        //cout<<"debug1"<<endl;
        solve();
        //cout<<"debug2"<<endl;
        int new_res = -1;
        for(int i = 1;i <= need_city;i++)
        {
            //cout<<"debug3"<<endl;
            int yy = dist[no_city[i]];
            //if(yy == inf) cout<<no_city[i]<<endl;
            new_res = max(new_res,yy);
        }
        //cout<<"debug4 "<<new_res<<endl;
        T *= putdown;
        int delta = res - new_res;
        if(delta > 0)
        {
            res = new_res;
            continue;
        }
        else if(exp(-(double)delta*RAND_MAX/T) < rand())
        {
            //cout<<"debug5"<<endl;
            continue;
        }
        swap(no_city[x],no_city[y]);
    }
    ans = min(ans,res);
}

int main()
{
    srand((int)time(0));
    memset(vis,true,sizeof(vis));
    memset(head,-1,sizeof(head));
    cin>>n>>m>>k;
    for(int i = 1;i <= n;i++)
    cin>>ri[i];
    for(int i = 1;i <= n;i++)
    {
        int d;
        cin>>d;
        add(i,ri[i]+1,d);
    }
    for(int i = 1;i <= m;i++)
    {
        int a;
        cin>>a;
        city[i] = a+1;
        //cin>>city[i];
        vis[city[i]] = false;
    }
    for(int i = 1;i <= n;i++)
    {
        if(vis[i])
        {
            no_city[++need_city] = i;
        }
    }
    solve();
    if(need_city == k)
    {
        ans = 0;
        for(int i = 1;i <= need_city;i++)
        {
            int y = no_city[i];
            ans = max(ans,dist[y]);
        }
        cout<<ans<<endl;
        return 0;
    }
    EA();
    EA();
    EA();
    cout<<ans<<endl;
    return 0;
}
View Code

例题集 

博客学习

https://blog.csdn.net/georgesale/article/details/80631417

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wybxz/p/12878374.html