基於插入法機制解決旅行者問題與分析
解法 （演算法） 選擇路徑方式
內插法
--------------------------------
1. 1階 （雙向連結）
2. 3階 深度解法
3. N階 深度解法
4. N/2階 動態 深度解法 ＃目前正在測試
5. N/3階 動態 深度解法 ＃目前正在測試
6. N/?階 ？？？ 在怎麼樣的階層中，你的插入法會達到最高效益
這個禮拜想辦法整理出數據！！
今天下午跑兩個小時的N階層數據結果看來，N階層比貪婪法還來的差
付出了部份的時間複雜度不打緊，在求解的過程也沒有對最佳路徑上的選擇
提高效益，是一個不可使用的方法！！！
所以我提出了一個降低 N階的想法，看是否在一個具備動態的深度階層插入法之下
能不能夠提高效率！！
＃插入技巧 種類
1. 取座標 中心點 出發，由內而外 ＃ 尚未寫出來：以均勻分佈為出發粒子 ，
2. 取座標 從最外圍，由外而外 ＃ 作為插入順序上的排列機制
---------------------------------
3. 以Y軸 為 線段 從左掃到右邊 、從右掃到左邊
4. 以X軸 為 線段 從下掃到上邊 、從上掃到下邊
5. 以隨機亂數產生排列數列，做插入序列 （Random Permutation）
問題1.
要怎麼統計用Randperm函數所生成出來的數字排列，matlab 有辦法追蹤 生成出來的數列
做一個統計嗎？？
或是自己想辦法把生成出來的數列，想辦法自己再寫出一支分佈狀況的分析副程式?
#有點麻煩，要準備很多統計、機率的資料來看
問題2.
要統計自己生成出來的數列，是以一個怎麼樣的分佈！！ 要定義清楚要搞清楚
再來的是對自己數列的分佈方式，對你的演算法有沒有驗證上的實質效益
簡單來說，就是你用隨機產生的方式，有什麼依據或是貢獻度
不能夠用碰運氣的方式去跑解得到<近似解>或<最佳解>
你要瞭解隨機分佈所得到的結果
在生成的過程，是個怎麼樣的狀況！！！
這個要非常注意！！！ 要交待清楚
1.Best_att48
----------------------------------------------------------------------------------------------------------------
N/? 階 準確率 迴圈次數 時間(秒) Std Avg 高於90％ 備註
----------------------------------------------------------------------------------------------------------------
n/3 95.0925(1484) 3000 2246 sec 6.4148 75.5979 39
n/4 97.3472(2071) 3000 1658 sec 6.7535 77.0788 80
n/5 97.7562(1976) 3000 1699 sec 6.6286 78.1441 96
n/6 97.6992(398) 3000 1155 sec 6.5156 78.9396 114
n/8 97.5967(2961) 3000 1055 sec 6.4104 79.4541 143
n/16 95.3415(617) 3000 592 sec 5.6308 78.1960 62
題庫
----------------------------------------------------------------------------------------------------------------
3階 準確率 迴圈次數 時間(秒) 備註
----------------------------------------------------------------------------------------------------------------
1.Best_att48 97.1242 3000次 1075
2.Best_kroA100 94.1216 3000次 4429
3.Best_kroC100 91.8663(2169) 3000次 2317
95.3221(7255) [91.0863 第4794次] [95.4803第4083次] [91.8663第2159]
4.Best_kroD100 92.4070 (第375次) 3000次 1480
5.Best_lin105 92.4395 3000次
92.4395 第161次擊中 花了 20612次迴圈下去跑
6.pr76 95.2296 (第684次) 3000次 740
----------------------------------------------------------------------------------------------------------------
掃蕩法 準確率 備註 att48
----------------------------------------------------------------------------------------------------------------
Y 軸掃蕩 準確率 X 軸掃蕩 準確率
左到右 77.85 下到上 76.5643
右到左 75.4521 上到下 79.4889
----------------------------------------------------------------------------------------------------------------
＊ 內外插 比較法 準確率 備註 att48
----------------------------------------------------------------------------------------------------------------
雙向連結
內外插 84.9338
外插內 74.4958
三階層 雙向連結
內外插 83.3304
外插內 61.5242
----------------------------------------------------------------------------------------------------------------
貪婪法 準確率 備註 att48
----------------------------------------------------------------------------------------------------------------
1.Best_att48 88.445
2.Best_kroA100 86.1633
3.Best_kroC100 88.0230
4.Best_kroD100 85.6469
5.Best_lin105 XXXXX
6.pr76 82.6085
............
In this paper ,We analysis a heuristic algorithm and provide method The Salesman Problem
.........................
In this paper,Author using Insertion heuristic to studies Travelling salesman problem,And these analysis several results to proved the Insertion Method is manifestation
...................
In follows has Introduction The Insertion Method sequential structures
.............................
............................
Reference: Heuristics - http://mat.gsia.cmu.edu/orclass/integer/node17.html
蒙地卡羅方法 - http://zh.wikipedia.org/wiki/%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%96%B9%E6%B3%95
蒙地卡羅方法（Monte Carlo method）也稱統計模擬方法
沒有留言:
張貼留言