上周末到这周三，和实验室的大腿们组队参加了数模竞赛，感觉那几天的朋友圈都被这张图刷屏了。
image.png
没错，就是这样！
如果说将各个看似毫无关系的条件罗列，逻辑从中剥离，这过程很艰难但也很有成就感的话。那么（因为题目表述不清或者其他各种各样的原因）一遍遍修正思路的过程，就很艰难又很挫败了。
队友们都很给力，勉强带动了我这个小坑货。
分工虽然不明确，但个人认为也明确不起来，因为这次建模的过程中“论文、算法、程序实现”几个部分耦合挺厉害的，而且中途多次修改方案，写论文的人如果不参与到算法中来，很难确切地描述思路，写算法的也需要有个人讨论，另外得夸一句小红的程序能力真是厉害，写起来又快又准。
接下来大致介绍一下本次建模时用到的一些算法吧。
一、图的最小生成树算法
图的最小生成树用于求解在多个点之间铺设线路的问题，当图中边的权是铺设线路的长度时，可以使得线路总长最短，而当边的权是线路的成本时，可以使得线路总花费最小。
就是因为一开始就知道有这个算法，我们才会选坑爹的F题的！
这个算法有两种基本的实现方法，分别是Prim算法和Kruskal算法。
Prim算法的思路是这样的：随机选择第一个顶点接入——>while（并非所有元素都接入）——>{寻找未接入的、与当前已接入顶点距离最短的顶点——>接入——>以新加入的顶点为起点，重新更新已接入的顶点与其他未接入顶点的最短距离}。
Kruskal算法的思路是这样的：假设总共有n个顶点，先则出所有边的起点、重点和权重——>按权重从小到大排序——>while（总边数<n-1）——>{边权重最小的顶点先接入——>如果新加入的两个顶点都在接入后的子图中则舍弃这条边}。
二、重心法
重心法可以用于定点选址问题。比如知道几个地方的贸易总量和地理位置，利用重心法可以算出理论上销售成本最短的贸易中心。
重心法的思想把分布的各个贸易总量不同的点看作一个不规则且不均质刚体，贸易中心应该建在重心，公式了就不打了，现在也有很多针对重心法的改进算法，比如精确重心法等。个人感觉重心法的思想推广性很强，但不知为何没有找到它在其他方面的应用。
三、谱聚类法
聚类方法的名字来源于“物以类聚，人以群分”，用于给一堆物体分类，是一门亚种繁多的算法。
谱聚类是聚类的一个亚种，其思想源于图论，即一堆物体中的每个物体都对应图中的一个顶点，这堆物品之间相似度是图的权。对图进行切割，要求切割后不同子图之间的边的权尽量低，而子图内部的边的权尽量高。
确定边权重（即相似度）可以采用全连接法，物品之间的相似度是物品间欧氏距离的函数。
图的最小切割，本身就是一个被广泛讨论的问题。一种常用的方法是RatioCut，要求切割的边权与切割后子图包含定顶点数的比最小（即边权尽量小，子图中点数尽量多）。另一种方法是NCut，比RatioCut更优一些，衡量指标不是顶点数而是权重。
参考资料：http://www.cnblogs.com/pinard/p/6221564.html
http://www.cnblogs.com/wentingtu/archive/2011/12/22/2297426.html
四、其他算法
以上几种算法都用于权重已知的情况，如果权重是结果的函数，就需要对这几种算法改进。拟采用遗传算法和线性规划，但由于时间问题并未付诸实践。以后下周有时间的话希望能好好研究一下。
后补充：
模拟退火算法
启发式算法的共同点就是“来源于生活”。退火法是一个随机性很强的算法，可以适当地增加退火粒子数量，增加找到合适点的概率。
MATLAB代码连接：https://pan.baidu.com/s/1i5w1kIL 密码: ngew
参考资料：
https://zhuanlan.zhihu.com/p/21277465
http://blog.csdn.net/google19890102/article/details/45395257
遗传算法
一个神奇的算法，一个看了定义和大概实现方法之后只会觉得“什么鬼？”，但看了例子之后又觉得“就是书上说的‘编码’、‘遗传’、‘交叉’、‘变异’、‘选择’啊……”，的算法，一个实现过程就像传说中那么玄乎的算法。
总觉得用遗传算法解一维问题太大材小用了，体现不出遗传算法的优势。
代码是仿照知乎中的高票答案写的。
MATLAB代码连接：https://pan.baidu.com/s/1slRYSCP密码: 8jdh
参考资料：
https://www.zhihu.com/question/19885905（里面有具体例子，非常好）
https://www.zhihu.com/question/23293449
参考资料：
https://www.zhihu.com/question/29762576
http://blog.csdn.net/emiyasstar__/article/details/6938608/
网友评论