Hamilton问题求解-最近邻点法和最近插入法
一、定义
1. 哈密顿通路
设G = < V , E >为一个图（有向图或者无向图）。G中经过的每个顶点一次且仅一次的通路称为哈密顿通路。（通路不一定回到起点，但一定穿过每个顶点一次且仅一次）
2. 哈密顿回路
设G = < V , E >为一个图（有向图或者无向图）。G中经过的每个顶点一次且仅一次的回路称为哈密顿回路。（回路要求穿过每个顶点一次后回到起点）
3. 性质
存在哈密顿通路（回路）的图一定是连通图
哈密顿通路是初级通路，哈密顿回路是初级回路
初级是通路（回路）指除了起点和终点之外，所有的顶点和边都互不相同的通路（回路）
若图G GG中存在哈密顿回路，则它一定存在哈密顿通路
只有哈密顿通路，无哈密顿回路的图不叫哈密顿图
二、判定定理
目前没有判定哈密顿图的简单充要条件
三、求解算法
1. 最近邻点法
算法思想：每次将离当前顶点最近的顶点加入，一般只能找到近似解，不能找到最优解
算法步骤：
- 从网络中找一个点做为起点
- 从剩下的点中找一个离上一个点最近的点加入
- 重复步骤2
- 将最后加入的点与起点连接构成回路
2.最近插入法
最近插入法(Nearest Insertion)于1977年提出，用于解决TSP问题，可以得到相对最近邻点法更优的解。
算法步骤
四、Python源码实现
Hamilton.py
import numpy as np class HamiltonUtil: def __init__(self, input_matrix): self.graph = input_matrix self.point_num = np.shape(self.graph)[0] self.HamSolve = [] self.HamLength = 0 def search_min(self, index, matrix): min_val = np.float('inf') for i in matrix: if self.graph[index][i - 1] < min_val: min_val = self.graph[index][i - 1] return min_val def find_match_vex(self, index, match_val): ret_index = 0 for i in self.graph[index]: if i != match_val: ret_index += 1 else: break return ret_index def find_index(self, vec, value): index = 0 for i in vec: if i != value: index += 1 else: break return index def clear_stack(self): self.HamSolve = [] self.HamLength = 0 def neibor_point(self): self.clear_stack() start = 1 V = np.arange(1, self.point_num + 1, 1) self.HamSolve.append(start) V = np.delete(V, start - 1) BetweenPoint = start while np.shape(V)[0] != 0: VWeight = self.search_min(BetweenPoint - 1, V) Next = self.find_match_vex(BetweenPoint - 1, VWeight) + 1 self.HamSolve.append(Next) V = np.setdiff1d(V, Next) self.HamLength = self.HamLength + VWeight BetweenPoint = Next self.HamSolve.append(start) self.HamLength = self.HamLength + self.graph[Next - 1][start - 1] def nearest_insertion(self): self.clear_stack() start = 1 V = np.arange(1, self.point_num + 1, 1) self.HamSolve.append(start) V = np.setdiff1d(V, self.HamSolve) BetweenPoint = start VWeight = self.search_min(BetweenPoint - 1, V) Next = self.find_match_vex(BetweenPoint - 1, VWeight) + 1 self.HamSolve.append(Next) self.HamSolve.append(start) V = np.setdiff1d(V, Next) self.HamLength = self.HamLength + VWeight + self.graph[Next - 1][start - 1] BetweenPoint = Next while np.shape(V)[0] != 0: HamPoint = list(set(self.HamSolve)) NearestPoint = 0 NearWeight = np.zeros((len(HamPoint),), dtype=float) NearPoint = np.zeros((len(HamPoint),), dtype=int) for i in range(len(HamPoint)): NearWeight[i] = self.search_min(HamPoint[i] - 1, V) NearPoint[i] = self.find_match_vex(HamPoint[i] - 1, NearWeight[i]) + 1 NearestPoint = NearPoint[self.find_index(NearWeight, np.min(NearWeight))] HamIncrement = np.zeros((len(self.HamSolve) - 1,), dtype=float) for i in range(len(self.HamSolve) - 1): HamIncrement[i] = self.graph[self.HamSolve[i] - 1][NearestPoint - 1] + \ self.graph[NearestPoint - 1][self.HamSolve[i + 1] - 1] - \ self.graph[self.HamSolve[i] - 1][self.HamSolve[i + 1] - 1] MinHamIncrement = np.min(HamIncrement) InsertPoint = self.find_index(HamIncrement, MinHamIncrement) + 1 self.HamSolve.insert(InsertPoint, NearestPoint) self.HamLength += MinHamIncrement V = np.setdiff1d(V, NearestPoint)
五、运行测试实例
main.py
from Hamilton import HamiltonUtil import numpy as np if __name__ == '__main__': E = np.array([[np.float('inf'), 10, 6, 8, 7, 15], [10, np.float('inf'), 5, 20, 15, 16], [6, 5, np.float('inf'), 14, 7, 8], [8, 20, 14, np.float('inf'), 4, 12], [7, 15, 7, 4, np.float('inf'), 6], [15, 16, 8, 12, 6, np.float('inf')]], dtype=float) neibor_point = HamiltonUtil(E) # 最邻近点法 neibor_point.neibor_point() print(neibor_point.HamSolve) print(neibor_point.HamLength) E = np.array([[np.float('inf'), 10, 6, 8, 7, 15], [10, np.float('inf'), 5, 20, 15, 16], [6, 5, np.float('inf'), 14, 7, 8], [8, 20, 14, np.float('inf'), 4, 12], [7, 15, 7, 4, np.float('inf'), 6], [15, 16, 8, 12, 6, np.float('inf')]], dtype=float) nearest_insertion = HamiltonUtil(E) # 最近插值法 nearest_insertion.nearest_insertion() print(nearest_insertion.HamSolve) print(nearest_insertion.HamLength)
