UPC Haywire（模拟退火 || 随机数法）

62 阅读 0 评论 41 点赞

我是靠谱客的博主魁梧香菇，最近开发中收集的这篇文章主要介绍UPC Haywire（模拟退火 || 随机数法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

中文题面友链传送门

Haywire

题目描述
Farmer John’s N cows (4 <= N <= 12, N even) have built a primitive system for communicating between pairs of friendly cows by building wires protected by wrappings made of hay.

Each cow has exactly 3 other friends in the barn, and the cows must arrange themselves to occupy N stalls lined up in a row. A wire of length L requires exactly L units of hay to build, so for example if the cows in stalls 4 and 7 are friends, it would take 3 units of hay to construct a wire to connect them.

Assuming every pair of friends must be connected by a separate wire, please determine the minimum possible amount of hay required to build these wires if the cows order themselves in the best possible way.
输入

Line 1: The integer N. FJ’s cows are conveniently numbered 1…N.
Lines 2…1+N: Each line contains three space-separated integers in the range 1…N. Line i+1 contains the numeric identifiers of the three friends of cow i. If cow i is a friend of cow j, then j will also be a friend of i.
输出
Line 1: The minimum total amount of hay required to connect all pairs of friendly cows.
样例输入 Copy
6
6 2 5
1 3 4
4 2 6
5 3 2
4 6 1
1 5 3
样例输出 Copy
17
提示
There are 6 cows. Cow 1 is friends with cows 6, 2, and 5, etc.A best ordering of the cows is 6, 5, 1, 4, 2, 3, which requires only 17 units of hay.

朴素随机数法

数据很小，利用随机数计算每次交换的牛的位置，计算出花费，跑1e6次就可以了。~~（真玄学）~~ 好像只能是1e6，反正1e5是82，5e5是92，越来越接近正解了
注意计算花费时每两头牛都算了两遍，所以结果需要/2.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=20,mod=1e9+7,tot=1e6;
int pos[maxn][maxn],n,a[maxn],tmp[maxn];
void init(){
	for(int i=1;i<=n;i++) a[i]=i;
}
int cul(){
	int sum=0;
	for(int i=1;i<=n;i++) tmp[a[i]]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=3;j++)
			sum+=abs(tmp[pos[a[i]][j]]-i);
	return sum/2;//计算时每两个牛的距离都算了都两遍
}
void AC(){
    n=read();
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=3;j++)
    		pos[i][j]=read();
    init();
    int cnt=1;
    int minn=2e9;
    while(cnt<=tot){
    	int l=(rand())%n+1;
    	int r=(rand())%n+1;
    	int t=a[l];a[l]=a[r];a[r]=t;
    	minn=min(minn,cul());
    	cnt++;
	}
	out(minn);
}
int main(){
    AC();
    return 0;
}

稍加优化的模拟退火

其实本质也是随机数，只是多了一个判断，如果当前解很差的话，就再交换回去。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=20,mod=1e9+7,tot=5e5;
int pos[maxn][maxn],n,a[maxn],tmp[maxn];
int minn=1e8;
const double s=10000,e=1e-12,c=0.99;
//起始温度 终止温度 温度改变速度 
void init(){
	for(int i=1;i<=n;i++) a[i]=i;
}
int cul(){
	int sum=0;
	for(int i=1;i<=n;i++) tmp[a[i]]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=3;j++)
			sum+=abs(tmp[pos[a[i]][j]]-i);
	return sum/2;//计算时每两个牛的距离都算了都两遍
}
void SA(int times){
	int x,y,t;
	while(times--){
		for(double i=s;i>e;i*=c){
			do{
				x=rand()%n+1;
				y=rand()%n+1;
			}while(x==y);
			swap(a[x],a[y]);
			t=cul();
			if(minn>=t) minn=t;
			else if(exp((minn-t)/i)>(double)rand()/RAND_MAX)
				swap(a[x],a[y]);
				//当前解很差 恢复此次交换
		}
	}
	return ;
}
void AC(){
    n=read();
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=3;j++)
    		pos[i][j]=read();
    init();
    SA(160);
	out(minn);
}
int main(){
    AC();
    return 0;
}

几率接受的几率是个很玄学的问题,通常情况,设当前温度为 T T ,当前解为 k k ,最优解为 K_{max} K
max
,我们通常用这样一个玄学公式…
exp((k-kmax)/T)<(double)rand()/RAND_MAX
我当初也不知道exp的意义何在,后来发现太妙了!如果不知道exp是啥,可以自己看一下百科,我稍作解释: exp函数在X < 0时, Y 一定为 0 - 1 之间的小数且单调递增,(double)rand()/RAND_MAX也是一个 0 - 1 之间的小数.这样温度越小,接受当前较差解的几率越低.

最后对比一下两种方法的运行结果吧，其实差不了很多~
朴素版本的随机数
在这里插入图片描述