爬山算法、模拟退火算法

参考：http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html#!comments

http://blog.csdn.net/acdreamers/article/details/10019849

1、POJ 2420 A Star not a Tree?

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <stack>#include <map>#include <set>#include <cmath>#include <cctype>#include <ctime>#include <cassert>using namespace std;#define REP(i, n) for (int i = 0; i < (n); ++i)#define eps 1e-9typedef long long ll;typedef pair<int, int> Pair;const int INF = 0x7fffffff;const int maxn = 100 + 10;struct Node {    double x, y;};int n;int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};Node node[maxn];double x_sum = 0.0, y_sum = 0.0, x_average = 0.0, y_average = 0.0;double dis(Node a, Node b);double get_sum(Node a);double Search(void);int main() {#ifdef __AiR_H    freopen("in.txt", "r", stdin);#endif // __AiR_H    scanf("%d", &n);    REP(i, n) {        scanf("%lf %lf", &node[i].x, &node[i].y);        x_sum += node[i].x; y_sum += node[i].y;    }    x_average = x_sum / n; y_average = y_sum / n;    PRintf("%.0f/n", Search());#ifdef __AiR_H    printf("Time used = %.2fs/n", (double)clock() / CLOCKS_PER_SEC);#endif // __AiR_H    return 0;}double Search(void) {    Node start, t; start.x = x_average; start.y = y_average;    double T = 100.0, ans = get_sum(start), ans_t;    while (T > eps) {        bool flag = true;        while (flag) {            flag = false;            REP(i, 4) {                t.x = start.x + dir[i][0] * T; t.y = start.y + dir[i][1] * T;                ans_t = get_sum(t);                if (ans_t < ans) { ans = ans_t; start = t; flag = true; }            }        }        T *= 0.9;    }    return ans;}double get_sum(Node a) {    double ret = 0.0;    REP(i, n) { ret += dis(node[i], a); }    return ret;}double dis(Node a, Node b) {    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}