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

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

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

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

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

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

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

最终的路径为:

代码如下:

运行结果:

1:输入样例

2:输出结果

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云时之间

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

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

1221
来自专栏Phoenix的Android之旅

在Android上用AI识别物体

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

3106
来自专栏企鹅号快讯

深入机器学习系列7-Random Forest

1 Bagging   采用自助采样法()采样数据。给定包含个样本的数据集,我们先随机取出一个样本放入采样集中,再把该样本放回初始数据集,使得下次采样时,样本仍...

4886
来自专栏鸿的学习笔记

写给开发者的机器学习指南(四)

查全率是定义由给定查询和数据语料库的算法检索的相关性的大小。因此,给定一组文档和应该返回这些文档的子集的查询,查全率的值表示实际返回了多少相关文档。 此值计算如...

651
来自专栏人工智能LeadAI

简易的深度学习框架Keras代码解析与应用

总体来讲keras这个深度学习框架真的很“简易”,它体现在可参考的文档写的比较详细,不像caffe,装完以后都得靠技术博客,keras有它自己的官方文档(不过是...

6797
来自专栏编程

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

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

2057
来自专栏互联网大杂烩

逻辑斯蒂回归(Logistic Regression)

定义x=<x1,x2,...xn>来表示n维特征向量,权重为w=<w1,w2,...wn>,同时,截距(Intercept)为b。则这种线性关系为: f(w,...

992

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

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

2.8K8
来自专栏用户2442861的专栏

计算图像相似度——《Python也可以》之一

声明:本文最初发表于赖勇浩(恋花蝶)的博客http://blog.csdn.NET/lanphaday,如蒙转载,敬请确保全文完整,未经同意,不得用于商业用途。

1.1K2
来自专栏木东居士的专栏

漫谈机器学习之小知识点总结

1884

扫码关注云+社区

领取腾讯云代金券