用c++实现的基于免疫算法/遗传算法的连通图最短哈密顿回路（TSP问题）求解，并支持记录迭代过程与画图。注释应有尽有，各项参数可调，结构清晰且难度较低，适合通过代码对经典免疫算法进行学习。
2022-11-18 14:29:50
53.61MB
1
【哈密顿圈问题】
对于一个有向图G=(V,E),如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈。即，哈密顿圈构成一条经过所有的顶点，没有重复的“路线”。如图6是一个含有哈密顿圈的图。
图6 一个含有哈密顿圈的有向图
证明哈密顿圈问题是NPC的，可以通过证明3-SAT≤p\leq_p≤p哈密顿圈来得到。
【3-SAT≤p\leq_p≤p哈密顿圈】
构造方法如下:
(1)对于每一个变量xix_ixi,创建3m+3个顶点。命名为vi,1,…,vi,3m+3v_{i,1},…,v_{i,3m+3}vi,1,…,vi,3m+3，并且对相邻的顶点，添加边(vi,j,vi,j+1v
2022-03-17 21:33:11
376KB
1
求哈密顿回路的递归算法
Hamiltonian(int k) // x[0]=1, k从2开始
{ while(1)
{ while(1)
{ x[k-1]=(x[k-1]+1)%(N+1);
if(x[k-1] == 0) break;
if(edge(k-2,k-1))
for(int j=0; (j
2021-12-14 20:15:33
1.4MB
1
课程的随堂作业，C语言的，用dev就能运行，萌新代码，勿喷，仅仅帮助不想写作业的朋友方便一下，反正老师也不会仔细检查的
2021-07-21 16:40:13
644B
1