節點定址演算法
『壹』 夢幻西遊自動尋路的尋路演算法怎麼算
A*尋路演算法 A*（A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的
節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價
中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最
好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價
函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎？肯定沒懂。接著看。
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是
。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函
數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計
算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}
『貳』 衡量無線感測網路節點定位演算法的性能指標有哪些
定位精準度：空間實體位置信息與真實位置之間的接近程度。
有效定位范圍：定位系統所能定位的有效范圍
節點密度：播撒的感測器節點的疏密程度
信標節點密度：信標節點在整個WSN中所佔比例
容錯性與自適應性
安全性：指系統對合法用戶的響應以及對非法請求的抗拒
功耗：低
代價與成本：包括時間代價，空間代價，資金代價都要盡可能低
『叄』 無線感測器網路移動節點定位演算法有哪些比較新的理論方法
大致有這幾種種演算法：信號強度、收信角度、收信時間和收信時間差。還有特殊一點的位置指紋演算法。
1、信號強度是指距離和信號強度之間有一定的函數關系，通過接收到的信號強度可以推算出距離。這種方法受到的干擾太大，誤差非常大。
2、收信角度是指兩個蜂窩狀接收裝置可以分辨出信號的來源，做兩條射線，交點即為位置。精度一般。
3、收信時間法是指從發送到接收是有時間差的，發送的時候信號中包含時間信息，接收的時候對照接收時間，做差即可。由於電磁波速度快，所以對於時間校準的要求很高。
4、收信時間差法是指移動點接收來自兩個基站的不同信號，可以測量前後兩次接收到信號的時間差。根據雙曲線定義：到兩定點距離差為定值的點在雙曲線上。那麼再來兩個基站，所做雙曲線的交點，就是所求點的距離。這種方法是上述幾種精度最高的。
5、位置指紋演算法。是指在待測區域內布置指紋狀一層層的節點，這樣在這樣的網中放置一個待測節點，那麼待測節點的位置可以通過插值法計算出。精度也比較高，不過需要布置比較節點。（摘自中國物聯網校企聯盟第二十一期線上活動）
希望有所幫助！ 求採納~
-中國物聯網校企聯盟技術部
『肆』 關節點的求解演算法
利用深度優先搜索便可以求的圖的關節點，本由此可判別圖是否重連通。
從任一點出發深度優先遍歷得到優先生成樹，對於樹中任一頂點V而言，其孩子節點為鄰接點。由深度優先生成樹可得出兩類關節點的特性：
（1）若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關節點。因為圖中不存在連接不同子樹頂點的邊，若刪除此節點，則樹便成為森林。
（2）若生成樹中某個非葉子節點V，其某棵子樹與V的祖先節點無連接，則V為關節點。因為刪去v，則其子樹和圖的其它部分被分割開來 low[v] 設對連通圖G=（V,E）進行先深搜索的先深編號為dnf[v]，產生的先深生成樹為S=（V,T），B試回退邊之集。對每個頂點v，low[v]定義如下
low[v]=Min{dfn[v],Min{low[w]|w是v的一個子女}，Min{dfn[x]|（v，x）是一條回邊}}//dfn數組記錄頂點的深度優先數
演算法： 求無向圖的雙連通分量
輸入：連通的無向圖G=( V, E )。L[v]表示關於v的鄰接表
輸出：G的所有雙連通分量，每個連通分量由一序列的邊組成。 1.計算先深編號：對圖進行先深搜索，計算每個結點v的先深編號dnf[v]，形成先深生成樹S=（V,T）。
2.計算low[v]：在先深生成樹上按後根順序進行計算每個頂點v的 low[v]， low[v]取下述三個結點中的最小者：
(1) dfn[v]；
(2) dfn[w]，凡是有回退邊（v,w）的任何結點w；
(3) low[y]，對v的任何兒子y。
3.求關節點：
(1)樹根是關節點，當且僅當它有兩個或兩個以上的兒子（第一類關節點）；
(2)非樹根結點v是關節點當且僅當v有某個兒子y，使low[y]≥dnf[v]（第二類關節點）。
求雙連通分量的演算法――同先深搜索演算法（略）
『伍』 Hashmap 與 jdk1.8中對hash演算法和定址演算法是如何優化的
數組+最簡單的原理
[<張三，32歲>，<李四，54歲>] —>數組
對key計算出一個hash值，根據這個hash值對數組進行取模，也就是index,定位到數組里的元素中去
map.get(「張三「) —> hash值 —> 對數組長度進行取模 —> return array[1]
Array[1]= <李四，54歲>
1、hash值進行右移 16位，把2進制往右邊推16位，把高16位推到低16位上來，前面用0來補齊，然後原來的hash值 與 右移出來的hash值 進行異或 異或出來的hash值包含了高16位與低16位hash值得特徵。使高低16位都參與了運算
異或出來的 hash值 就是一個32位的 int值
異或 兩個一樣 是0； 兩個不一樣 是1
如 1 0
1 1
0 1
數組—> hash值對數組長度取模，定位到數組的一個位置
2、優化地方，定址演算法優化
（n-1）& hash —> 數組里的一個位置
取模運算，他是性能比較差，為了優化這個數組定址的過程
（n-1）& hash —>效果要跟hash對n取模，效果是一樣的，但是與運算的性能要比hash對n取模要高很多
總結jdk1.8中對hash演算法和定址演算法是如何優化的？
1、hash演算法的優化：對每個hash值，在他的低16位中，讓高低16位進行異或，讓他的低16位同時保持了高低16位的特徵，盡量避免一些hash值後續出現沖突，大家可能會進入數組的同一個位置。
2、定址演算法的優化：用與運算替代取模，提升性能。
map.put 和 map.get —> hash演算法優化（避免hash沖突），定址性能優化
算出key 的hash值，到數組中定址，找到一個位置，把key-value對放進數組，或從數組里取出來
兩個key 多個key ，他們算出來的hash值，與n-1 ，與運算後，發現定位出來的數組的位置還是一樣的，hash碰撞，hash沖突
會在這位置掛一個鏈表，這個鏈表裡放入多個元素，讓多個key-value 對，同時放在數組的一個位置離
get，如果定位到這個數組里發現這個位置掛了一個鏈表，此時遍歷鏈表，找到你要的key-value對就可以了
假設這個鏈表很長，可能會導致遍歷鏈表，性能會比較差 O(n)
優化，如果鏈表的長度達到了一定的長度之後，其實會把鏈表轉換為紅黑樹，遍歷一顆紅黑樹找到一個元素，此時O(logn)，性能會比鏈表高一些
『陸』 數學建模中，給出非常多的節點，求這些節點的最短路徑（類似一條線的路徑），應該用什麼演算法好
下面是我自己編寫的一段代碼，用來求過包含兩千多個點的最短路，速度很快，比遺傳、蟻群快而且最短路更短。你可以試試看，有問題再問我。
function [S,len]=short(P)
% 此程序用來求相同類型點間的最短路
% P表示某一類型的點的坐標矩陣
% p是最短路徑
% d是路徑權值和
%建立權值矩陣
n=length(P);%求該類型點的數量
W=zeros(n,n);
for i=1:n %計算權值並填充權值矩陣,由於各點聯通，此權值矩陣就是該圖的最短路矩陣
for j=(i+1):n
W(i,j)=sqrt((P(i,1)-P(j,1))^2+(P(i,2)-P(j,2))^2);
end
end
for i=2:n
for j=1:(i-1)
W(i,j)=W(j,i);
end
end
%求通過所有點的最短路
%先求從i點至j點，必須通過指定其他n-2個點的最短路,選出其中的的最短路
S=zeros(1,n);
S(1)=1; %先插入1,2點，以此為基準，每次插進一個新點
S(2)=2;
d1=2*W(1,2);
for i=3:n %新加入的點的標號
d1i=zeros(1,i); %插入第i個點，有i中可能的距離,其中最小值將為該輪的d1
for j=1:i %新加入點的位置，插入第i個點是有i個空位可供選擇
if j==1 %在第一個空位插入
d1i(j)=d1+W(i,S(1))+W(i,S(i-1))-W(S(1),S(i-1)); %插入點在首端時，距離為原距離與第i點與上一次插入後的第1位置的點之間距離之和
end
if j>1 & j<i %在中間的空位插入
d1i(j)=d1+W(S(j-1),i)+W(i,S(j))-W(S(j-1),S(j));
end
if j==i
d1i(j)=d1+W(S(i-1),i)+W(S(1),i)-W(S(1),S(i-1));
end
end
[d1,I]=min(d1i);
S((I+1):i)=S(I:(i-1)); %將第I位後面的點後移一位
S(I)=i;%將第i點插入在I位置
end
len=d1;
下面這段代碼是我用來把上面的結果保存到txt文件中的代碼，如果你需要，可以用用。代碼是我上次用過的沒有改，你自己按照需要自己改吧。
clear
close all
clc
loaddata
X=[C;E;I;J];
[S,len]=short(X);
DrawPath(S,X);
print(1,'-dpng','cmeiju3.png');
% 將結果保存至txt文件
fid=fopen('cmeijulujin.txt','wt'); %創建alunjin.txt文件
fprintf(fid,'c號刀具\n');
fprintf(fid,'%d %d\n',X(S));
save('cmeijus','S');
save('cmeijulen','len');