題目鏈接：http://poj.org/problem?id=2420

求費(fèi)馬點(diǎn)，即到所有其他點(diǎn)總和距離最小的點(diǎn)。

一開始想枚舉一個(gè)坐標(biāo)，另一個(gè)坐標(biāo)二分的，但是check的時(shí)候還是O(n)的，復(fù)雜度相當(dāng)于O(n^2lgn)，沒意義。

學(xué)習(xí)一種神貪心，模擬退火。感覺和啟發(fā)式搜索有點(diǎn)像啊，又有點(diǎn)像牛頓迭代。

　　思路就是，固定一個(gè)點(diǎn)和一個(gè)步長(zhǎng)，從這個(gè)點(diǎn)開始向四個(gè)方向擴(kuò)展，擴(kuò)展的步長(zhǎng)就是當(dāng)前步長(zhǎng)。如果擴(kuò)展到的點(diǎn)可以更新答案，那么記住這個(gè)點(diǎn)，也就是說這個(gè)貪心方向（梯度？）是正確的。就可以拿著這個(gè)點(diǎn)繼續(xù)沿著這個(gè)方向走了（剩余的方向可以不考慮了）。

　　如果四個(gè)方向都不能走，說明步長(zhǎng)過長(zhǎng)，這個(gè)時(shí)候模擬退火，將步長(zhǎng)按比率縮小。

1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <cassert> 8 #include <cstdio> 9 #include <bitset> 10 #include <vector> 11 #include <deque> 12 #include <queue> 13 #include <stack> 14 #include <ctime> 15 #include <set> 16 #include <map> 17 #include <cmath> 18 using namespace std; 19 20 typedef pair<double, double> pdd; 21 #define x first 22 #define y second 23 const double eps = 1e-8; 24 const double delta = 0.98; 25 const int maxn = 10100; 26 const int dx[5] = {1, -1, 0, 0}; 27 const int dy[5] = {0, 0, 1, -1}; 28 int n; 29 double ret; 30 pdd cur; 31 pdd p[maxn]; 32 33 double dist(pdd a, pdd b) { 34 double p = a.x - b.x; 35 double q = a.y - b.y; 36 return sqrt(p * p + q * q); 37 } 38 39 int main() { 40 // freopen("in", "r", stdin); 41 while(~scanf("%d", &n)) { 42 for(int i = 0; i < n; i++) { 43 scanf("%lf %lf", &p[i].x, &p[i].y); 44 } 45 int t = 100; 46 ret = 1e100; 47 cur = pdd(.0, .0); 48 while(t > eps) { 49 bool flag = 1; 50 while(flag) { 51 flag = 0; 52 for(int i = 0; i < 4; i++) { 53 pdd pos = pdd(cur.x+dx[i]*t, cur.y+dy[i]*t); 54 double tmp = .0; 55 for(int j = 0; j < n; j++) { 56 tmp += dist(pos, p[j]); 57 } 58 if(ret - tmp > eps) { 59 ret = tmp; 60 cur = pos; 61 flag = 1; 62 break; 63 } 64 } 65 } 66 t *= delta; 67 } 68 printf("%.0f\n", ret); 69 } 70 return 0; 71 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/kirai/p/6229822.html

總結(jié)

以上是生活随笔為你收集整理的[POJ2420]A Star not a Tree?（模拟退火）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。