返回顶部
返回首页
返回首页
欢迎访问  中国机械网   | 今天是   
中国机械网全新改版进行中!
单个单元提示解决计算机科学中最大的问题,中国机械网,okmao.com
home 您现在的位置: 首页 >设备与仪器>技术中心 > 详细信息
单个单元提示解决计算机科学中最大的问题
2019年03月13日    阅读量:108    新闻来源:中国机械网 okmao.com  |  投稿

计算机科学中最古老的问题之一就是单个细胞解决了。


来自东京庆应义塾大学的一组研究人员开始使用变形虫来解决旅行推销员问题,这是计算机科学中的一个着名问题。问题是这样的:想象一下,你是一个旅行推销员,从一个城市飞到另一个城市,出售你的商品中国机械网okmao.com。你最关心的是最大化你的效率以赚取尽可能多的钱,所以你想要找到最短的路径,让你击中路线上的每个城市。


没有简单的数学公式可以为我们的销售人员找到最有效的路线。相反,解决问题的唯一方法是计算每条路线的长度,看看哪条路线最短。


多头泡菌(PHYSARUM POLYCEPHALUM)是一种非常简单的有机体,可以做两件事:它向食物移动并远离光线。


更糟糕的是,执行此计算会使得路线中添加的城市越来越多。有四个城市,只有三条不同的路线需要考虑。但是有六个城市,需要计算360条不同的路线。如果你有一个有十个或更多城市的路线,那么可能的路线数量就是数百万。


这使得旅行商问题成为计算机科学家称之为“NP难”的广泛问题之一。这些问题很快就会出现指数级难度,其中还包括与黑客加密系统和加密货币挖掘相关的问题。由于非常明显的原因,很多人都有兴趣找到尽快解决这些问题的方法。


庆应义塾大学的解决方案与其他研究人员生产的典型算法解决方案不同,因为科学家们使用变形虫。具体而言,Physarum polycephalum 粘液霉菌。多头泡菌(Physarum polycephalum)是一种非常简单的有机体,可以做两件事:它向食物移动并远离光线。数百万年的进化使得Physarum在这两方面都异常高效。


庆应义塾大学的研究人员利用这种效率建立了解决旅行商问题的设备。他们将变形虫放在一个充满通道的特殊室中,在每个通道的末端,研究人员放置了一些食物。本能地,变形虫会将卷须延伸到通道中以尝试获取食物。但是,当它这样做时,它会触发灯光在其他通道中消失。



在这种特殊情况下,每个渠道代表我们假设的推销员路线上的城市,以及应该访问城市的订单。当变形虫延伸到代表城市的通道时,它会影响光线在代表路线上下一个城市的通道中消失的可能性。距离这个城市越远,光线就越频繁地消失。


这似乎是计算旅行商问题解决方案的迂回方式,但优点是变形虫不必像大多数计算机算法那样计算每个单独的路径。相反,变形虫只是被动地对条件做出反应,并自己找出最好的安排。这意味着对于变形虫来说,增加更多的城市不会增加解决问题所需的时间。


因此,变形虫可以比我们的任何计算机算法更快地解决NP难问题。这是怎么发生的?Keio的科学家们并不确定。


首席研究作者Masashi Aono 在新闻发布会上表示,“变形虫维持近似解决方案质量的机制,即短路线长度仍然是一个谜。”


但是,如果研究人员能够弄清楚变形虫是如何起作用的,他们可以使用这个技巧,而不仅仅是帮助旅行推销员。它可以加快我们解决各种困难计算问题的能力,并改变我们处理安全性的方式。


这个小变形虫 - 以及它解决困难问题的方式 - 可能会永远改变计算的面貌。


标签:行业资讯今日头条技术中心设备与仪器办公设备
免责声明: 本文仅代表作者本人观点,与中国机械网无关。本网对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。本网转载自其它媒体的信息,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如因作品内容、版权和其它问题需要同本网联系的,请在一周内进行,以便我们及时处理。客服邮箱:service@cnso360.com | 客服QQ:23341571
相关文章HOT
今日头条Show更多
    热点排行Hot
      中国机械网手机版MOBILE
      扫描二维码,获取手机版最新资讯 中国机械网 您还可以直接微信扫描打开
      全站地图

      深圳网络警察报警平台 深圳网络警
      察报警平台

      公共信息安全网络监察 公共信息安
      全网络监察

      经营性网站备案信息 经营性网站
      备案信息

      中国互联网举报中心 中国互联网
      举报中心

      中国文明网传播文明 中国文明网
      传播文明

      深圳市市场监督管理局企业主体身份公示 工商网监
      电子标识