平面上给定n条线段，找出一个点，使这个点到这n条线段的距离和最小 模拟退火 无处提交的辣鸡题

缘起

这传闻是一道面试题目

1
平面上给定n条线段，找出一个点，使这个点到这n条线段的距离和最小。

本辣鸡想说的是——题目出的是不严谨的, 应该说是n条直线而不是线段. 就像【1】中最后总结的那样, 这种搜索空间极大的最优解问题，又不能暴力枚举的, 考虑采用模拟退火.

分析

有了【1】的基础, 就可以直接撸代码了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "stdafx.h"
#include <stdio.h>
#include <math.h>
#define LOCAL
#define SQUARE(x) ((x)*(x))
const int maxn = 1005;
int n, cnt, dir[4][2]={{1,0},{-1,0},{0, 1},{0, -1}};
double ans, step, eps = 1e-8;
struct Line
{
	double a,b,c; // 直线 ax+by+c=0;
}ls[maxn];

struct Point
{
	double x,y;
	Point(double x = 0, double y=0){}
}cur, nxt;

double dis(Point &p, Line &l) // p到直线l的距离
{
	return abs((l.a*p.x+l.b*p.y+l.c)/sqrt(SQUARE(l.a)+SQUARE(l.b)));
}

double e(Point &p)
{
	double ans = 0;
	for (int i = 0; i<n; i++)
	{
		ans+=dis(p, ls[i]);
	}
	return ans;
}

void transform(int i)
{
	nxt.x = cur.x+dir[i][0]*step,nxt.y = cur.y+dir[i][1]*step;
}

void sa()
{
	step = 100, ans = e(cur);
	while(step>eps)
	{
		bool ok = true;
		while (ok)
		{
			ok = false;
			for (int i = 0; i<4; i++)
			{
				transform(i);
				double nxte = e(nxt);
				if (nxte+eps<ans)
				{
					ans = nxte;
					cur = nxt;
					ok = true;
					cnt++; // 状态转移数量+1
				}
			}
		}
		step/=2;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 0; i<n; i++)
	{
		scanf("%lf%lf%lf", &ls[i].a, &ls[i].b, &ls[i].c);
	}
	sa();
	printf("达到最优的点是(%.4lf, %.4lf), 最小的距离之和是%.4lf, 模拟退火一共经历了%d次搜索.\n", nxt.x, nxt.y, ans, cnt);
	return 0;
}

无处提交~ 辣鸡题目, 制造数据的程序如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "stdafx.h"
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include<random>

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000000;
typedef long long LL;
typedef vector<int>::iterator vit;


int main()
{
	freopen("d:\\data.in", "w", stdout);
	srand((int)(time(0)));


	int n = 10;
	printf("%d\n", n);

	default_random_engine e(time(0));
	uniform_real_distribution<double> abc(-100,100);
	for(int i = 0; i < n; ++i)
	{
		cout << abc(e) << ' ' << abc(e) << ' ' << abc(e) << endl;
	}

	fclose(stdout); 
	return 0;
}

然后随意yy了一组数据

1
2
3
4
5
6
7
8
9
10
11
10
89.8966 -64.0834 2.95602
30.1413 -41.9175 -46.1736
32.2537 -51.3097 57.8875
-43.6388 -55.6 -64.6502
21.1126 85.3875 52.6779
-98.8699 -40.0879 -5.68766
-96.3723 -0.0584871 -30.3226
64.4949 -79.3621 -75.1657
78.782 47.0611 36.1393
-75.4902 2.01727 3.68237

跑上面的模拟退火算法, 得到输出

1
达到最优的点是(-0.0409, -0.6995), 最小的距离之和是3.5142, 一共经历了21次搜索.

其实, 就算是1000条直线, 答案也是秒出的. 而且搜索的次数极少（几乎就稳定在20次以内）. 所以【1】中祭出的模拟退火的板子还是相当高效的.

参考

【1】https://yfsyfs.github.io/2019/09/27/poj-2420-A-Star-not-a-Tree-%E8%B4%B9%E9%A9%AC%E7%82%B9%E7%9A%84%E6%B1%82%E8%A7%A3-%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB/