哈密爾頓演算法

Ⅰ 哈密爾頓路徑計算公式有什麼實際意義

用最短的路徑解決運算。
哈密頓路徑也稱作哈密頓鏈，指在一個圖中沿邊訪問每個頂點恰好一次的路徑。找一條哈密頓路的近似比為常數的近似演算法也是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;
}