本帖最后由 KeyTo9_Fans 于 2010-11-17 13:12 编辑
要否定四边界共点是最优的，那么就应该仔细考察$N=4$和$N=9$的情况。
当$N=4$时，最短田埂问题的答案不是分成$4$个小正方形，而是将田埂拉成三叉状。
对于此问题，参考最短田埂问题的答案，$4$个点摆成菱形状就可以避免四边界共点，形成三叉状。
如下图所示：
然而凭感觉看，这个答案并不是最优的。
离中心较远的$2$个点有向中心靠拢的趋势，而离中心较近的$2$个点有远离中心的趋势。
当$4$个点与中心的距离相等时稳定下来，形成$4$个小正方形。
利用我前面想到的迭代方法写了个随机算法的程序，不过发现迭代收敛速度还是挺慢的。
函数
genCenters(K,N,ERR)
用来产生一个随机解，其中K是火车站数目，N是迭代次数，ERR是使用的误差（需要注意的是如果计算精度不够高，而是用误差ERR很小，可能会出现除0错误，这时可以降低迭代次数或增加误差或提高计算精度）
对于计算出来的解，可以调用函数getTotalT(..)来计算这个解的平均距离。
部分计算过程:
? \p
realprecision = 38 significant digits (20 digits displayed)
? genCenters(3,100,1e-10)
%173 =
? genCenters(3,1000,1e-10)
%174 =
? \p 14
realprecision = 19 significant digits (14 digits displayed)
? genCenters(4,500,1e-10)
*** for: division by zero
? genCenters(4,500,1e-10)
*** for: division by zero
? \p 20
realprecision = 38 significant digits (20 digits displayed)
? genCenters(4,500,1e-10)
*** for: division by zero
? \p 30
realprecision = 38 significant digits (30 digits displayed)
? genCenters(4,50,1e-10)
%175 =
? genCenters(4,50,1e-10)
%176 =
? genCenters(5,50,1e-10)
%177 =
? genCenters(5,50,1e-10)
%178 =
? genCenters(5,50,1e-10)
%179 =
? genCenters(5,500,1e-10)
%180 =
? setrand(1000)
%181 = 1000
? genCenters(5,500,1e-10)
%182 =
? \r train
? getTotalT(%182)
%183 = 0.174786180973170660322941393138
? getTotalT(%180)
%184 = 0.175660708263854388172181275707
? genCenters(5,500,1e-10)
%185 =
? getTotalT(%185)
%186 = 0.174786180973170660322941393138
? genCenters(6,500,1e-10)
%187 =
? getTotalT(%187)
%188 = 0.160771534476707546590248210081
? genCenters(7,200,1e-10)
%189 =
? getTotalT(%189)
%190 = 0.148592718737155249948954581302
? genCenters(7,200,1e-10)
%191 =
? getTotalT(%191)
%192 = 0.148592718737155249948954618912
? genCenters(7,200,1e-10)
%193 =
? getTotalT(%191)
%194 = 0.148592718737155249948954618912
? getTotalT(%193)
%195 = 0.148810411888737275049524820469
? genCenters(7,200,1e-10)
%196 =
? getTotalT(%196)
%197 = 0.148107927307609628274837275884
上面迭代的方法由于收敛速度比较慢，只能得出一个近似解。
在得出一个近似解以后，我们可以假设真正的解的模式和这个近似解相同。此后我们可以通过假设所有Fans心的坐标和各个区域顶点的坐标为未知数。由此，每个Fans心对应两个未知数，每个内部的区域顶点两个未知数，边界上的区域顶点一个未知数。
而根据Fans心的条件，可以得出两条方程（也就是40#中的$T_x=0,T_y=0$）。而对于区域每条非边界的边，必然有两个Fans心关于它对称，由此，又可以得出两条方程（Fans心的连线和这条边垂直，中点在这条边上）。
而解这个超越方程必然可以得出解。而由于我们已经有一个不错的近似解，可以再次采用牛顿迭代法来计算（当然需要实现计算处这些方程的导函数，最后还需要对矩阵求逆）
同样，对于那个田埂问题，在已经拥有近似解的模式下，也可以采用类似的方法，只是对于那个问题，采用变量略微不同，出了各个区域顶点的坐标以外，另外的变量可以采用每条边的曲率（半径的倒数）和长度作为变量