计算机网络中的最优性原理

计算机网络中的最优性原理表述如下 −

解释

路由器上的路由算法的目的是决定传入数据包应该走哪条输出线路。从特定路由器到另一个路由器的最佳路径可能是成本最低的路径、距离最短的路径、时间最短的路径、最少的跳数路径或上述任意组合。

最优性原理可以逻辑地证明如下 −

• 如果可以在路由器 J 和路由器 K 之间找到更好的路由，则从路由器 I 经由 J 到路由器 K 的路径将通过此路由进行更新。因此，从 J 到 K 的最佳路径将再次位于从 I 到 K 的最佳路径上。

示例

考虑一个路由器网络，{G、H、I、J、K、L、M、N}，如图所示。让从 I 到 K 的最佳路线如绿色路径所示，即通过路线 I-G-J-L-K。根据最优性原则，从 J 到 K 的最佳路径将沿着相同的路线，即 J-L-K。

现在，假设我们发现从 J 到 K 的更好路线，比如沿着 J-M-N-K。因此，我们还需要将从 I 到 K 的最佳路线更新为 I-GJ-M-N-K，因为在这种情况下，之前的路线不再是最佳路线。下图中橙色线显示了这条新的最佳路径 −