注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

易拉罐的博客

心静自然凉

 
 
 

日志

 
 

转 Traving Saleman Problem by Neural approaches  

2011-10-20 21:50:56|  分类: 神经网络 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://wayne.cs.nthu.edu.tw/~roland/nn/report_fc.html

How simple is TSP? Very simple

推銷員問題就是,給定一個有 n個城市的集合,一個可憐的推銷員想要確實地拜訪每個城市然後再回到開始的地方。推銷員問題可以追溯到十七世紀漢米爾頓循環(Hamiltonain Cycle) 的問題。在電腦的發展歷程中,就因為推銷員問題的簡單性和 NP-problem 的代表性,推銷員問題總是做為新機器的鍊金石(就像有的喜歡以計算圓周率到數百萬位小數一樣)。

如果需要更多有關 TSP最近的發展歷程與說明,可以看看我們以前的成果

How difficult is TSP?Very difficult

諷刺的是,越不起眼的東西通常是越致命的。什麼是地球上最致命的玩意呢?病毒。圍棋-規則最少但卻最難學得精。推銷員問題有最簡單的規則-簡單得連一個小漢都懂-可是它卻需要天文數字般的計算能力才能獲得最佳的結果,也許比「天文數字」還糟。以一個有42個城市的推銷員問題為例,如果我們很不幸地需要列舉所有的路徑才能確定何者最短,那麼總共會有 (42-1)!/2 = 1.67 * 1049  的拜訪方式。如果你不瞭解這個數字有多大,給你一個概念:全宇宙總共才有 1048 個粒子。
 

有了電腦的幫助,我們可以奇蹟似地解決遠比上面來得大的推銷員問題(世界記錄:米飯大學(Rice)的包柏?比克司拜爾特( Bob Bixbyet)等人用了50台接在一起的工作站解決了3038個城市的推銷員問題)。根據欣欣那提大學的馬克?諾司章(Mark H. Noschang)的報告,解決推銷員問題的方法可以略分為以下兩類:

Heuristic
  • Limited Memory Heuristic Search
  • Clustering Heuristics for the Euclidean TSP
  • Genetic Algorithms and Evolutionary Programs 
  • Memetic Algorithms 
  • Tabu Search 
  • Simulated Annealing 
  • Neural Networks 
  • Ant Systems 
  • Space-filling heuristics 
  • Other Search Heuristics 
 
 Approximation
  • Polynomial-time Approximation Schemes (PTAS) 
  • Branch-and-Bound & Branch-and-Cut 

去年,我們在乏晰集理論與應用的課程裡,已經試過用基因演算法( Genetic Algorithm)和模擬退火(Simulated Annealing )來對付惱人的推銷員問題。今年學了類神經網路,我們便想換個花樣用類神經網路來解解看繼續推銷員問題。在這個計畫裡,我們試了兩招-彈性網絡( Elastic Net)與螞蟻王國(Ant System)。除此之外,為了能瞭解人腦在解決推銷員問題時到底靈不靈光,我們還做了一個人腦對電腦的實驗。

Can Neural Net solve TSP?Maybe.

 

  评论这张
 
阅读(465)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017