第57章 教不教?(求追读)-《交易千年后,开局百万桶石油》


    第(1/3)页

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

    江凡把手机放两人中间,给她解释道:

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

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

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

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

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

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

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

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

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

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

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

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

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

    “这么多啊。”林婉嘴抽抽。

    “真需要这么多吗?”江凡引导,看她想不出来,就直接解释了:

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

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

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

    江凡循循善诱道。

    “可是360个也很多啊,要一个个算出来嘛。”林婉还是很苦恼。
    第(1/3)页