#?-*-?coding:?utf-8?-*-
import?random
import?copy
import?time
import?sys
import?math
import?tkinter
import?threading
from?functools?import?reduce

#?參數
（ALPHA?BETA?RHO?Q）?=?（1.0?2.0?0.5?100.0）

#?站點坐標
distance_x?=?[30135125200220300350400480530]
distance_y?=?[500550470450510480290200220300]
#?站點數，蟻群
（station_num?ant_num）?=?（len（distance_x）?50）
#?站點距離和信息素
distance_graph?=?[[0.0?for?col?in?range（station_num）]?for?raw?in?range（station_num）]
pheromone_graph?=?[[1.0?for?col?in?range（station_num）]?for?raw?in?range（station_num）]


#?-----------?螞蟻?-----------
class?Ant（object）:
????#?初始化
????def?__init__（self?ID）:

????????self.ID?=?ID??#?ID
????????self.__clean_data（）??#?隨機初始化出生點

????#?初始數據
????def?__clean_data（self）:

????????self.path?=?[]??#?當前螞蟻的路徑
????????self.total_distance?=?0.0??#?當前路徑的總距離
????????self.move_count?=?0??#?移動次數
????????self.current_station?=?0??#?當前停留的站點
????????self.open_table_station?=?[True?for?i?in?range（station_num）]??#?探索站點的狀態

????????station_index?=?0?#?出生點
????????self.current_station?=?station_index
????????self.path.append（station_index）
????????self.open_table_station[station_index]?=?False

????#?選擇下一個站點
????def?__choice_next_station（self）:

????????next_station?=?-1
????????select_stations_prob?=?[0.0?for?i?in?range（station_num）]
????????total_prob?=?0.0

????????#?獲取去下一個站點的概率
????????for?i?in?range（station_num）:
????????????if?self.open_table_station[i]:
????????????????try:
????????????????????#?計算概率：與信息素濃度成正比，與距離成反比
????????????????????select_stations_prob[i]?=?pow（pheromone_graph[self.current_station][i]?ALPHA）?*?pow（
????????????????????????（1.0?/?distance_graph[self.current_station][i]）?BETA）
????????????????????total_prob?+=?select_stations_prob[i]
????????????????except?ZeroDivisionerror?as?e:
????????????????????print（‘Ant?ID:?{ID}?current?station:?{current}?target?station:?{target}‘.format（ID=self.ID
????????????????????????????????????????????????????????????????????????????????????????????????current=self.current_station
????????????????????????????????????????????????????????????????????????????????????????????????target=i））
????????????????????sys.exit（1）

????????#?輪盤選擇站點
????????if?total_prob?>?0.0:
????????????#?產生一個隨機概率
????????????temp_prob?=?random.uniform（0.0?total_prob）
????????????for?i?in?range（station_num）:
????????????????if?self.open_table_station[i]:
????????????????????#?輪次相減
????????????????????temp_prob?-=?select_stations_prob[i]
????????????????????if?temp_prob?????????????????????????next_station?=?i
????????????????????????break

????????#?未從概率產生，順序選擇一個未訪問站點?????????????
????????if?next_station?==?-1:
????????????for?i?in?range（station_num）:
????????????????if?self.open_table_station[i]:
????????????????????next_station?=?i
????????????????????break

????????#?返回下一個站點序號
????????return?next_station

????#?計算路徑總距離
????def?__cal_total_distance（self）:

????