火车站的最佳位置

KeyTo9_Fans

要否定四边界共点是最优的，那么就应该仔细考察$N=4$和$N=9$的情况。

当$N=4$时，最短田埂问题的答案不是分成$4$个小正方形，而是将田埂拉成三叉状。

对于此问题，参考最短田埂问题的答案，$4$个点摆成菱形状就可以避免四边界共点，形成三叉状。

如下图所示：



然而凭感觉看，这个答案并不是最优的。

离中心较远的$2$个点有向中心靠拢的趋势，而离中心较近的$2$个点有远离中心的趋势。

当$4$个点与中心的距离相等时稳定下来，形成$4$个小正方形。

mathe

利用我前面想到的迭代方法写了个随机算法的程序，不过发现迭代收敛速度还是挺慢的。
函数
genCenters(K,N,ERR)
用来产生一个随机解，其中K是火车站数目，N是迭代次数，ERR是使用的误差（需要注意的是如果计算精度不够高，而是用误差ERR很小，可能会出现除0错误，这时可以降低迭代次数或增加误差或提高计算精度）
对于计算出来的解，可以调用函数getTotalT(..)来计算这个解的平均距离。

mathe

部分计算过程:
? \p
   realprecision = 38 significant digits (20 digits displayed)
? genCenters(3,100,1e-10)
%173 =
[0.50001314437628946040 0.20855638949725765617]

[0.76565467355489545422 0.69042389777839742687]

[0.23433861084747588480 0.69040623063531377332]

? genCenters(3,1000,1e-10)
%174 =
[0.79144361052635529774 0.50000000000000000000]

[0.30958493536250887521 0.23434196856282313452]

[0.30958493536250887521 0.76565803143717686548]

? \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 =
[0.249999992136344046528784923755 0.749999992008232418196524125938]

[0.250000007863718325203001513467 0.249999992008232856423429200642]

[0.750000007863717882935451814051 0.250000007991723942923804104817]

[0.749999992136343604265381271620 0.750000007991723504699868136972]

? genCenters(4,50,1e-10)
%176 =
[0.249999999952009981228512107622 0.250000000105464018074517877686]

[0.749999999952009981185102435910 0.249999999894536518627827735759]

[0.750000000047989513129584826464 0.749999999894536518605768704461]

[0.250000000047989513172994290102 0.750000000105464018052458367789]

? genCenters(5,50,1e-10)
%177 =
[0.761345254535713127079103774090 0.755348861596047735807542947098]

[0.310808148356488800910091962576 0.500000148444991700531222851009]

[0.240380759484490069874508544618 0.169444301010067156815101320715]

[0.240380752464826531221607839851 0.830555844954500163304377975230]

[0.761345219745332982380149136406 0.244651149788284257299640149042]

? genCenters(5,50,1e-10)
%178 =
[0.244974018334860028837432630538 0.238828533953388336867257475519]

[0.831105790407222934150066484146 0.758660463568066668102893786796]

[0.168894169965836434160879919877 0.758660463854306885094532548623]

[0.499999960089810246499320517573 0.692027764358028691302760418157]

[0.755025979490275689964627097097 0.238828543800014254650105380094]

? genCenters(5,50,1e-10)
%179 =
[0.499999979676888015243997048913 0.310009208056341535920706887386]

[0.830712591906500600346001550674 0.240648352118741440477818054494]

[0.244741868658317028951256710820 0.761295617564467641663201043479]

[0.169287388048427013546983814115 0.240648351411907271277973723850]

[0.755258129932865313627174566373 0.761295612713074353237057841316]

? genCenters(5,500,1e-10)
%180 =
[0.756340850451555744884430591004 0.238076219757519160077353416511]

[0.828727847022804549756557201482 0.762456521538049853916004695226]

[0.500000000000000000000000000000 0.680349838876930919422126658399]

[0.243659149548444255115569408996 0.238076219757519160077353416511]

[0.171272152977195450243442798518 0.762456521538049853916004695226]

? setrand(1000)
%181 = 1000
? genCenters(5,500,1e-10)
%182 =
[0.219974916539819067099987529596 0.780025083460180932900012470404]

[0.780025083460180932900012470404 0.219974916539819067099987529596]

[0.780025083460180932900012470404 0.780025083460180932900012470404]

[0.500000000000000000000000000000 0.500000000000000000000000000000]

[0.219974916539819067099987529596 0.219974916539819067099987529596]

? \r train
? getTotalT(%182)
%183 = 0.174786180973170660322941393138
? getTotalT(%180)
%184 = 0.175660708263854388172181275707
? genCenters(5,500,1e-10)
%185 =
[0.780025083460180932900012470404 0.780025083460180932900012470404]

[0.500000000000000000000000000000 0.500000000000000000000000000000]

[0.219974916539819067099987529596 0.780025083460180932900012470404]

[0.780025083460180932900012470404 0.219974916539819067099987529596]

[0.219974916539819067099987529596 0.219974916539819067099987529596]

? getTotalT(%185)
%186 = 0.174786180973170660322941393138
? genCenters(6,500,1e-10)
%187 =
[0.783660324770699185702354695048 0.796828548414195840887567497840]

[0.500000000000000000000000000001 0.160510658264000958605107627579]

[0.500000000000000000000000000000 0.549771461115572537533693931415]

[0.216339675229300814297645304951 0.796828548414195840887567497840]

[0.840331672325631673586317646987 0.273786573419332543555816207635]

[0.159668327674368326413682353013 0.273786573419332543555816207634]

? getTotalT(%187)
%188 = 0.160771534476707546590248210081
? genCenters(7,200,1e-10)
%189 =
[0.736408436877698647419471851577 0.149903685626746665862911463692]

[0.822355951147032313466949180616 0.479930953173220085056033467326]

[0.440240066956345251283496182344 0.440240066956400224107558748794]

[0.827090607015998531802450481554 0.827090607015971588090550363507]

[0.197231092812677723812412925369 0.197231092812683898428498666931]

[0.149903685626756201361755020793 0.736408436877752184728745154231]

[0.479930953173276686247451496342 0.822355951147037368440837750309]

? getTotalT(%189)
%190 = 0.148592718737155249948954581302
? genCenters(7,200,1e-10)
%191 =
[0.197231092812681304513849171883 0.197231092812684659776668534130]

[0.736408436877707542619161581941 0.149903685626747509673831812285]

[0.827090607015989620684178241197 0.827090607015974979573986921279]

[0.440240066956364540217369210494 0.440240066956394412240029413321]

[0.822355951147037731562833134428 0.479930953173228020800388443319]

[0.479930953173258777671738003290 0.822355951147040478416323571212]

[0.149903685626752691227519142096 0.736408436877736634588610881401]

? getTotalT(%191)
%192 = 0.148592718737155249948954618912
? genCenters(7,200,1e-10)
%193 =
[0.474245098633189029096342169076 0.752713912329618057189735044084]

[0.158053940727921148562873944409 0.751473763595615593640608435451]

[0.476022901957186601842423634374 0.238800697485384842292642673064]

[0.793199408907365813913126735674 0.499640708552930106629768302573]

[0.822541241719569500083577003578 0.161495203163019188042272156325]

[0.820388148429908005676328654965 0.839029914296686248978402497080]

[0.158909574581454436019622640899 0.255510331112718061310890304809]

? getTotalT(%191)
%194 = 0.148592718737155249948954618912
? getTotalT(%193)
%195 = 0.148810411888737275049524820469
? genCenters(7,200,1e-10)
%196 =
[0.849956181353029296430735040078 0.500000000000289861623119666064]

[0.748970498093881310119222853974 0.839877588043227304476678146743]

[0.499999999999999999999999999360 0.500000000000000009809780903021]

[0.251029501906118698402902347639 0.160122411956772692249775219126]

[0.748970498094183177792783190562 0.160122411956958884569025032830]

[0.150043818646970703569264959323 0.499999999999710118233606539389]

[0.251029501905816813685091607613 0.839877588043041112157428333176]

? getTotalT(%196)
%197 = 0.148107927307609628274837275884

mathe

上面迭代的方法由于收敛速度比较慢，只能得出一个近似解。
在得出一个近似解以后，我们可以假设真正的解的模式和这个近似解相同。此后我们可以通过假设所有Fans心的坐标和各个区域顶点的坐标为未知数。由此，每个Fans心对应两个未知数，每个内部的区域顶点两个未知数，边界上的区域顶点一个未知数。
而根据Fans心的条件，可以得出两条方程（也就是40#中的$T_x=0,T_y=0$）。而对于区域每条非边界的边，必然有两个Fans心关于它对称，由此，又可以得出两条方程（Fans心的连线和这条边垂直，中点在这条边上）。
而解这个超越方程必然可以得出解。而由于我们已经有一个不错的近似解，可以再次采用牛顿迭代法来计算（当然需要实现计算处这些方程的导函数，最后还需要对矩阵求逆）

mathe

同样，对于那个田埂问题，在已经拥有近似解的模式下，也可以采用类似的方法，只是对于那个问题，采用变量略微不同，出了各个区域顶点的坐标以外，另外的变量可以采用每条边的曲率（半径的倒数）和长度作为变量