longyangjing的个人博客分享 http://blog.sciencenet.cn/u/longyangjing

博文

从图的最短路问题看热带算术和动态规划的联系

已有 1834 次阅读 2018-1-23 20:23 |系统分类:科研笔记

本文介绍热带算术和动态规划的联系,旨在容易理解,不求精确。


内容摘自Algebraic Statistics for Computational Biology, (Lior Pachter, Bernd Sturmfels), Cambridge University Press, 2005.


1. 热带算术的定义


加法和乘法  x?y := min(x,y) and xy := x+y.


热带算术的表格




2. 一个求图的最短路的例子





3.证明


The iterative evaluation of the formula (2.2) is known as the Floyd-WarshallAlgorithm [Floyd, 1962, Warshall, 1962] for finding shortest paths in a weighteddigraph. Floyd-Warshall simply means performing the matrix multiplication

Dr = Dr1 DG for r = 2, . . ., n 1.




https://wap.sciencenet.cn/blog-3353914-1096435.html

上一篇:在德国监考口试(2)
下一篇:关于科研方向的思考

1 黄仁勇

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-1-26 08:21

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部