資源簡介
用A*算法解決TSP問題,用python語言實現。用了一個400節點的數據進行測試

代碼片段和文件信息
from?math??import?sqrt
class?city(object):
????def?__init__(self):
????????self.deep?=0
????????self.g_cost=0?#g_cost為從初始狀態到此節點的實際代價
????????self.f_cost=0?#f_cost?=?g_cost?+?h_cost
????????self.father?=?None
????????self.number=1?#初始化?默認第一次訪問的城市是1
def?get_data(filepath):
????result?=?[]
????with?open(filepath?‘r‘)?as?tspfile:
????????for?line?in?tspfile:
????????????result.append(line)
????data?=?result[6:-1]??#?只取含有數劇的部分
????return?data
def?get_dis_matrix(data):
????city_x?=?[]
????city_y?=?[]
????for?words?in?data:
????????nxy=words.split()
????????city_x.append(float(x))
????????city_y.append(float(y))
????def?cal_distance(index1index2):
????????x1=pow(city_x[index1]-city_x[index2]2)
????????y1=pow(city_y[index1]-city_y[index2]2)
????????return(sqrt(x1+y1))
????#?將城市兩兩之間的距離存在一個二維數組里
????length?=?len(city_x)
????dis?=?[[0?for?x?in?range(length)]?for?y?in?range(length)]
????for?i?in?range(length):
????????for?j?in?range(length):
????????????dis[i][j]=cal_distance(ij)
????return?dis
#定義一個獲取h_cost的函數?即是啟發式策略所估算的代價
def?get_hcost(ideep):
????mins?=?dis[i][0]
????for?j?in?range(city_number):
????????if?dis[i][j]?==0:
????????????continue
????????if?path_city_label[j]?==0:#如果j點已經訪問過了
????????????continue
????????elif?mins>dis[i][j]:
????????????mins?=?dis[i][j]
????return?mins*(city_number-deep)
#A*算法尋找最優路徑
def?get_bestway(thiscity):
????while(1):
????????num=0
????????for?i?in?range(city_number+1):
????????????if(path_city_label[i]==0):
????????????????num+=1?????#檢測已經訪問過城市的個數
????????if?num>city_number:#城市全部訪問完
????????????break
????????if?num==city_number:#這是搜索到最后一個節點的狀況
????????????nextcity?=?city()
????????????nextcity.deep?=?thiscity.deep?+?1
????????????nextcity.number?=?1
????????????nextcity.g_cost?=?thiscity.g_cost?+?dis[thiscity.number?-?1][0]#就是最后一個節點到1號城市的距離
????????????nextcity.f_cost?=?thiscity.g_cost
????????????nextcity.father?=?thiscity
????????????closed.append(nextcity)
????????????path_city_label[city_number]=0
????????if?num? ????????????open_list?=?[]????#?初始化open表,因為這是A星算法,不需要保留拓展過但未被選取的其他的分支
????????????for?i?in?range(city_number):
????????????????if?i?==?thiscity.number?-?1:
????????????????????continue
????????????????if?path_city_label[i]?==?0:
????????????????????continue
????????????????nextcity?=?city()
????????????????nextcity.deep?=?thiscity.deep?+?1
????????????????nextcity.number?=?i?+?1
????????????????nextcity.g_cost?=?thiscity.g_cost?+?dis[thiscity.number?-?1][i]
????????????????h_cost?=?get_hcost(nextcity.number?-?1?nextcity.deep?+?1)
????????????????nextcity.f_cost?=?h_cost?+?nextcity.g_cost
????????????????nextcity.father?=?thiscity
????????????????open_list.append(nextcity)
????????????openlen?=?len(open_list)
????????????tmpcity?=?open_list[0]
????????????min_fcost?=?open_list[0].f_cost
????????????for?item?in?open_list:
????????????????if?item.f_cost????????
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2017-10-22?15:09??A-TSP\
?????目錄???????????0??2017-10-22?15:09??A-TSP\.idea\
?????文件?????????398??2017-10-18?10:25??A-TSP\.idea\A-TSP.iml
?????文件?????????219??2017-10-18?10:25??A-TSP\.idea\misc.xm
?????文件?????????262??2017-10-18?10:25??A-TSP\.idea\modules.xm
?????文件????????9610??2017-10-18?17:11??A-TSP\.idea\workspace.xm
?????文件?????????613??2017-10-08?22:55??A-TSP\eil51.tsp
?????文件????????4253??2017-10-07?16:35??A-TSP\lin318.tsp
?????文件???????11221??2017-10-07?16:35??A-TSP\rd400.tsp
?????文件????????2338??2017-10-18?17:01??A-TSP\result.tsp
?????文件????????4518??2017-10-18?16:50??A-TSP\tsp.py
- 上一篇:大作業2 –路由協議Python
- 下一篇:43個Python代碼打包
評論
共有 條評論