Hamilton问题求解 |
您所在的位置：网站首页 › 用python解决tsp问题 › Hamilton问题求解 |
Hamilton问题求解
|
Hamilton问题求解-最近邻点法和最近插入法
一、定义
1. 哈密顿通路
设 G = < V , E > G= G=为一个图（有向图或者无向图）。 G G G中经过的每个顶点一次且仅一次的通路称为哈密顿通路。（通路不一定回到起点，但一定穿过每个顶点一次且仅一次） 2. 哈密顿回路设 G = < V , E > G= G=为一个图（有向图或者无向图）。 G G G中经过的每个顶点一次且仅一次的回路称为哈密顿回路。（回路要求穿过每个顶点一次后回到起点） 3. 性质 存在哈密顿通路（回路）的图一定是连通图哈密顿通路是初级通路，哈密顿回路是初级回路初级是通路（回路）指除了起点和终点之外，所有的顶点和边都互不相同的通路（回路） 若图 G G G中存在哈密顿回路，则它一定存在哈密顿通路只有哈密顿通路，无哈密顿回路的图不叫哈密顿图 二、判定定理目前没有判定哈密顿图的简单充要条件 设无向图 G = < V , E > G= G=为哈密顿图， V 1 V_1 V1是 V V V的任意真子集，则 p ( G − V 1 ) ≤ ∣ V 1 ∣ p(G-V_1)\le |V_1| p(G−V1)≤∣V1∣
p
(
G
−
V
1
)
p(G-V_1)
p(G−V1)为G中删除
V
1
V_1
V1后的所得图的联通分支数目，
∣
V
1
∣
|V_1|
∣V1∣为
V
1
V_1
V1集合中包含的顶点个数。 推论：有割点的图一定不是哈密顿图。 割点：类似下图，去掉
V
1
V_1
V1后连通就剩
(
V
2
,
V
4
)
(V_2,V_4)
(V2,V4)和
(
V
3
,
V
5
)
(V_3,V_5)
(V3,V5)两个连通分量，大于等于2，故其为割点。 d(u),d(v)分别代表顶点u,v的度数。 推论：设G是n(n ≥ \ge ≥ 3)阶无向简单图，若G的最小度 ≥ n 2 \ge \frac{n}{2} ≥2n，则G是哈密顿图。(d1+d2) ≥ \ge ≥ n 由推论可知，对于完全图Kn，当n ≥ \ge ≥ 3时，是哈密顿图，完全二部图Kr,s 当r==s ≥ \ge ≥ 2时是哈密顿图。 在n(n ≥ \ge ≥ 2)阶有向图 D = < V , E > D= D=中，如果略去所有有向边的方向，所得无向图中含生成子图Kn，则D中存在哈密顿通路。推论：n(n ≥ \ge ≥ 3)阶有向完全图是哈密顿图。 三、求解算法 1. 最近邻点法算法思想：每次将离当前顶点最近的顶点加入，一般只能找到近似解，不能找到最优解 算法步骤： 从网络中找一个点做为起点从剩下的点中找一个离上一个点最近的点加入重复步骤2将最后加入的点与起点连接构成回路 2.最近插入法最近插入法(Nearest Insertion)于1977年提出，用于解决TSP问题，可以得到相对最近邻点法更优的解。 算法步骤 任取一点作为整个Hamilton回路的起点，记为 v 1 v_1 v1，同时找出离 v 1 v_1 v1最近的一个顶点 v k v_k vk，形成一个子回路： v 1 → v k → v 1 v_1 \rightarrow v_k \rightarrow v_1 v1→vk→v1在剩下的顶点中寻找一个离子回路中的各顶点最近的顶点 v s v_s vs，并在已有子回路中找到一条边 ( v i , v j ) (v_i,v_j) (vi,vj)，使得 w i s + w s j − w i j w_{is}+w_{sj}-w_{ij} wis+wsj−wij最小，然后把顶点 v s v_s vs插入顶点 v i v_i vi和 v j v_j vj之间，用两条边 ( v i , v s ) (v_i,v_s) (vi,vs)和 ( v s , v j ) (v_s,v_j) (vs,vj)代替原来的边 ( v i , v j ) (v_i,v_j) (vi,vj)形成一条新的回路： v 1 → . . . → v i → v s → v j → . . . → v 1 v_1\rightarrow ...\rightarrow v_i\rightarrow v_s\rightarrow v_j\rightarrow ...\rightarrow v_1 v1→...→vi→vs→vj→...→v1重复步骤2，直到所有的顶点都加入到子回路。此时，最后的回路就是所求的TSP的一个较好的Hamilton回路。 四、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] |
【本文地址】
今日新闻 |
推荐新闻 |