今天我来跟大家聊聊这个叫作“Bellman”的玩意儿,它是一个算法。我一开始也是一头雾水,不知道这是个后来自己琢磨一番,总算是弄明白点儿。
我是从哪儿知道这个的?忘,反正就是在网上瞎逛的时候看到的。我就好奇,这啥玩意儿,听着挺玄乎的。然后我就去查查,发现这东西主要是用来算那个什么“最短路径”的,就是从一个点到另一个点,怎么走最近。听着好像挺简单的,但实际操作起来,还真有点复杂。
我这个人,喜欢自己动手试试。我就开始自己琢磨这个算法。我得有个图,就是那种点和线连起来的图。这个图我是自己随便画的,几个点,几条线,还给每条线都标个数字,表示这条线的长度。这个长度可以是负数,这就是这个算法厉害的地方,能处理负数的边。
我就开始按照网上说的那个步骤来操作。先是初始化,就是把所有的点到起点的距离都设成无穷大,然后把起点到自己的距离设成0。这一步还挺简单的,我就用一个数组,把每个点对应的距离都写进去。
然后就是那个叫作“松弛”的操作。这一步我琢磨半天,就是看每条边,比如说从点A到点B有一条边,长度是5,那么我就看看,从起点到点A的距离,加上这条边的长度,是不是比现在已知的起点到点B的距离要短。如果是的话,那就更新一下起点到点B的距离。这一步我写一个循环,把所有的边都遍历一遍。
- 先画个图:自己随便画几个点和线,给每条线标上数字(长度)。
- 初始化:把所有点到起点的距离设成无穷大,起点到自己的距离设成0。
- 松弛操作:遍历所有边,看能不能通过这条边缩短起点到某个点的距离。
这个“松弛”操作,我要做几轮?网上说是点的数量减一次。比如说我有5个点,那我就要做4轮。这个我也不是很明白为反正就照着做。每一轮,我都把所有的边都“松弛”一遍。做完之后,我就得到一个数组,里面记录从起点到每个点的最短距离。
实践心得
自己这么一通操作下来,我还真感觉有点意思。虽然这个算法看起来挺复杂的,但实际上,就是不断地尝试,看看能不能找到更短的路径。我觉得这个思想还是挺巧妙的。这个算法也有它的局限性,就是效率比较低。如果点的数量和边的数量很多的话,算起来会很慢。不过对于我这种只是想解一下算法的人来说,已经足够。
这回实践还是挺有收获的。虽然过程有点曲折,但还是弄明白。以后再遇到这种问题,我就知道该怎么解决。而且通过这回实践,我也对算法这个东西有更深的理解。以前总觉得算法很神秘,现在看来,也没那么难嘛只要肯动手,肯琢磨,总能弄明白的。
好,今天就跟大家分享到这里。希望我的这点儿经验能对大家有所帮助。如果你也对这个“Bellman”算法感兴趣,不妨自己动手试试看!说不定你会有新的发现!


还没有评论,来说两句吧...