哈密尔顿算法

Ⅰ 哈密尔顿路径计算公式有什么实际意义

用最短的路径解决运算。
哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。找一条哈密顿路的近似比为常数的近似算法也是NP完全。

Ⅱ 哈密尔顿回路问题具体指什么

1857年，英国数学家汉密尔顿(Hamilton)提出了着名的汉密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：这两个问题成为数学史上着名的难题。而后者在工程优化、现场管理等现实生活中有重要作用：以电站建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等，最终都归结为赋权汉密尔顿问题，是电站建设中成本控制和进度优化的关键技术；因而，赋权汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题。而且，主生产计划安排，又可以分解为有向图的赋权汉密尔顿问题进行解决；因此，赋权汉密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位，具有重大的理论和现实意义。理论上讲，赋权汉密尔顿问题的最优解总可以用枚举法求出；但在实际工作中，枚举法的计算量巨大，对于n个点的问题存在(n－1)!条汉密尔顿回路，当n比较大时，枚举法显然是行不通的，为此，优化专家们提出了启发式算法[1]，以期求得该问题的近似最优解。而不同算法之目的是共同的，即在多项式的运算量内，尽可能提高其解的精度。其中应用比较广泛的有Clarke和Wright的C－W算法，Norback和Love的几何算法[2]，在此，称这些算法为经典启发式算法，简称经典算法，这些算法的一个共同特点就是非优化性。针对这一特点，本文提出一种局部优化的算法，对业已求得的汉密尔顿回路进行优化。这种算法的结果是以经典算法结果为起点的局部优化解，因此，该算法极大改进了经典启发式算法的性能，且在目前可考证的情况下，均能求得最优解；但是，是否在任何情况下都能求得最优解则尚待证明。

Ⅲ 哈密顿回路的算法是怎样的

哈密顿回路的算法是指:

在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路。

Ⅳ 哈密尔顿系统的辛几何算法是如何算的

哈密尔顿系统是描述各种守恒的物理和力学过程的三种基本形式之一，是一类具有特殊几何结构的常微分方程或偏微分方程，系统的几何结构——辛结构，是该系统的数学基础。20世纪80年代以后，从事计算数学的冯康院士首次系统地提出了哈密尔顿系统的辛几何算法，解决了一系列理论和数值计算问题，获得了远优于现有方法的计算效果，在数学领域取得了世界公认的成就。这一开创性工作已带动了国际上多辛格式的研究，并在天体力学、分子动力学、刚体和多刚体运动、场论等领域的研究中得到了成功的应用。从而开创了一个充满活力，发展前景广阔的新领域。

Ⅳ 哈密顿回路的算法

哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。
从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。
要满足两个条件：
⒈封闭的环
⒉是一个连通图，且图中任意两点可达
经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。
⒊若以1到2、2到3、3到4、4到5、5到1，为计数规律，则各点均出现两次；这种判断方法在计算机编程运算中显得尤为重要，其会精简很多运算过程。
⒋新出炉，有待检测的代码如下：
%-------输入的数据的原数据参照
% v1 v2 v3 v4 v5
%v1 0 20 1 11 2
%v2 0 0 9 1 3
%v3 0 0 0 13 8
%v4 0 0 0 0 6
%v5 0 0 0 0 0
%以上为输入数据的原数据参照
%建议所计算的数据矩阵长度为5，不会产生bug，且不会对任何计算机造成计算负担
%输入数据矩阵长度可以超过5，但是最初计算出的n个最小值中，重复次数超过2的点的种类只允许为一种
a=[0 20 1 11 2
0 0 9 1 3
0 0 0 13 8
0 0 0 0 6
0 0 0 0 0];
l=length(a)
s1=inf
zp=inf
n2=1
f=a
f(a==0)=inf
b=zeros(l)
i1=0
while i1<=l-1
[r c]=find(f==min(min(f)))
b(r⑴，c⑴)=f(r⑴，c⑴)
f(r⑴，c⑴)=inf
i1=i1+1
end
f1=f
[rz cz]=find(b>0)
pathz=[rz cz]
pz=[rz;cz]
p2z=zeros（2*l,1）
i2z=1
n2z=0
while i2z<=2*l
[r2z c2z]=find(pz==pz(i2z,1）)
k1z=size(r2z)
if k1z（1,1）>2
p2z(r2z,1）=pz(r2z,1）
n2z=n2z+1
end
i2z=i2z+1
end
if n2z==2
HHL=b
zp=sum(sum(b))
else
while min(min(f1）)~=inf
if n2>2
b=snh
end
[r1 c1]=find(b>0)
path1=[r1 c1]
p1=[r1;c1]
p2=zeros（2*l,1）
i2=1
n2=0
while i2<=2*l
[r2 c2]=find(p1==p1(i2,1）)
k1=size(r2）
if k1（1,1）>2
p2(r2,1）=p1(r2,1）
n2=n2+1
end
i2=i2+1
end
[r3 c3]=find(p2>0)
p3=zeros(l,2）
i3=0
while i3<=n2-1
if r3⑴<=l
p3(r3⑴，：)=path1(r3⑴，：)
else
p3(r3⑴-l,:)=path1(r3⑴-l,:)
end
r3⑴=[]
i3=i3+1
end
p3(p3==0)=[]
p3=reshape(p3,n2,2）
p8=p2
[r8 c8]=find(p8>0)
p9=p8
r9=r8
i4=1
while i4<=n2
f1(p9(r9⑴，1），：)=inf
f1(:,p9(r9⑴，1）)=inf
r9⑴=[]
i4=i4+1
end
[r4 c4]=find(f1==min(min(f1）))
f1(r4,c4）=inf
b1=b
b1(r4,c4）=a(r4,c4）
i5=1
p4=p3
while i5<=n2
b1=b
b1(r4⑴，c4⑴)=a(r4⑴，c4⑴)
b1(p4（1,1），p4（1,2）)=0
p4（1,:)=[]
[r5 c5]=find(b1>0)
p5=[r5;c5]
i6=1
n6=0
while i6<=2*l
[r6 c6]=find(p5==p5(i6,1）)
k6=size(r6）
if k6（1,1）>2
n6=n6+1
end
i6=i6+1
end
if n6>2
if sum(sum(b1）)<s1
snh=[]
s1=sum(sum(b1）)
snh=b1
end
else
if sum(sum(b1）)<zp
HHL=[]
zp=sum(sum(b1）)
HHL=b1
end
end
i5=i5+1
end
end
[rs cs]=find(HHL>0)
minpaths=[rs cs]
journeys=zp
注：这段代码采用分支定界法作为编写程序的依据，因此代码依旧局限在算法上；而且代码的使用对所要计算的数据是有要求的，如下：
⒈只要数据在开始计算出的n个最小值中，其重复次数超过2次的点的种类只能为一种，例如：代码段中的数据五个最小值中其重复次数超过2次的点只有v5。
⒉数据矩阵格式要求：只允许为上三角矩阵，不支持全矩阵以及下三角矩阵的运算。
⒊代码扩展方法请使用者独立思考，不唯一。
⒋运算数据扩展方法，请使用者独立思考，不唯一。
⒌此代码为本人毕设的附加产品，不会对使用此代码者，因理解不当或使用不当而造成的任何不良后果，付出任何责任。
⒍代码仅供交流。

Ⅵ 哈密尔顿算法是做什么的

你好！
可以用来做图像处理
如有疑问，请追问。

Ⅶ hamilton圈算法是什么意思

哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。

从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。
要满足两个条件：
⒈封闭的环
⒉是一个连通图，且图中任意两点可达
经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。

Ⅷ 我国一位数学家提出了哈密顿体系的保结构算法他是谁

1984年起冯康将其研究重点从以椭圆方程为主的稳态问题转向以哈密顿方程和波动方程为主的动态问题。他于1984年首次提出基于辛几何计算哈密顿体系的方法，即哈密顿体系的保结构算法，从而开创了哈密顿体系计算方法这一富有活力及发展前景的新领域；冯康指导和带领了中国科学院计算中心一个研究组投入了此领域的研究，取得了一系列优秀成果。新的算法解决了久悬未决的动力学长期预测计算方法问题,正在促成天体轨道、高能加速器、分子动力学等领域计算的革新，具有更为广阔的发展前景。冯康多次应邀在国内及西欧、苏联、北美等多国讲学或参加国际会议作主题报告，受到普遍欢迎及高度评价，国际和国内已兴起了许多后继研究。1995年国际工业与应用数学大会已决定邀请冯康就此主题作一小时大会报告。

由于在科学上的突出贡献，他曾先后获得1978年全国科学大会重大成果奖、全国自然科学二等奖、科技进步二等奖及科学院自然科学一等奖等。

Ⅸ 求哈密尔顿链问题（骑士周游问题）的求解高效算法。

我用C实现了一个高效算法。
此算法用不到1秒钟就可以算出结果啦！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
int start_i,start_j,end_i,end_j;
int maze[10][10];
int path[64][2];

void init()
{
int i,j;
for (i = 0; i <= 9; i++)
{
maze[0][i] = 0;
maze[9][i] = 0;
maze[i][0] = 0;
maze[i][9] = 0;
}
maze[1][1] = 2;
maze[1][8] = 2;
maze[8][1] = 2;
maze[8][8] = 2;
for (i = 2; i <= 7; i++)
{
maze[1][i] = 3;
maze[8][i] = 3;
maze[i][1] = 3;
maze[i][8] = 3;
}
for (i = 2; i <= 7; i++)
for (j = 2; j <= 7; j++)
{
maze[i][j] = 4;
}
maze[start_i][start_j]++;
maze[end_i][end_j]++;
}

void visit(int i, int j)
{
int k,new_i,new_j;
maze[i][j] = -maze[i][j];
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (maze[new_i][new_j] > 0)
{
maze[new_i][new_j]--;
}
}
}

void undo_visit(int i, int j)
{
int k,new_i,new_j;
maze[i][j] = -maze[i][j];
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (new_i >= 1 && new_i <= 8 && new_j >= 1 && new_j <= 8 && maze[new_i][new_j] >= 0)
{
maze[new_i][new_j]++;
}
}
}

int try_it(int n, int i, int j, int end_i, int end_j, int range)
{
int new_i,new_j,k,l,dir_select_num;
int dir_select[4][2];
int result;
result = 0;
path[n][0] = i;
path[n][1] = j;
if (i == end_i && j == end_j)
{
result = (n == 64 - 1);
return result;
}
dir_select_num = 0;
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (maze[new_i][new_j] > 0)
{
for (l = dir_select_num - 1; l >= -1; l--)
{
if (l == -1 || maze[new_i][new_j] >= dir_select[l][1])
{
dir_select[l+1][0] = k;
dir_select[l+1][1] = maze[new_i][new_j];
break;
}
dir_select[l+1][0] = dir_select[l][0];
dir_select[l+1][1] = dir_select[l][1];
}
dir_select_num++;
}
}
for (l = 0; l < dir_select_num; l++)
{
if (dir_select[l][1] > dir_select[0][1] + range)
{
break;
}
k = dir_select[l][0];
new_i = i + dir[k][0];
new_j = j + dir[k][1];
visit(i,j);
if (try_it(n+1,new_i,new_j,end_i,end_j,range))
{
undo_visit(i,j);
result = 1;
return result;
}
undo_visit(i,j);
}
return result;
}

int main(int argc, char **argv)
{
int i;
//printf("input start_i start_j end_i end_j: ");
//scanf("%d%d%d%d", &start_i,&start_j,&end_i,&end_j);
if (argc < 5)
{
printf("Usage: %s <start_i> <start_j> <end_i> <end_j>\n", argv[0]);
return 1;
}
start_i = atoi(argv[1]);
start_j = atoi(argv[2]);
end_i = atoi(argv[3]);
end_j = atoi(argv[4]);
if (start_i < 1 || start_i > 8 || start_j < 1 || start_j > 8)
{
printf("Input error!\n");
return 1;
}
if (end_i < 1 || end_i > 8 || end_j < 1 || end_j > 8)
{
printf("Input error!\n");
return 1;
}
if (((start_i + start_j + end_i + end_j)%2) != 1)
{
printf("No solutions!\n");
return 0;
}

init();
if (try_it(0,start_i,start_j,end_i,end_j,0))
{
for (i = 0; i < 64; i++)
{
printf("%d %d\n", path[i][0], path[i][1]);
}
printf("Find a solution!\n");
}
else if (try_it(0,end_i,end_j,start_i,start_j,0))
{
for (i = 64-1; i >= 0; i--)
{
printf("%d %d\n", path[i][0], path[i][1]);
}
printf("Find a solution!\n");
}
else
printf("Cannot find a solutions!\n");
return 0;
}