一、TSP問題

旅行商問題，又叫貨郎擔問題。它是指如下問題：在完全圖中尋找一條最短的哈密爾頓回路。
哈密爾頓回路問題：給定一個圖，判斷圖中是否存在哈密爾頓回路。
哈密爾頓回路：尋找一條回路，經過圖中所有點且每個點只經過一次。
歐拉回路：尋找一條回路，經過圖中所有的邊且每條邊只經過一次。
判斷一個圖是否存在歐拉回路只需要判斷每個頂點的出度和入度是否相同。
判斷一個圖是否存在一條哈密爾頓回路是一個NP問題。
旅行商問題和哈密爾頓回路問題最大的區別在于：旅行商研究的圖是完全圖，必然存在一條哈密爾頓回路。哈密爾頓回路問題的研究對象是一般的圖。
由此，可以構造一個難上加難的問題：在無向圖中尋找最短的哈密爾頓回路，這必然也是NP問題。

二、Hopfield神經網絡

神經網絡系列分成好多種：

• 前饋神經網絡
• 反饋神經網絡
• 不分前后的神經網絡

Hopfield神經網絡就是不分前后的神經網絡，它的每個神經元之間都是全連接的，構成一個完全圖，N個神經元就有$N \times N$個權值。

Hopfield神經網絡根據激活函數不同可以劃分為：離散型Hopfield神經網絡（Discrete Hopfield Neural Network,DHNN）和連續型Hopfield神經網絡（Continuous Hopfield Neural Network）。離散型Hopfield神經網絡的激活函數是離散的，連續型Hopfield神經網絡的激活函數是連續的。

離散型Hopfield神經網絡主要用于死記硬背，說好聽點就是用于聯想記憶、存儲知識。

連續型Hopfield神經網絡主要用于優化，類似模擬淬火、遺傳算法、蟻群算法。1985年Hopfield將連續型Hopfield神經網絡用于求解大規模旅行商問題并取得不錯成果，開創了神經網絡在最優化領域的應用先河。連續型Hopfield神經網絡其實就是不斷地迭代，使得整個系統的能量逐漸減少。這種方法會陷入局部最優。

三、對Hopfield神經網絡的理解

任何優化問題都需要找到明確的目標。神經網絡方法把分類、聚類、回歸等一切問題都轉化成了最優化問題，神經網絡的唯一作用就是求解最優化問題。因為神經網絡都是定義一個loss，然后更改權值去使得loss最小。

起初，人們不把“損失”叫“損失”，而是稱之為“能量”。能量和損失其實完全是一回事。Hopfield神經網絡最突出的特點就是它跟電路硬件關系密切。Hopfield提出的主要思想是我們可以使用硬件電路來模擬神經網絡的優化過程，這個過程速度極快。因為這個過程使用的電路不是數字電路而是模擬電路。這是Hopfield神經網絡最大的貢獻。而用軟件實現Hopfield神經網絡時，可謂毫無亮點，簡直就是閹割版全連接神經網絡。

四、大規模TSP問題的求解

雖然用Hopfield網絡求解大規模TSP問題十分困難，然而處理N=10或20個城市則比較容易。一個自然的想法是把N>100的TSP問題先用分類算法分成若干子類，每一子類10~20個城市，然后把每一個子類看成類似于城市的一個區，再用神經網絡求每一區的TSP。而各城區之間的連接也將是一個較小的規模的TSP。用這種分類和分級的方法可使神經網絡有效地用于大規模TSP問題的求解。實踐證明這一方法也適用于其他的大規模組合優化問題。

參考資料

也不知道這群人誰抄誰，這么垃圾的模型研究的人這么多

金燦. 基于離散Hopfield神經網絡的數字識別實現[J]. 計算機時代, 2012(3):1-3.
王韜. 基于連續型Hopfield神經網絡的噪聲字符識別[J]. 系統仿真學報, 2003, 15(9):1288-1290.
江鐵, 曹龍漢, 孫奧. 基于離散Hopfield神經網絡的噪聲數字識別[J]. 計算機科學, 2012, 39(b06):526-528.
傅德勝, 張學勇. 基于Hopfield神經網絡噪聲數字的識別[J]. 通信技術, 2010, 43(1):126-128.
車潔, 竇新宇, 彭國志,等. 基于離散Hopfield神經網絡的車牌字符識別[J]. 城市建設理論研究:電子版, 2013(14).
鐘杰, 房智. Hopfield神經網絡在噪聲字符識別中的應用[J]. 內江科技, 2009, 30(1):76-76.
劉艷紅. 基于離散型Hopfield神經網絡的車牌漢字識別方法研究[D]. 東北師范大學, 2013.
王小峰. 基于離散Hopfield神經網絡的數字識別研究[J]. 忻州師范學院學報, 2012, 28(2):21-24.
朱獻文. 基于遺傳算法和Hopfield神經網絡的字符識別方法[J]. 電子設計工程, 2011, 19(18):57-59.

https://zh.wikipedia.org/wiki/Hopfield%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C
https://blog.csdn.net/weixin_39707121/article/details/79042714
https://blog.csdn.net/weixin_39707121/article/details/79041536
https://blog.csdn.net/app_12062011/article/details/54290484

總結

以上是生活随笔為你收集整理的Hopfield神经网络和TSP问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。