打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
网络与现实生活中的数问题研究

网络与现实生活中的数问题研究

  拓扑学上的网络通常是在各地理位置间画出连接线所形成的.网络的每一段弧线可给予一数字,代表结点间的距离、经过两点所需的时间或连接两点间的电话线路数目等.对有些问题可以用这种方法找到实用而且具有商业价值的答案.本课题即探讨解决这类问题的多种方法.

  最短距离的连接

  把数字当作距离(千米),点当作城镇,找出煤气公司铺设连接所有城镇的煤气管道的最短长度.这个问题是要决定哪一段弧线可以不在网络内,但任何城镇并不被孤立在外,同时弧线的总长度是最短的.

  这个例子的最佳答案如图所示.你的答案是否相同?更重要的是要知道如何求解,你是否了解其策略?是否可以用这种策略来解决类似的问题?

  巡查街道

  把弧线当作警察巡逻区域内的街道路线,弧线上的数字当作走完每条街道所需的时间(分钟).如果警察自A点出发,应该如何走才能以最少的时间走过每条街道?

  如果网络具有穿程性(即可以不重复地走完每一段弧线),则求解就比较容易,但图中的网络不具有穿程性.不过求解时还是要先了解穿程性所要求的条件,可重复几段弧线而有效地将网络转化为具有穿程性的网络.

  本例所需的最少时间为65分钟,路线如下:

  AGBCBACDADEFGEA

  7 11 4 4 5 2 4 3 3 7 3 2 4 6

  推销员的旅行问题

  有一位住在B的推销员想要拜访所有的客户(以网络上的结点表示).弧线上的数字代表各路线的旅行时间(小时).你如何建议这位推销员在最短的时间内走完访问行程?有4种方法可以用32小时走完访问行程.你能否提出一般性的策略来解决这一类问题?

  最短的路径及最长的路径

  对如上所述的简单网络,求取网络上结点间的最短路径是相当明显的问题.但在较复杂的网络中,尤其是在有些弧线上有方向箭头标示“单向”时,求解就变得耐人寻味了。

  我们可以用结点来表示在某段时间发生的事件,如学校音乐会的筹备活动,箭头上的数字表示所需时间(周),如从预订服装至送到的时间,那么筹备此音乐会的复杂过程就可以用有方向性的网络来表示,所需的最长路径称为临界路径(critical path),可以由此算出筹备音乐会所需的最少时间。

  最大流量

  假设第一个网络的结点为电话交换机,弧线上的数字是交换机之间的线路数,探讨G点的用户可以与C点的用户同时通话的最大数目。

本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
简单的dp题(898.数字三角形)
LDP-标签交换协议
那些年网络上的最后神回复!各位复习一下吧
初中最短路径汇总
八上数学最短路径问题
石墨烯又一黑科技,或颠覆数字电路工作方式!
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服