算法_全权教学教材.pptx

实用算法全权可靠飞行控制研究组()自动化科学与电气工程学院北京航空航天大学本节课内容最短路径—Dijkstra算法动态规划1. 最短路径—Dijkstra算法 Dijkstra 提出“goto有害论”; 提出信号量和PV原语; 解决了“哲学家聚餐”问题; 最短路径算法(SPF)和银行家算法的创造者; 第一个Algol 60编译器的设计者和实现者; THE操作系统的设计者和开发者; 与D. E. Knuth并称为我们这个时代最伟大的计算机科学家的人。 曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日）荷兰人1. 最短路径—Dijkstra算法 Dijkstra“对于我来说，计算机科学上的第一个挑战是如何把命令维持在有限个内，然而巨大的、分立的宇宙是复杂地缠绕着的。第二个也是同样重要的挑战是如何传授解决那第一个问题的方法：只培养你个人的才智（那会随你进入坟墓的东西）是不够的，你必须教会其他人如何去发挥他们的才智。你越关注这两个挑战，你越会清楚的看到它们只不过是同一枚硬币的两个面：自学是去发现什么东西是可以被教会的。”?艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日）荷兰人1. 最短路径—Dijkstra算法 问题1. 最短路径—Dijkstra算法 问题1. 最短路径—Dijkstra算法 问题C16128D1E13B13325C25F165451AD2E2G8232337B2C3363F266D3E384 问题：给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径,并限定各边上的权值大于或等于0。3C41. 最短路径—Dijkstra算法AA欧拉(1736)CDDCBB哥尼茨堡城区 图论基本概念 图论起源七桥问题的图1. 最短路径—Dijkstra算法 基本概念若边e是顶点u和v的无序对，则记e = (u, v)或e = (v, u)，称u和v是e的端点，或e连接u和v。两个端点重合的边称为环。若两条或两条以上的边有相同的端点，则这些边称为重边。若顶点u是边e的一个端点，则称顶点u与边e关联。不与任何边关联的顶点称为孤立点。如果两个顶点与一条边关联，那么称这两个顶点相邻。如果两条边与同一个顶点关联，那么称这两条边相邻。1. 最短路径—Dijkstra算法 基本概念没有环与重边的图称为简单图。只有一个顶点的图称为平凡图。任意不同的两个顶点都相邻的简单图称为完全图，有n个顶点的完全图记作Kn。边数为零的图称为零图。1. 最短路径—Dijkstra算法 基本概念定义：在无向图G中，对于每个G中的顶点v，与v相关联的边的数目称为v的度，记为dG(v)，或d(v)。并规定在计算关联边数目时，环算作两条边。定理：在无向图G=(V,E)中，结点度数的总和等于边数的两倍1. 最短路径—Dijkstra算法21312115253232121333333313126666666352434444444412322122222221331155555554552233121233442213113155223312123344 Dijkstra算法例子1????IterationND2D3D4D5D6Initial{1}325??1{1,3}324?32{1,2,3}324733{1,2,3,6}324534{1,2,3,4,6}324535{1,2,3,4,5,6}32453?????1. 最短路径—Dijkstra算法21312115253231233333331266666634444444422122222213311555555552233121233442213113155223312123344 Dijkstra算法例子11. 最短路径—Dijkstra算法 Dijkstra算法[Dijkstra算法] 求有向网络 G=(V, A) 中结点v1 到其它结点的最短距离。 设D为G的距离矩阵，n=|V|，向量U=(u1, u2, …, un)的ui 标记结点v1到vi 的距离。 S为已取得最短路的结点集合，其中每个结点在U中有固定标号标记取得的最短路的长度；S?为未取得最短路的结点集合，其中每个结点在U中有临时标号。1. 最短路径—Dijkstra算法 Dijkstra算法0. 初始化：u1(1) ? 0，uj(1) ? d1j ( j =2,3,…,n)