文学驿站

手机浏览器扫描二维码访问

第57章教不教求追读（第1页）

林婉听了江凡的话，赶忙拖着餐盘做到江凡旁边的位置，

江凡把手机放两人中间，给她解释道：

“这就是一个旅行商问题，用的是图论的知识，

我们可以把它抽象成一个点线的图，点代表7个城市，线代表彼此之间的航程，

线有权重，就代表他们之间的机票......”

江凡说的这个就是数学建模的一般思路，把现实的问题抽象成数学问题，

借助数学的一些方法以及计算机的算力进行解决，然后可以反过来指导现实的生产。

而他们手里的旅行商问题又是其中很经典且实用范围很广的问题，属于优化组合范畴，是经典的NP难题，

包括电路布线、输油管路铺设、连锁店的货物配送路线等，经过简化后建模都可以变成旅行商问题，所以有很大的应用价值。

当然，解决思路也很多，但江凡不想给林婉讲太复杂的，就选其中理解起来最简单的一个‘蛮力算法’来给她讲，

于是接着道：“把这个问题抽象成一个完全图后，算一下它的全排列个数，把这些可能都列出来，比较一下它们的大小就行了。”

说的同时也用手机画图软件把点线权重图给画出来了。

接着给林婉提了问题：“你觉得有多少种组合？”

林婉这个简单的还是会的，手机计算器算了下：

7！

=7*6*5*4*3*2=5040种。

“这么多啊。”

林婉嘴抽抽。

“真需要这么多吗？”

江凡引导，看她想不出来，就直接解释了：

“这个问题最后会形成一个哈密尔顿回路，额，就是指可以一笔都把连起来，

所以从哪个点开始是无所谓的，也就是只需要算6的全排列，这样就只有720种可能了。

又因为我们关心的回路是没有方向性的，因此在这些排列中两个对称的也只需要考虑一个，所以还可以再除以2，这样就只剩下360个了。”

江凡循循善诱道。

“可是360个也很多啊，要一个个算出来嘛。”

林婉还是很苦恼。

“你听你刚才那个学长说的，只用给解题思路就行了。”

江凡知道建模这东西结果不重要，反正有计算机去算，重要的是思路。

“对哦。”

林婉也反应过来，喜出望外，拍了一下江凡胳膊：“凡哥，你太棒了。”

江凡心想我这两天胳膊快被你拍废了。

问题解决，吃完午饭，两人找了间教室趴着休息了一会，下午按点去机房，

两个学长已经在里面了，江凡找了个角落继续玩他的游戏，

林婉则到黄伟学长旁边，给他讲了上午问题的分析思路。

黄伟还问了非完全图怎么弄以及花费最小和访问每个节点恰好一次是否冲突之类的衍生问题，

因为江凡猜到对方可能会提，也提前跟林婉讲了，所以林婉依然对答如流，

这让黄伟学长稍稍觉得有些意外，以前问她题目，给的都是一些粗浅的理解，甚至有时给出的思路连题目都没看全，

结果这次的问题，虽然也很基础，但相比较她之前的表现简直有点天差地别，长进了啊。

林婉能够察觉到学长的表情是微微有些讶异的，心里也很得意，还得是凡哥。

黄伟难得点点头，道：“不错，思路完全正确，不过你可以考虑下除了‘蛮力算法’，还有没其他算法思路。”