|
本文介绍热带算术和动态规划的联系,旨在容易理解,不求精确。
内容摘自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.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-6 03:20
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社