数学建模中的常用模型和算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import numpy as np

# 默认使用9级评分
RI_dict = {1: 0, 2: 0, 3: 0.58, 4: 0.90, 5: 1.12, 6: 1.24, 7: 1.32, 8: 1.41, 9: 1.45}

# 矩阵, 注意使用小数, 否则计算结果为整数
A_arr = [[1, 2, 1.0/3, 3],
        [1.0/2, 1, 1.0/3, 2],
        [3, 3, 1, 4],
        [1.0/3, 1.0/2, 1.0/4, 1]]

def main():
    # 矩阵
    A = np.array(A_arr)

    a_sum0 = A.sum(axis=0)
    B = A / a_sum0  
    print('新矩阵:')
    print(B)
    b_sum = B.sum(axis=1)
    print('新矩阵行和: %s' % b_sum)

    
    W = b_sum.sum()
    w_arr = []
    for w in b_sum:
        w_arr.append(w/W)

    print('W: %s' % w_arr)

    AW = []
    for a in A :
        aa = a * w_arr
        AW.append(aa.sum())

    print('AW: %s' % AW)

    result = np.array(AW) / np.array(w_arr)
    print('AW/W: %s' % result)

    row = result.shape[0]
    Max = result.sum()/row
    print('λMax: %s' % Max)

    CI = (Max - row) / (row - 1)
    print('CI: %s' % CI)
    
    CR = CI / RI_dict[row]
    print('CR: %s' % CR)
    
 
if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import numpy as np
from scipy.optimize import linprog

# 目标函数系数，这里取负值因为 linprog 默认进行最小化优化
c = [-20, -30, -45]  

# 不等式约束的系数矩阵 A
A_ub = [
    [4, 8, 15],
    [1, 1, 1]
]  

# 不等式约束的右侧值向量 b
b_ub = [100, 20]  

# 定义域，变量取值范围（下限为 0，上限无限制）
bounds = [[0, None], [0, None], [0, None]]  

# 求解线性规划问题
# 由于 linprog 默认求解最小化问题，通过对目标函数系数取负值转换为最大化问题
result = linprog(c, A_ub, b_ub, bounds=bounds)  

print(result)

# 输出 A、B、C 三图分别通关的次数（解向量）
print('A、B、C 三图分别通关的次数为：')
print(result.x)  

# 目标函数的最大值是最小化问题结果的相反数
y = -result.fun  
print('最终获得的经验为：')
print(y)

1
res = minimize(fun, x0, args, method, jac, hess, hessp, bounds, constraints, tol, callback, options)  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import numpy as np
from scipy.optimize import minimize

# 目标函数，接受长度为 2 的一维数组 x（代表变量 x1 和 x2），计算并返回目标函数值
def fun1(x):
    return x[0] ** 2 + x[1] ** 2 - x[0] * x[1] - 2 * x[0] - 5 * x[1]

# 第一个非线性约束条件函数，接受变量 x，返回对应约束条件的值
def nonlcon1(x):
    return -(x[0] - 1) ** 2 + x[1]

# 第二个非线性约束条件函数，接受变量 x，返回对应约束条件的值
def nonlcon2(x):
    return 2 * x[0] - 3 * x[1] + 6

# 初始值设定，设置为一个二维的 numpy 数组，初始值为 [0, 0]
x0 = np.array([0, 0])

# 使用默认算法（类似内点法，scipy 会根据情况选择合适的）求解
res = minimize(
    fun1, 
    x0, 
    constraints=(
        {'type': 'ineq', 'fun': nonlcon1},
        {'type': 'ineq', 'fun': nonlcon2}
    ),
    bounds=None, 
    tol=None, 
    options=None, 
    args=()
)

# 输出求解结果
print("默认算法（类似内点法等情况）求解结果：")
print("最优解：", res.x)
print("最优值：", res.fun)

import numpy as np

# 假设目标函数和约束函数已定义（需与之前的 fun1、nonlcon1、nonlcon2 对应）
def fun1(x):
    return x[0]**2 + x[1]**2 - x[0]*x[1] - 2*x[0] - 5*x[1]

def nonlcon1(x):
    return -(x[0]-1)**2 + x[1]

def nonlcon2(x):
    return 2*x[0] - 3*x[1] + 6

# 使用蒙特卡罗方法找初始值（推荐）
n = 10000000  # 随机采样数量，越大越可能找到优值但耗时更长
# 在 [-100, 100] 区间生成均匀分布的随机数
x1 = np.random.uniform(-100, 100, size=n)  
x2 = np.random.uniform(-100, 100, size=n)  

fmin = 100000000  # 初始化最小目标函数值
x0 = None         # 初始化蒙特卡罗找到的初始值

for i in range(n):
    x = np.array([x1[i], x2[i]])  # 构造变量数组
    # 检查约束条件：两个不等式约束均需满足（返回值 ≥ 0 表示满足）
    if nonlcon1(x) >= 0 and nonlcon2(x) >= 0:  
        result = fun1(x)  # 计算满足约束的目标函数值
        if result < fmin:  # 找到更优的目标函数值时更新
            fmin = result
            x0 = x  # 记录对应自变量

print("蒙特卡罗选取的初始值为：", x0)

# 使用找到的初始值再次进行优化求解
res_final = minimize(
    fun1, 
    x0, 
    method='SLSQP',
    constraints=(
        {'type': 'ineq', 'fun': nonlcon1},
        {'type': 'ineq', 'fun': nonlcon2}
    ),
    bounds=None, 
    tol=None, 
    options=None, 
    args=()
)

print("基于蒙特卡罗初始值的最终求解结果：")
print("最优解：", res_final.x)
print("最优值：", res_final.fun)

1
LpProblem(name, sense)  

1
2
3
4
5
6
7
from pulp import LpProblem, LpMaximize, LpMinimize  

# 定义一个最大化问题  
problem = LpProblem(name="Problem_Name", sense=LpMaximize)  

# 或定义最小化问题  
problem = LpProblem(name="Problem_Name", sense=LpMinimize)  

1
LpVariable(name, lowBound, upBound, cat)  

1
2
3
4
5
6
7
8
9
10
from pulp import LpVariable  

# 连续变量 x，下界 0，无上界  
x = LpVariable(name="x", lowBound=0, upBound=None, cat="Continuous")  

# 整数变量 y，下界 0，上界 10  
y = LpVariable(name="y", lowBound=0, upBound=10, cat="Integer")  

# 0-1 变量 z，默认下界 -infinity、上界 +infinity（实际受限于 0-1）  
z = LpVariable(name="z", cat="Binary")  

1
2
3
4
5
6
7
8
# 添加目标函数：3x + 2y
problem += 3 * x + 2 * y, "Objective_Function"
# 添加约束条件 1：x + y <= 10
problem += x + y <= 10, "Constraint_1"
# 添加约束条件 2：x - y >= 2
problem += x - y >= 2, "Constraint_2"
# 添加等式约束 3：x + z == 1
problem += x + z == 1, "Constraint_3"

1
problem.solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from pulp import LpMaximize, LpProblem, LpVariable, lpSum, value

# 创建一个最大化问题，问题名称为 "Maximize_Experience"
problem = LpProblem(name="Maximize_Experience", sense=LpMaximize)

# 定义决策变量，均为非负整数，分别代表 A、B、C 图通关次数
x1 = LpVariable(name="x1", lowBound=0, cat="Integer")  # A 图通关次数
x2 = LpVariable(name="x2", lowBound=0, cat="Integer")  # B 图通关次数
x3 = LpVariable(name="x3", lowBound=0, cat="Integer")  # C 图通关次数

# 定义目标函数：总经验，表达式为 20*x1 + 30*x2 + 40*x3，名称为 "Total_Experience"
problem += 20 * x1 + 30 * x2 + 40 * x3, "Total_Experience"

# 添加约束条件
# 资源约束：4*x1 + 8*x2 + 10*x3 <= 100，名称为 "Resource_Constraint"
problem += 4 * x1 + 8 * x2 + 10 * x3 <= 100, "Resource_Constraint"
# 时间约束：x1 + x2 + x3 <= 20，名称为 "Time_Constraint"
problem += x1 + x2 + x3 <= 20, "Time_Constraint"

# 求解问题
problem.solve()

# 输出结果
print("A、B、C 三图分别通关的次数为：")
print(int(value(x1)), int(value(x2)), int(value(x3)))

print("最终获得的经验为：")
print(int(value(problem.objective)))

1
2
3
squares = [i**2 for i in range(10)]
print(squares)
# 在上述代码中, range(10)就是可迭代对象, i是变量, i**2是表达式, 代码会依次将range(10)中的每个值赋给i

1
2
even_squares = [i**2 for i in range(10) if i%2 ==0]
print(even_squares)

1
2
import coptpy as cp
from coptpy import COPT

1
2
# Create COPT environment
env = cp.Envr()

1
2
# Create COPT model
model = env.createModel("lp_ex1")

1
2
3
4
# Add variables: x, y, z
x = model.addVar(lb=0.1, ub=0.6, name="x")
y = model.addVar(lb=0.2, ub=1.5, name="y")
z = model.addVar(lb=0.3, ub=2.8, name="z")

1
2
3
# Add constraints
model.addConstr(1.5*x + 1.2*y + 1.8*z <= 2.6)
model.addConstr(0.8*x + 0.6*y + 0.9*z >= 1.2)

1
2
# Set objective function
model.setObjective(1.2*x + 1.8*y + 2.1*z, sense=COPT.MAXIMIZE)

1
2
# Set parameter
model.setParam(COPT.Param.TimeLimit, 10.0)

1
2
# Solve the model
model.solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import random
import numpy as np
import math
num_city=30#城市总数0-29
num_total=100#随机生成的初始解的总数
copy_num=70#保留的解的个数
cross_num=20#交叉解的个数
var_num=10#变异解的个数
location=np.loadtxt('city_location.txt')
#print(location)
#随机生成初始解[[],[],[]...]
def generate_initial():
    initial=[]
    city=list(range(num_city))
    for i in range(num_total):
        random.shuffle(city)
        p=city.copy()
        while (p in initial):
            #print('2333')#随机了一个重复的解
            random.shuffle(city)
            p=city.copy()
        initial.append(p)
    return initial

#对称矩阵，两个城市之间的距离
def distance_p2p_mat():
    dis_mat=[]
    for i in range(30):
        dis_mat_each=[]
        for j in range(30):
            dis=math.sqrt(pow(location[i][0]-location[j][0],2)+pow(location[i][1]-location[j][1],2))
            dis_mat_each.append(dis)
        dis_mat.append(dis_mat_each)
   # print(dis_mat)
    return dis_mat

#目标函数计算,适应度计算，中间计算。适应度为1/总距离*10000
def dis_adp_total(dis_mat,initial):
    dis_adp=[]
#    dis_test=[]   
    for i in range(num_total):
        dis=0
        for j in range(num_city-1):
            dis=dis_mat[initial[i][j]][initial[i][j+1]]+dis
        dis=dis_mat[initial[i][29]][initial[i][0]]+dis#回家
#        dis_test.append(dis)        
        dis_adp_each= 10000.0/dis
        dis_adp.append(dis_adp_each)
#    print(dis_test)
    return dis_adp

def choose_fromlast(dis_adp,answer_source):
    mid_adp=[]
    mid_adp_each=0
    for i in range(num_total):
        mid_adp_each=dis_adp[i]+mid_adp_each
        mid_adp.append(mid_adp_each)
   # print(mid_adp)
    #产生0-mid_adp[num_total-1]之间的随机数
    #选择n-1<随机数<n的那个n的解,保留
    copy_ans=[]
    for p in range(copy_num):
        rand=random.uniform(0,mid_adp[num_total-1])#产生随机数
       # print(rand)
       # print(p)
        for j in range(num_total):
            if (rand<mid_adp[j]):#查找位置
                copy_ans.append(answer_source[j])
                break
            else:
                continue
    return copy_ans

#随机选择保留下来的70中的25个进行交叉
def cross_pronew(copy_ans):
    for i in range(cross_num):
        which=random.randint(0,copy_num-1)#选择对那个解交叉
        cross_list=copy_ans[which].copy()
        while (cross_list in copy_ans):
            p=random.randint(0,num_city-1)
            q=random.randint(0,num_city-1)
            cross_list[p],cross_list[q]=cross_list[q],cross_list[p]#第一次交换位置
            m=random.randint(0,num_city-1)
            n=random.randint(0,num_city-1)
            cross_list[m],cross_list[n]=cross_list[n],cross_list[m]#第二次交换位置            
        copy_ans.append(cross_list)
    cross_ans=copy_ans.copy()
    return cross_ans

#随机选择那95中的5个进行变异
def var_pronew(cross_ans):
    for i in range(var_num):
        which=random.randint(0,copy_num+cross_num-1)#选择对那个解交叉
        var_list=cross_ans[which].copy()
        while (var_list in cross_ans):
            p=random.randint(0,num_city-1)
            q=random.randint(0,num_city-1)
            var_list[p],var_list[q]=var_list[q],var_list[p]#交换位置
        cross_ans.append(var_list)
    var_ans=cross_ans.copy()
    return var_ans
    
answer_source=generate_initial()
dis_mat=distance_p2p_mat()
#print(dis_mat)
dis_adp=dis_adp_total(dis_mat,answer_source)
adp_max_new=max(dis_adp)
if (max(dis_adp)>10000/700):
    print('找到的最近距离是：',max(dis_adp))
else:
    print('哎呀没找到，我再找找~')    
    answer_new=answer_source
    dis_adp_new=dis_adp
    while(adp_max_new<=10000/700):
        copy_answer=choose_fromlast(dis_adp_new,answer_new)
        cross_answer=cross_pronew(copy_answer)
        var_answer=var_pronew(cross_answer)
        answer_new=var_answer.copy()
        dis_adp_new=dis_adp_total(dis_mat,answer_new)
        adp_max_new=max(dis_adp_new)
#        dis_min=10000/adp_max_new
#        print('这次是：',dis_min)
    dis_min=10000/adp_max_new
    print('终于找到你啦：',dis_min)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import random
import numpy as np
import math

num_city=30#城市总数
initial_t=120#初始温度
lowest_t=0.001#最低温度
M=150#当连续多次都不接受新的状态，开始改变温度
iteration=500#设置迭代次数

location=np.loadtxt('city_location.txt')

#==========================================
#对称矩阵，两个城市之间的距离
def distance_p2p_mat():
    dis_mat=[]
    for i in range(30):
        dis_mat_each=[]
        for j in range(30):
            dis=math.sqrt(pow(location[i][0]-location[j][0],2)+pow(location[i][1]-location[j][1],2))
            dis_mat_each.append(dis)
        dis_mat.append(dis_mat_each)
   # print(dis_mat)
    return dis_mat

#计算所有路径对应的距离
def cal_newpath(dis_mat,path):
    dis=0
    for j in range(num_city-1):
        dis=dis_mat[path[j]][path[j+1]]+dis
    dis=dis_mat[path[29]][path[0]]+dis#回家
    return dis

#==========================================
#点对点距离矩阵
dis_mat=distance_p2p_mat()
#初始路径
path=list(range(30))
#初始距离
dis=cal_newpath(dis_mat,path)
#初始温度
t_current=initial_t

while (t_current>lowest_t):#外循环，改变温度
    count_m=0#M的计数
    count_iter=0#迭代次数计数
    while (count_m<M and count_iter<iteration):#内循环，连续多次不接受新的状态或者是迭代多次,跳出内循环        
        i=0
        j=0
        while(i==j):#防止随机了同一城市
            i=random.randint(1,29)
            j=random.randint(1,29)
        path_new=path.copy()
        path_new[i],path_new[j]=path_new[j],path_new[i]#任意交换两个城市的位置,产生新解
        #计算新解的距离
        dis_new=cal_newpath(dis_mat,path_new)
        #求差
        dis_delta=dis_new-dis
        #取0-1浮点随机数
        rand=random.random()
        #计算指数函数的值
        exp_d=math.exp(-dis_delta/t_current)
        #选择
        if dis_delta<0:
            path=path_new
            dis=dis_new
        elif exp_d>rand:
            path=path_new
            dis=dis_new    
        else:
            count_m=count_m+1
        count_iter=count_iter+1
    t_current=0.99*t_current#改变温度
#外循环结束
dis_min=dis
path_min=path
print('最短距离：',dis_min)
print('最短路径：',path_min)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import random
import numpy as np
import math

location=np.loadtxt('city_location.txt')
num_ant=200 #蚂蚁个数
num_city=30 #城市个数
alpha=1 #信息素影响因子
beta=1  #期望影响因子
info=0.1 #信息素的挥发率
Q=1 #常数

count_iter = 0
iter_max = 500
#dis_new=1000
#==========================================
#对称矩阵，两个城市之间的距离
def distance_p2p_mat():
    dis_mat=[]
    for i in range(num_city):
        dis_mat_each=[]
        for j in range(num_city):
            dis=math.sqrt(pow(location[i][0]-location[j][0],2)+pow(location[i][1]-location[j][1],2))
            dis_mat_each.append(dis)
        dis_mat.append(dis_mat_each)
   # print(dis_mat)
    return dis_mat

#计算所有路径对应的距离
def cal_newpath(dis_mat,path_new):
    dis_list=[]
    for each in path_new:
        dis=0
        for j in range(num_city-1):
            dis=dis_mat[each[j]][each[j+1]]+dis
        dis=dis_mat[each[num_city-1]][each[0]]+dis#回家
        dis_list.append(dis)
    return dis_list

#==========================================
#点对点距离矩阵
dis_list=distance_p2p_mat()
dis_mat=np.array(dis_list)#转为矩阵
#期望矩阵
e_mat_init=1.0/(dis_mat+np.diag([10000]*num_city))#加对角阵是因为除数不能是0
diag=np.diag([1.0/10000]*num_city)
e_mat=e_mat_init-diag#还是把对角元素变成0
#初始化每条边的信息素浓度，全1矩阵
pheromone_mat=np.ones((num_city,num_city))
#初始化每只蚂蚁路径，都从0城市出发
path_mat=np.zeros((num_ant,num_city)).astype(int)


#while dis_new>400:
while count_iter < iter_max:
    for ant in range(num_ant):
        visit=0#都从0城市出发
        unvisit_list=list(range(1,30))#未访问的城市
        for j in range(1,num_city):
            #轮盘法选择下一个城市
            trans_list=[]
            tran_sum=0
            trans=0
            for k in range(len(unvisit_list)):
                trans +=np.power(pheromone_mat[visit][unvisit_list[k]],alpha)*np.power(e_mat[visit][unvisit_list[k]],beta)
                trans_list.append(trans)
                tran_sum =trans
            
            rand=random.uniform(0,tran_sum)#产生随机数

            for t in range(len(trans_list)):
                if(rand <= trans_list[t]):
                    visit_next=unvisit_list[t]


                    break
                else:
                    continue
            path_mat[ant,j]=visit_next#填路径矩阵

            unvisit_list.remove(visit_next)#更新
            visit=visit_next#更新

    #所有蚂蚁的路径表填满之后，算每只蚂蚁的总距离
    dis_allant_list=cal_newpath(dis_mat,path_mat)

    #每次迭代更新最短距离和最短路径        
    if count_iter == 0:
        dis_new=min(dis_allant_list)
        path_new=path_mat[dis_allant_list.index(dis_new)].copy()      
    else:
        if min(dis_allant_list) < dis_new:
            dis_new=min(dis_allant_list)
            path_new=path_mat[dis_allant_list.index(dis_new)].copy() 

    # 更新信息素矩阵
    pheromone_change=np.zeros((num_city,num_city))
    for i in range(num_ant):
        for j in range(num_city-1):
            pheromone_change[path_mat[i,j]][path_mat[i,j+1]] += Q/dis_mat[path_mat[i,j]][path_mat[i,j+1]]
        pheromone_change[path_mat[i,num_city-1]][path_mat[i,0]] += Q/dis_mat[path_mat[i,num_city-1]][path_mat[i,0]]
    pheromone_mat=(1-info)*pheromone_mat+pheromone_change
    count_iter += 1 #迭代计数+1，进入下一次
        
print('最短距离：',dis_new)
print('最短路径：',path_new)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import random
import numpy as np
import math

num_city=30#城市总数
table_len=20#禁忌表长度
location=np.loadtxt('city_location.txt')
taboo_table=[]


#==========================================
#对称矩阵，两个城市之间的距离
def distance_p2p_mat():
    dis_mat=[]
    for i in range(30):
        dis_mat_each=[]
        for j in range(30):
            dis=math.sqrt(pow(location[i][0]-location[j][0],2)+pow(location[i][1]-location[j][1],2))
            dis_mat_each.append(dis)
        dis_mat.append(dis_mat_each)
   # print(dis_mat)
    return dis_mat

#计算所有路径对应的距离
def cal_newpath(dis_mat,path_new):
    dis_list=[]
    for each in path_new:
        dis=0
        for j in range(num_city-1):
            dis=dis_mat[each[j]][each[j+1]]+dis
        dis=dis_mat[each[29]][each[0]]+dis#回家
        dis_list.append(dis)
    return dis_list

#寻找上一个最优路径对应的所有领域解
def find_newpath(path_best):
    path_new=[]
    for i in range(1,num_city-1):
        for j in range(i+1,num_city):
            path=path_best.copy()
            path[i],path[j]=path[j],path[i]
            path_new.append(path)
    return path_new


#==========================================
#点对点距离矩阵
dis_mat=distance_p2p_mat()

#设置初始解
path_initial=[]
initial=list(range(30))
path_initial.append(initial)
#print(path_initial)

#加入禁忌表
taboo_table.append(initial)

#求初始解的路径长度
dis_list=cal_newpath(dis_mat,path_initial)
dis_best=min(dis_list)#最短距离
path_best=path_initial[dis_list.index(dis_best)]#对应的最短路径方案
#print(path_best)

#初始期望
expect_dis=dis_best
expect_best=path_best
for iter in range(5000):#迭代
    #寻找全领域新解
    path_new=find_newpath(path_best)
    #print(path_new)

    #求出所有新解的路径长度
    dis_new=cal_newpath(dis_mat,path_new)
#    print(dis_new)

    #选择路径
    dis_best=min(dis_new)#最短距离
    path_best=path_new[dis_new.index(dis_best)]#对应的最短路径方案
    if dis_best < expect_dis:#最短的<期望
        expect_dis=dis_best
        expect_best=path_best#更新两个期望
        if path_best in taboo_table:
            taboo_table.remove(path_best)
            taboo_table.append(path_best)
        else:
            taboo_table.append(path_best)
    else:#最短的还是不能改善期望
        if path_best in taboo_table:#在禁忌表里
            dis_new.remove(dis_best)
            path_new.remove(path_best)
            dis_best=min(dis_new)#求不在禁忌表中的最短距离
            path_best=path_new[dis_new.index(dis_best)]#对应的最短路径方案
            taboo_table.append(path_best)
        else:#不在禁忌表
            taboo_table.append(path_best)
    if len(taboo_table)>=table_len:
        del taboo_table[0]
        
print('最短距离',expect_dis)
print('最短路径：',expect_best)