( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230624{main}( ).../view.php:0
20.0001231368include( '/var/www/html/head.php' ).../view.php:2
30.0010250728isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(23)-网络

小学计算思维课程(23)-网络

小学计算思维课程(23)-网络

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com

第二十三课:网络

网络在我们的生活中随处可见,互联网、电网、交通网等等,有些网络非常复杂,比如我国的公路交通网,它比蜘蛛网可复杂多了。网络主要由“节点”和“连接”组成,比如下面这个“杭州—北京路线图”,杭州和北京就是两个节点,它们之间的路线就是连接。本节课主要研究的就是怎样寻找高效连接网络中各节点的方法。下面我们通过一个游戏来体验一下网络的魅力。

公元2498年,新人类在“斯坦星”上建立了第一个城市,但这座城市还未铺上道路,一下雨,地面就被雨水浸透,满是泥泞,车辆纷纷陷入泥沼之中,人们的鞋子上沾满了泥水。现在市民们都迫切的希望为一些道路铺上石砖。因为经费太少,市长要求:

1.道路要足够让每个人都能从他家沿着石砖走到别人的房子。

2.所铺的砖块越少越好。

如果这个城市只有三幢房子和3条路,达到上面的要求还是挺简单的。请看下图并思考下面的问题:

1.如果从房子A走到房子C,你会怎么走?

2.上面最少需要几块砖块才能达到要求?

很显然,3所房子很容易解决,让我们来试一试5所房子的问题,请看下图,用最少的砖块,哪些路是必须铺上的?

问题:

1.你一共用了多少块砖块?

2.从房子A到房子D,你会走哪一条铺好的路?

3.还有更好的铺法吗?为什么?

4.从房子B到房子E,哪条路比较近?

从上面的游戏中你可能已经注意到,使用最少的砖块铺的路线,不一定能让两幢房子间的路线最短。像上面这样设计出总长最短的网络,在计算机科学中被称为“最小生成树问题”。在上面的问题中,最小就表示要使用最少的砖块,但必须保证所有节点可以连通。要保证总长最小,就不能有回路或相交,如果有了,说明将有两条道路通往同一幢房子,其中的一条一定是浪费砖块的路线。想一想在生活中还有什么最小生成树的应用吗?(提示:房子间还有什么连接?)

上图中的节点可以用圆圈表示,道路可以用线条表示,砖块的数量可以用数字表示,这样绘制而成的网状结构在计算机上就称为“图”(graph),见下图:

问题:

1.上图中有多少个节点?多少条连接?

2.能用“图”来表示前面5所房子的问题吗?

图是一种特别的结构,它的重点是节点、节点之间的连接和连接的长度,所以对图进行旋转是没有意义的。如下4个图都表示相同的意思。

下面是一个更大的城市:

1.如何使用最小的砖块,找出连接全部房子的最佳路线?(提示:千万不要有循环路线)

2.画出这座城市对应的“图”。

在现实生活中,我们的网络一般不可能只有一条连接,它往往会有“冗余”,如果一条连接断了,那么还可以从另一条连接走过去,比如公路网、电力网等。但也有一些网络没有或很少有冗余,比如自来水管网,某个主力水管断掉后,总会伴随着一大片小区供水停止。所以自来水网络可以使用最小生成树模型来设计,让所铺设的管线最少。

对于“图”来说,有些图问题非常困难,比如“世界旅行商问题”,它用于寻找世界上1904711座不同城市的最佳访问路径(求访问每一座城市一次并回到起始城市的最短回路),2008年时有人用计算机程序找到7515947.511千米的路径,它比最短路径只多了0.0497%。而据英国科学家研究,在花丛中飞来飞去的小蜜蜂显示出了轻易破解“旅行商问题”的能力。因为蜜蜂每天都要在蜂巢和花朵间飞来飞去,为了采蜜而在不同花朵间飞行是一件很耗精力的事情,所以实际上蜜蜂每天都在解决“旅行商问题”。大自然又一次向我们展示了它的神奇。