用A*算法解决TSP问题

用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 < min_fcost:
       

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           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.xml
     文件         262  2017-10-18 10:25  A-TSP\.idea\modules.xml
     文件        9610  2017-10-18 17:11  A-TSP\.idea\workspace.xml
     文件         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