上海城市精神:海纳百川、追求卓越、开明睿智、大气谦和
街镇报: 天平家园鹤翔航头朱家角古镇泗泾 今日九星宝山社区璀璨徐家汇定海家园科瑞物业湖南社区健康枫林今日虹梅今日练塘龙华社区曲阳社区庙行之声北站社区江桥报太平家园嘉兴天地美丽顾村和谐盈浦金泽报道康健社区走进广中川北印象重固家园今日佘山永丰社情友谊社区今日张江今日真如宣桥之声岳阳家园宜居东明新车墩报今日宜川
您现在的位置:首页 > 夜光杯 > 正文

优化算法

  优化算法

  AndrewBoyd(安德鲁·博伊德)文 姜小龙译

  早晨你发现上班路被封闭了,更糟的是许多相关路线都在维修,很难快速比较确定最短路径。没关系,你可以用电脑访问一个网站,寻问:家与办公室最短路径。网站秒算给出答案。如果你输入信息准确,程序将为你提供最短的路线。

  网上程序是怎样计算出最佳路径的?算法并非计算出所有可能路径,然后比较出最短路线。即使借助计算机,这种穷尽算法在休斯敦这类城市,计算时间大约与地球年龄一样长。

  网上程序使用一种特殊优化计算方法,只要所谓“最佳”被清晰定义出来,任何类似问题都能得到解决。

  上班最短路线这类问题算法,与人们常用方法相似,先猜试一条路,然后改变路径与其比较,重复上述方法直到没有更近路线。人们会先选一条看上去不错的路线,然后不断试探不同捷径,直到你找不到更好路径了。但是你如何证明你找到路线是最短的呢?也许存在一条更短路径。与人尝试不同的是,优化程序不仅算出最短路径,同时证明没有更短的路线存在。最短距离问题算法不仅保证没有更短路线,同时计算速度非常之快。

  并非所有问题都能找到最短距离这么简单的算法。以旅行商问题为例,商人寻找最短的路线,去拜访一个城市里所有的顾客。似乎我们可以用上述两点之间最短距离类似方法去解决这个旅行商问题,实际上最佳解决方案是非常之难。至今没有一个简单算法可以解决旅行商路径难题。

  如果你难以理解这两个问题的巨大差别,这也是很正常的。半个世纪以来,许多最聪明的数学家试图证明旅行销售员问题与最短二点之间距离问题一样简单。但是迄今为止,尝试者全部铩羽而归。

  在更普遍层面,旅行商问题在理论计算机科学领域被视为最重要难题。如果该难题能借助计算机快速解决,类似成千上万问题也将迎刃而解,每年可以为世界经济节省几千亿美元。解决问题算法是双刃剑,它可能危及现行网上交易,从而对世界金融体系造成巨大威胁。由于问题解决意义如此重大,解题奖金高达一百万美元,仅有6个教学难题有如此高的奖金。但是数学家会告诉你,使他们着迷的不仅仅是赢得巨额奖金,更重要的是为了挑战这个同行髙手认为“难于上青天”的难题。

侬好上海由新民网出品
微信号:helloshanghai2013

吃喝玩乐、上海故事、同城活动
每天热爱上海多一点,
加入小侬家族就对啦!

新民晚报官方微信
微信号:xmwb1929

有用、有益、有趣

街谈巷议微信
微信号:xinminwangshi

街头访谈,麻辣点评

今日热点
更多新闻
发布评论
您还能输入300

版权声明:

• 在本网站刊登的所有内容,包括但不限于文字、图片、音频视频、美术设计、程序及多媒体等信息,未经著作权人合法书面授权,不得进行一切形式的下载、转载或建立镜像。获得著作权人合法书面授权的,必须在授权范围内使用,使用时保留本网注明的"稿件来源",并自负法律责任。凡注明为其他媒体来源,均为转载自其他媒体,转载并不代表本网赞同其观点,也不代表本网对其真实性负责。如果擅自篡改为"稿件来源:新民网",本网将依法追究责任。

• 您若对稿件处理有任何疑问或质疑,请即与新民网联系,本网将迅速给您回应并做处理。

电话:021-22899999  传真:021-62677454

邮箱:稿件处理  处理时间:9:00—16:00

新闻热词榜
  • 数据加载中……
【街谈巷议】旅行社那些坑爹事 市民:“强制消费”最可恶 2016-08-04 09:10
聚合
生活在上海 生活在上海

这里,有土生土长的本地上海人,有来自国内各地的新上海人,有不远万... [详情]

登巴巴那么可爱,怎么忍心让他受伤害 登巴巴那么可爱,怎么忍心让他受伤害

在这里不想发任何和他昨天受伤有关的图。毕竟乐观而又虔诚的登巴巴,... [详情]

新民报系成员|客户端|官方微博|微信矩阵|新民网|广告刊例|战略合作伙伴

新民晚报|新民网|新民周刊|新民晚报社区版|新民地铁

新民晚报数字报|新民晚报ipad版|新民网客户端

关于新民网|联系方式|工作机会|知识产权声明|友情链接

北大方正|上海音乐厅|中卫普信|东方讲坛|今日头条|钱报网|少儿英语教育论坛|中国网信网|中国禁毒网|陆家嘴金融网

增值电信业务经营许可证(ICP):沪B2-20110022号|互联网新闻信息服务许可证:3112009001|信息网络传播视听节目许可证:0909381

广电节目制作经营许可证:(沪)字第536号|违法与不良信息举报电话15900430043|网络敲诈和有偿删帖|沪公网安备 31010602000044号

新民晚报官方网站 xinmin.cn ©2013 All rights reserved