网络设备硬核技术内幕 路由器篇 3 贾宝玉梦游太虚幻境 (中)

上回说到，贾宝玉在太虚幻境中需要尽快找到黛玉，才能返回大观园。

幸好，贾宝玉想到了，利用出生时所含之通灵宝玉之超能力，向每个岛上的金钗仙子询问：如何才能找到黛玉？

但是，只有离黛玉最近的金钗，湘云、宝钗和元春三位知道，黛玉是自己的邻居。其他金钗并不知道。

如下图，红圈中的1代表到黛玉的跳数：

湘云、宝钗和元春都会通知自己的邻居，自己可以通过1跳直连黛玉。

如图，惜春和凤姐都可以从宝钗处知道去往黛玉的路径（学习到路由）。由于宝钗通告自己到黛玉的跳数为1，凤姐和惜春将自己到黛玉的跳数增加1，为2跳。

惜春学习到通往黛玉的路由后，也会向凤姐通告自身到黛玉需要2跳。凤姐进行比较，发现自己通过惜春到黛玉需要3跳，并非最优路径，就不选择这条路径通往黛玉。

问题来了。

惜春和凤姐都会向对方通告，从自己这里可以找到黛玉。这有可能会造成两位金钗把宝玉当作皮球踢来踢去。因此，宝玉制定了一条规则：从谁这里学到的路由，不再通告给对方。这条规则叫做水平分割。

这样一来，最后太虚幻境的网络路由计算结果如下：

可以看出，宝玉可以通过迎春/惜春，宝钗找到宝玉。

但是，宝玉在路过宝钗的时候，会被宝钗勾引走拜堂成亲，最后没有和黛玉在一起……

而宝玉又嫌弃凤姐丑(大家都嫌弃，不只是宝玉一个)，不想见到她。

所以，我们要设法让宝玉避免路过宝钗和凤姐。从网络中将这两个节点删除，重新计算路由：

于是，宝玉就可以通过这条路径找到黛玉了：

我们看到，在宝钗和凤姐这两个节点离线以后，各个节点的路由可以自动重新计算，最后重新得到了通往目的地址(黛玉)的最佳路径。最佳路径以中间经过的节点数为准。

由于路由可以自动动态计算，我们管这种路由计算方式叫动态路由协议。这种以节点跳数度量距离的动态路由算法，叫做距离矢量算法，代表性的路由协议为RIP协议。

但是，这样真的能帮助宝玉最快速度找到黛玉吗？

事实上，各个小岛(节点)之间的距离(链路开销)并非完全相等。实际上，小岛之间的距离是这样的：

宝玉哥哥还能最快找到林妹妹吗？

请看明天的专题。

今天遗留的问题：宝玉通过迎春和惜春都可以在3跳到达黛玉，那么会选择哪条路径呢？

昨天遗留问题答案：

计算从宝玉到黛玉的距离并不是NP-Hard问题。如果警幻仙子给宝玉出了什么样的题目，才是NP-Hard问题？

如果指定必须经过特定的点，并寻求最短的路径，属于NP-Hard问题，也就是无法在多项式复杂度的时间内得到解。