codes for 模拟退火()-其他

codes for 模拟退火()

伪代码:

#include<bits/stdc++.h>
using namespace std;

signed main()
{
	ios::sync_with_stdio(0);

	cin >> 初始解;
	
	认为当前为最优解;
	
	for (由前解扰动生成新解)
	{
		if (是否为最优解)
		{
			接收新解;
			
			增加生成次数;
		}
		else
		{
			按照Metropolis接收新解;
			
			增加生成次数;
		}
		
		if (生成次数达到迭代次数)
		{
			if (是否可以输出)
			{
				cout << 结果 << endl;
				
				return 0;
			}
			
			else
			{
				缓慢降低温度,重置迭代次数;
			}
		}
	}
}

P2210 参考代码:

#include<bits/stdc++.h>
using namespace std;

long long n,a[15][5],aw[15],nowans=1e18;

const double B=10000,E=1e-12,W=0.999;

long long getans()
{
	long long ans=0;
	
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=3;j++)
			ans+=abs(aw[i]-aw[a[i][j]]);
			
	return ans;
}

void sa()
{
	long long t=clock();
	
	while (clock()-t<0.99*CLOCKS_PER_SEC)
	{
		for (double j=B; j>=E; j*=W)
		{
			long long x,y;
			
			do
			{
				x=1+rand()%n;
				y=1+rand()%n;
			}while (x==y);
			
			swap(aw[x],aw[y]);
			
			long long tmp=getans()/2;
			
			if (tmp<=nowans)
				nowans=tmp;
				
			else if (exp((nowans-tmp)*1.0/j)<rand()*1.0/RAND_MAX)
				swap(aw[x],aw[y]);
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	
	cin >> n;
	
	for (long long i=1; i<=n; i++)
	{
		for (long long j=1; j<=3; j++)
			cin >> a[i][j];
			
		aw[i]=i;
	}
	
	sa();
	
	cout << nowans << endl;
	
	return 0;
}

伪代码:

#include<bits/stdc++.h>
using namespace std;

signed main()
{
	ios::sync_with_stdio(0);

	cin >> 初始解;
	
	认为当前为最优解;
	
	for (由前解扰动生成新解)
	{
		if (是否为最优解)
		{
			接收新解;
			
			增加生成次数;
		}
		else
		{
			按照Metropolis接收新解;
			
			增加生成次数;
		}
		
		if (生成次数达到迭代次数)
		{
			if (是否可以输出)
			{
				cout << 结果 << endl;
				
				return 0;
			}
			
			else
			{
				缓慢降低温度,重置迭代次数;
			}
		}
	}
}

P2210 参考代码:

#include<bits/stdc++.h>
using namespace std;

long long n,a[15][5],aw[15],nowans=1e18;

const double B=10000,E=1e-12,W=0.999;

long long getans()
{
	long long ans=0;
	
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=3;j++)
			ans+=abs(aw[i]-aw[a[i][j]]);
			
	return ans;
}

void sa()
{
	long long t=clock();
	
	while (clock()-t<0.99*CLOCKS_PER_SEC)
	{
		for (double j=B; j>=E; j*=W)
		{
			long long x,y;
			
			do
			{
				x=1+rand()%n;
				y=1+rand()%n;
			}while (x==y);
			
			swap(aw[x],aw[y]);
			
			long long tmp=getans()/2;
			
			if (tmp<=nowans)
				nowans=tmp;
				
			else if (exp((nowans-tmp)*1.0/j)<rand()*1.0/RAND_MAX)
				swap(aw[x],aw[y]);
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	
	cin >> n;
	
	for (long long i=1; i<=n; i++)
	{
		for (long long j=1; j<=3; j++)
			cin >> a[i][j];
			
		aw[i]=i;
	}
	
	sa();
	
	cout << nowans << endl;
	
	return 0;
}