火车站的最佳位置

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

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