算法导论系列:贪心算法(2)

这篇文章我们将来一起看看贪心算法一个具体例子, Dijkstra算法

Dijkstra算法最著名的应用是解决单元最短路径,这是一类贪心算法,他先是求出长度最短的一条路径,然后参照这一条最短路径去求出长度次短的路径,知道求出从起点到各个定点的最短路径.

这个算法不仅仅是贪心算法,其实也是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心每次可以求得最优的独立子问题,这两者有一些交集,但是收到很多约束,会影响适应的范围.

举例:今天你去一个景点去玩,景点地图如下,假如你从1号点出发,那到达其他各个节点的最短路径是什么?

现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

下图是算法的过程(用电子屏幕写字果然很不舒服):

最终的路径为:

代码如下:

运行结果:

1:输入样例

2:输出结果

下一篇文章我们将一起学习下哈夫曼编码

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

GAN学习指南:从原理入门到制作生成Demo

作者:何之源,复旦大学计算机科学硕士在读,研究方向为人工智能以及机器学习的应用。 生成式对抗网络(GAN)是近年来大热的深度学习模型。最近正好有空看了这方面的...

2769
来自专栏技术沉淀

03 Types of Learning

从Output Space/Data Label/Protocol/Input Space四个维度介绍常见机器学习类型,见详细课件。

1681
来自专栏Phoenix的Android之旅

在Android上用AI识别物体

AI其中一个很重要的应用就是物体识别。 今天我们来看看如何在Android上实现这个功能。

2385
来自专栏大数据挖掘DT机器学习

如何用TensorFlow和TF-Slim实现图像标注、分类与分割

本文github源码地址: 在公众号 datadw 里 回复 图像 即可获取。 笔者将和大家分享一个结合了TensorFlow和slim库的小应用,来实现...

5824
来自专栏利炳根的专栏

学习笔记CB010:递归神经网络、LSTM、自动抓取字幕

递归神经网络(RNN),时间递归神经网络(recurrent neural network),结构递归神经网络(recursive neural network...

5864
来自专栏Coding迪斯尼

从零开始构造一个识别猫狗图片的卷积网络

在深度学习的项目实践中,往往会遇到两个非常难以克服的难题,一是算力,要得到精确的结果,你需要设计几千层,规模庞大的神经网络,然后使用几千个GPU,把神经网络布置...

1982

用Python的长短期记忆神经网络进行时间序列预测

长短期记忆递归神经网络具有学习长的观察序列的潜力。

2.7K8
来自专栏AI研习社

Tensorflow 中 learning rate decay 的奇技淫巧

深度学习中参数更新的方法想必大家都十分清楚了——sgd,adam 等等,孰优孰劣相关的讨论也十分广泛。可是,learning rate 的衰减策略大家有特别关注...

5064
来自专栏编程

关于反向传播在Python中应用的入门教程

我来这里的目的是为了测试我对于Karpathy的博客《骇客的神经网络指导》以及Python的理解,也是为了掌握最近精读的Derek Banas的文章《令人惊奇的...

2047
来自专栏大数据文摘

手把手 | 亲测好用!Google发布了一个新的Tensorflow物体识别API

2243

扫码关注云+社区