TSP问题之二边逐次修正法

算法步骤

算法代码

  原算法只支持无向图，以下代码同时支持无向图和有向图。

import numpy as npdef ebzcxz(D, H):# 计算初始H圈权值W = 0for i, j in zip(H, H[1:] + [H[0]]):W += D[i, j]print('初始H圈为:', [i + 1 for i in H], '权值和为;', W)# 计算顶点数N = D.shape[0]# 初始化迭代次数k_iter = 1while 1:# 取出H圈中一对相邻点for i1, j1 in zip(H, H[1:] + [H[0]]):# 取出H圈中另一对相邻点for i2, j2 in zip(H, H[1:] + [H[0]]):if (H.index(i2) - H.index(j1)) >= 1:indi1, indj1, indi2, indj2 = H.index(i1), H.index(j1), H.index(i2), H.index(j2)# 计算原H圈和改H圈不同路径位