火车站的最佳位置

mathe

同样，
$T_{x x}=int_{D'}u^2/{(u^2+v^2)^{3/2}}dudv$
然后左边变换为极坐标形式，得到
$T_{x x}=int_0^{2pi}d\theta int_0^{R(\theta)}cos^2(\theta)dr$
即
$T_{x x}=int_0^{2pi}R(\theta)cos^2(\theta)d\theta$
$T_{x x}=\sum_{k=1}^n int_{t_{k-1}}^{t_k}{h_kcos^2(\theta)}/{cos(\theta-\theta_k)}d\theta$
或者
$T_{x x}=\sum_{k=1}^n int_{t_{k-1}-theta_k}^{t_k-theta_k}{h_kcos^2(\theta+\theta_k)}/{cos(\theta)}d\theta$
即
$T_{x x}=\sum_{k=1}^n h_k({1-cos(2\theta_k)}/4ln((1+sin(\theta))/(1-sin(\theta)))+sin(\theta+2\theta_k))|_{\theta=t_{k-1}-theta_k}^{t_k-theta_k}$
同样可以计算出
$T_{x y}=-\sum_{k=1}^n h_k({sin(2\theta_k)}/4ln((1-sin(\theta))/(1+sin(\theta)))-cos(\theta+2\theta_k))|_{\theta=t_{k-1}-theta_k}^{t_k-theta_k}$
$T_{y y}=\sum_{k=1}^n h_k({1+cos(2\theta_k)}/4ln((1+sin(\theta))/(1-sin(\theta)))-sin(\theta+2\theta_k))|_{\theta=t_{k-1}-theta_k}^{t_k-theta_k}$

mathe

同样
$T=1/3int_0^{2pi}R(\theta)^3d\theta$
$T=1/3\sum_{k=1}^n h_k^3(1/4ln((1+sin(\theta))/(1-sin(\theta)))+{sin(\theta)}/{2cos^2(\theta)})|_{\theta=t_{k-1}-theta_k}^{t_k-theta_k}$
上面各表达式计算有点复杂，难免出错，谁来验算一下看看

mathe

mathe的方法都是建立在分图形的Fans心刚好都是关于分界垂直平分。这样的结果是不是能算出最小值，没有被证明。
我的思路，任意设定三个站点的坐标，利用解析方法计算出垂直平分线及图形的分界，计算每个图形的平均距 ...
056254628 发表于 2010-11-9 22:12

分图形的Fans心刚好被分界先垂直平分是显然的。
假设使用k个火车站的最优方案给定，那么对于区域中每个点，自然被划分到离它最近的一个火车站；而这种划分的各个分界线就是那些火车站的中垂线（其中可能只有部分起作用）。而这些分割线将整个区域分割成一些小区域。而根据Fans心的定义，如果方案最优，那么每个火车站都是各自子区域的Fans心。

mathe

重新采用新的方法枚举31#的最后一种情况和33#的方案，得到31#方案最优距离为0.23602877，而33#方案最优距离为0.23561674。
也就是38#的结果是正确的

mathe

其中对于33#的最优方案，三条分界线交点的纵坐标为0.477283，也分界线同边交点的纵坐标为0.752942
区域的Fans心坐标为(0.23434202,0.30958497),(0.5,0.79144368)
train.tgz (1.53 KB, 下载次数: 3)

2010-11-10 14:57 上传

点击文件名下载附件

附件给出了计算给定凸边形为边界的区域的Fans心的C代码（如果不是凸边形边界，结果就没有意义了）

mathe

上面几层楼的想法都很有道理。

猜想：

当$N$是完全平方数时，$N$个火车站的排列是有规律的。

规律如下：

将大正方形分成$n$*$n$个小正方形，其中$n$*$n$=$N$。

这$N$个火车站就分别位于$n$*$n$个小正 ...
KeyTo9_Fans 发表于 2010-11-6 23:59

当N充分大，这个猜想应该不成立。等边六边形划分应该比正方形更高效

056254628

对于n=5时，最小值为0.174786180973171
五点坐标为 (a,a),(a,1-a),(1-a,a),(1-a,1-a),(0.5,0.5)
a精确到小数点后7位时，a=0.2199749

056254628

利用逐渐逼近法计算n=6：
得最小值=0.160771534476805
六个站点的坐标如下：   （坐标的绝对误差小于0.000001）
0.203171816602654，0.216339470856365
0.203171643959506，0.783660270131779
0.726213897395046，0.159668221225385
0.726213400209119，0.840331892217754
0.839489396058242，0.500000244424711
0.450228998010121，0.499999991969136

mathe

也许有了45#Fans心的快速算法以后，我们可以采用迭代法来解决这个问题。
0)每次可以先任意选择k个火车站位置。
1)然后根据各点到k个火车站的距离划分正方形成k个凸区域
2)计算每个区域的Fans心，作为新的火车站位置，返回1)
如果上面过程收敛，那么必然收敛到一个局部最优的方案。
不同的初始值选择可能收敛到不同的局部最优方案。多选择几个初始值，可以得出多个方案，选择其中最优的方案即可。

056254628

利用逐渐逼近法计算n=7：
得最小值=0.148810407004875
七个站点的坐标如下：   （坐标的绝对误差小于0.0000001）
0.239461264412722，0.524101299554266
0.753421285066396，0.525602710805835
0.750900000937741，0.841886114801357
0.254963948563921，0.841157213750004
0.838984382922992，0.179420970196441
0.161455989240008，0.177616245793998
0.499700355731923，0.206814563474133




有点奇怪，n=7时得到的结果居然不是对称图形，而n<7的结果都是对称图形。