博文
从图的最短路问题看热带算术和动态规划的联系
|
本文介绍热带算术和动态规划的联系，旨在容易理解，不求精确。
内容摘自Algebraic Statistics for Computational Biology, (Lior Pachter, Bernd Sturmfels), Cambridge University Press, 2005.
1. 热带算术的定义
加法和乘法 x?y := min(x,y) and x⊙y := 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
D⊙r = D⊙r−1 ⊙ DG for r = 2, . . ., n − 1.
https://blog.sciencenet.cn/blog-3353914-1096435.html
上一篇：在德国监考口试（2）
下一篇：关于科研方向的思考
