題意：平面上給你n個點，讓你求一個點，到這n點的距離和最小
板子得模擬退火，系數也是很好控制，對數器和ACdream得代碼跑了1884組樣例，結果只有一組不一樣,可是我得解更優(yōu)啊, 交上去RE,
不想再改了,
真心感覺或者模擬退火算法是個假得算法,a不a多數靠運氣啊,
脫坑
6
6878 4617
2040 3626
2067 9225
9729 4725
8635 7922
5480 3415
20010//我的跑出來的結果
20040//ACdream跑出來的結果
哇,A了A了，第二天，想著用VS2017debug一番,果真有不通過的地方 原來是他媽~scanf("%d",&n); ?把他改成EOF就過了 操
re到哭，長記性了?
#include <iostream>
#include <cmath>
#include <cstdio>
#include <stdlib.h>
#include <ctime>
#define mp make_pair
#define sz(x) int((x).size())
#define fin freopen("in.txt","r",stdin)
#define fout freopen("out.txt","w",stdout)
#define io ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
//const int mod = 1e9 + 7;
//const int maxn = 1e6 + 5;
int n, x, y;
struct point { double x, y, w; } p[1000006], now, nex, ansp;
double dis(point a, point b) { return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); }
double f(point x)
{ //評估函數double res = 0;for (int i = 1;i <= n;i++) res += dis(x, p[i]);return res;
}
double ans = 1e20;//最開始的能量值,初始很大就可以,不用修改
void sa()
{ans = 1e20;double T = 100; //初始溫度, (可以適當修改,最好和給的數據最大范圍相同,或者縮小其原來0.1)double d = 0.99; //降溫系數 (可以適當修改,影響結果的精度和循環(huán)的次數,)double eps = 1e-8; //最終溫度 (要是因為精度問題，可以適當減小最終溫度)double TT = 1.0; //采納新解的初始概率double dd = 0.98; //(可以適當修改,采納新解變更的概率)(這個概率下面新解更新的時候,最好和未采納的新解更新的次數是一半一半)double res = f(now); //傳入的初始默認解(now)下得到的評估能量值if (res < ans) ans = res, ansp = now;//ansp終解while (T > eps){for (int i = -1;i <= 1;++i)for (int j = -1;j <= 1;++j)if ((i || j) && (now.x + T * i <= 10000) && (now.x + T * i >= 0) && (now.y + T * j <= 10000) && (now.y + T * j >= 0)){nex.x = now.x + T * i, nex.y = now.y + T * j;//新解double tmp = f(nex);//新解下的評估能量值if (tmp < ans) ans = tmp, ansp = nex;//降溫成功,更新當前最優(yōu)解if (tmp < res) res = tmp, now = nex;// 降溫成功,采納新解else if (TT > rand() % 10000 / 10000.0) res = tmp, now = nex;//,cout<<"======"<<endl;//沒有 降溫成功，但是以一定的概率采納新解//else cout<<"="<<endl;//用于測試，設定的采納新解的概率,是否為一半一半,可以適當修改降溫參數dd}T *= d; TT *= dd;}
}
int main()
{srand(time(0));while (scanf("%d", &n!=EOF){now.x = now.y = 0;for (int i = 1;i <= n;++i){cin >> p[i].x >> p[i].y;//scanf("%lf%lf%lf",&p[i].x,&p[i].y),now.x += p[i].x, now.y += p[i].y;}now.x /= n, now.y /= n; sa();printf("%.0f\n", ans);//cout<<ans<<endl;}return 0;
}
?
《新程序員》：云原生和全面數字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結
以上是生活随笔為你收集整理的poj2420 A Star not a Tree? 【模拟退火】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
