从疫情到求解最短路的Floyd算法
忽然间,还有两周多就要过年了。
不知是气温下降,还是临近春节人口流动较大,亦或是奥米克戎变种传播性强大,近期也是多出小疫情不断反弹。前文笔者还在考虑拜访亲朋是否可行,最近几周,深圳,也就是笔者所在的城市也出行了新冠感染。这导致一个问题:各地的防疫政策基本都要求中风险地区回乡需经历隔离。
不过万幸的是,本次疫情受到政府和人民的高度重视。迅速的控制住了局势,阻止了疫情的进一步传播。希望深圳在接下来的几周内能不断保持 0 新增,深圳稳住!
当然,本文会以此展开,从计算机的角度去做一些分析。
(本文讨论的疫情相关问题只为引申出算法知识,不含任何额外拓展含义。)
关于前文信息可以点击连接查看游戏2048(C++版)
首先回顾一下图的存储,我们用的是最简单的方式——二维矩阵:
IsConnected数组只是单纯的用 0 和 1 来描述是否有边。如果说,我们不仅仅关心地点是否连通,还关心其他信息呢?
比如说,假如从 x 到 y 需要隔离 7 天, 从 y 到 z 又 需要隔离 7+7 天。而从 x 到 z 只需要 2+14 天。考虑到大家春节放假的时间不长,所以我们现在的问题就变成了——给出各地的防疫政策,求从 x 到 y 最少花费几天。
当然计算机处理现实问题一般需要将其做抽象,建立数学模型。
因此我们假设,在前文的基础上,给每条边设置一个权重,表示花费时间。现求一条从 x 到 y 路径,使得路径上边的权重之和最小,问这个最小值。其实这也就是算法中很经典的最短路问题。
那么很显然,IsConnected数组不能再单纯的只有 0 和 1 了,因为我们还有保留边的权重问题。接下来处理几个小问题:
1.边权如何表示?
答:将 IsConnected数组修改为 Cost数组。
2.怎么表示有边和无边?
答:有边则让 Cost数组有正常值,无边则将值修改为无穷大即可(计算机中无穷大一般用一个较大数字代替,比如 16 进制数字:0x3f3f3f3f)。
3.x 到 y 如果有多条边,每条边的权重不一,如何思考?
答:取最小边即可。因为最小的是最优方案,所以永远不会经过其他变。
所以边的处理如下:
ok,现在问题来到了最后一步,或者是终于回到了一开始的问题,如何求解最短路?
这边提供一种经典算法,Floyd算法。其本质是一个动态规划问题,如果讲述所占幅度较大,有些繁琐,具体原理这边不做过多解释,有兴趣的同学可以自己去网络查询。
那么做完这个看起来很繁琐的三重循环后,我们就可以直接求得任意两点之间的最小权重之和了。就存储在 Cost数组里。也就是说:
Cost数组现在是表达任意两点之间的最短距离。
那到这今天的问题就结束啦。各位也可以尝试一下这边的代码内容,来求解图上任意两点的最短路问题。当然前提是有一个合适的数学模型以及相应的数据,这方面可能就需要各位自己来总结和提炼了。
原创文章,作者:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司,如若转载,请注明出处:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司