USACO/fence3
来自"NOCOW"
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 5 .2中的OI题目Electric Fences的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 问题分析
首先很容易看出，这道题目精度要求并不高，所以我们完全可以把所有数据扩大10倍，这样就可以按照整数来处理了。 PS：针对下面两个算法提下自己的意见。这种逐渐加精度的搜索方法是可以过Usaco的，但是并不代表是严谨的。我们如果根据每个点做电源时的最短电线绘制一个类似等高线的等距图，那么可能存在一个大坑和一个小坑，大坑的最低点就是答案，但是在搜索的时候我们掉进了小坑出不来，那么将无法找到答案。 PS：针对上面的评论提一下自己的意见。下面的模拟退火似乎不太标准。如果用标准的模拟退火的话应该可以随机掉这个问题，因为标准的模拟退火在比原解劣的情况下仍有可能接受这个解。 PS：+-1范围内搜索10000次就过了...
[编辑] 算法一
局部搜索。
当供电点固定后，计算电网的总长度并不难，这道题的核心任务就在于找到这个点。对于查找这个点，采用一般的搜索是会超时的。采用了“局部搜索”的方法。就是先以一个较大的距离网格扫描，找到目前使结果最短的点的坐标。最终结果一定在目前找到的点的附近，然后对这个范围进行细化的搜索，直到找到要求的精度为止。
参见 [1]
[编辑] 算法二
随机化。
题目的精度要求不高，采用迭代逼近的思想，首先随便选一个点，确定一个长度范围，在这个长度范围内随便向一个方向走任意的长度，如果这个点比先前的点更优则替换。重复足够多次以后，将长度范围缩小一点，继续迭代，直到长度范围=0。这样所得到的解在精度范围内几乎绝对是正确的。（我取的长度范围是30，随机500次，长度范围缩小值为1，以上全部都是扩大10倍以后的数据） ——即是传说中的模拟退火算法
[编辑] 算法三
数学计算。
具体方法很恶心，不推荐。[需要证实]
[编辑] 算法四
二維三分搜索。
題目相當於求二元函數的極值，可先對y進行三分。y固定後，題目相當於求一元函數的極值，此時對x進行三分搜索。
[编辑] 算法五
很多随机算法，比如遗传算法也是可以的。 详情请见C++代码.
