路徑偏移演算法

① 如何解決坐標轉換，坐標偏移的問題

一、坐標體系
首先我們要明白，開發者能接觸到哪些坐標體系呢？
第一種分類：
1、 GPS，WGS-84，原始坐標體系。一般用國際標準的GPS記錄儀記錄下來的坐標，都是GPS的坐標。很可惜，在中國，任何一個地圖產品都不允許使用GPS坐標，據說是為了保密。GPS坐標形式如圖，度分秒形式的經緯度：

2、 GCJ-02，國測局02年發布的坐標體系。又稱「火星坐標」。在中國，必須至少使用GCJ-02的坐標體系。比如谷歌，騰訊，高德都在用這個坐標體系。GCJ-02也是國內最廣泛使用的坐標體系。
3、 其他坐標體系。一般都是由GCJ-02進過偏移演算法得到的。這種體系就根據每個公司的不同，坐標體系都不一樣了。比如，網路和搜狗就使用自己的坐標體系，與其他坐標體系不兼容。

第二種分類：
首先明白，所有坐標體系的原點，都是非洲。

1、 經緯度。這個是球面坐標，對於北京來說，就是(116.38817139.935961)這樣的坐標。比如騰訊、高德、網路都是這樣的經緯度坐標。谷歌是經緯度順序寫反的經緯度坐標。
如果是度分秒坐標，需要進行轉換，才能得到這樣的經緯度坐標。詳見坐標轉換。
2、 墨卡托坐標。平面坐標，相當於是直線距離，數字一般都比較大，像這樣的。(215362.00021333335 99526.00034912192)
墨卡托坐標，主要用於程序的後台計算。直線距離嘛，加加減減幾乎計算方便。
搜狗地圖API就是直接使用的墨卡托坐標。

二、坐標轉換
在各種web端平台，或者高德、騰訊、網路上取到的坐標，都不是GPS坐標，都是GCJ-02坐標，或者自己的偏移坐標系。
比如，你在谷歌地圖API，高德地圖API，騰訊地圖API上取到的，都是GCJ-02坐標，他們三家都是通用的，也適用於大部分地圖API產品，以及他們的地圖產品。
例外，網路API上取到的，是BD-09坐標，只適用於網路地圖相關產品。
例外，搜狗API上取到的，是搜狗坐標，只適用於搜狗地圖相關產品。
例外，谷歌地球，google earth上取到的，是GPS坐標，而且是度分秒形式的經緯度坐標。在國內不允許使用。必須轉換為GCJ-02坐標。

1、度分秒坐標轉換為經緯度
比如，在GPS記錄儀，或者google earth上採集到的是39°31'20.51，那麼應該這樣換算，31分就是31/60度，20.51秒就是20.51/3600度，結果就是39 + 31/60 + 20.51/3600 度。

2、 GPS轉換為GCJ-02坐標
谷歌，高德，騰訊的地圖API官網上，都不直接提供這樣的坐標轉換。如果要得到GCJ-02坐標，最好在他們的地圖上直接取點，或者通過地址解析得到。（這個工具我後續會貼出來的。我就愛干這樣的事情，哈哈。）

不過，在網上搜到了這樣的介面，該介面的type=1就是GPS轉到GCJ-02的墨卡托坐標。請大家對介面保密，哈哈。詳見：

3、GCJ-02與BD-09之間互轉
國測局GCJ-02坐標體系（谷歌、高德、騰訊），與網路坐標BD-09體系的轉換，在CSDN上有很詳細的講解：

不過也有更簡單的演算法，線性演算法（lat和lng是經緯度，球面坐標）：
To_B是轉到網路，To_G是轉到GCJ-02。
var TO_BLNG = function(lng){return lng+0.0065;};
var TO_BLAT = function(lat){return lat+0.0060;};
var TO_GLNG = function(lng){return lng-0.0065;};
var TO_GLAT = function(lat){return lat-0.0060;};

4、經緯緯度轉成墨卡托

5、各家API公司坐標轉換介面的申請
一般需要將您的公司名稱、項目名稱、項目簡介、聯系人和聯系方式，發郵件至地圖API公司的商務部，經過申請，才能使用。
下面是他們的聯系方式：

② 偏移量的 計算方法

曾經的電腦主流是八位的，內存定址只有16位，也就是64K。當年PC機剛出的時候，還不完全是16位電腦，是個20位電腦。
但是他的地址線由兩部分組成，一部分叫做段地址，一部分叫做偏移量，就類似單元樓住址，可以叫做單元的，然後這個某編號住戶。
由這兩個的疊加，形成一個地址。演算法是，段地址占高20-4位，偏移量佔16-0位，然後加起來。

③ 求google 地圖偏移 演算法或數據表 如何校正二維地圖的准確性 謝謝，如有 再加賞更多

一般沒有太大出入的，你是不是用了GOOGLE頁面自帶的工具生成的x,y坐標？那個是不太准，我是通過後台連接google提供的介面將地址轉換成x,y再在頁面顯示的，感覺這個出入就不大了。應為這個介面得到的數據是由全世界的人幫你校正的，精確度比較大。你試試用它提供的java介面吧。其它語言的介面也應該有，不過我不需要用所以沒找。

④ 疊前時間偏移比疊前深度偏移好在哪裡

的成像問題。它與常規疊後時間偏移處理相比有以下優點 1符合斯奈爾定律成像准確適用於復雜介質2消除了疊加引起的彌散現象使得大傾角地層信噪比和解析度有所提高 3能夠綜合利用地質、鑽井和測井等資料來約束處理結果還可以直接利用得到的深度剖面進行構造解釋方便與實際的鑽井數據進行對比。 第 3 頁共 5 頁 所以綜合起來考慮 只有疊前深度偏移才是復雜地質體成像的一種理想方法特別是對於像前陸沖斷帶、逆掩推覆、高陡構造、地下高速火成岩體等可以取得較滿意的成像效果。 Kirchhoff 疊前深度偏移方法的具體實現過程是首先把地下地質體劃分成一個個的面元網格然後計算從地面每一個炮點位置到地下不同面元網格的旅行時形成走時表利用經過選擇的疊前數據集和射線追蹤技術計算出的走時表計算出地下成像點到地面炮點和接收點的走時 tS(x,y,z) 和 tR(x,y,z)以及相應的幾何擴散因子 A(x,y,z)最後在孔徑范圍內對地震數據沿由 tS (x,y,z)和 tR (x,y,z)確定的時距曲面進行加權疊加放在輸出點位置上實現偏移成像。 疊前深度偏移是一個解釋性的處理過程一般包括初始模型建立、模型的迭代優化和最終數據體的成像三個過程其中模型的迭代優化是疊前深度偏移的關鍵和核心。 Kirchhoff 疊前深度偏移方法相對於其它的疊前深度偏移演算法如波動方程疊前深度偏移而言其主要優點是速度較快能夠適應野外採集的不規則觀測系統 同時可以有選擇地輸出目標線提高了速度分析和模型迭代的效率但缺點也是很明顯的具有近似性和方法局限性如多路徑走時、頻散問題、振幅不保真、過分依賴速度模型等因此在速度模型不是十分精確的情況下偏移誤差加上頻散問題使地下地質目標的成像位置嚴重偏離了地下真實構造位置造成鑽井風險增加使深度偏移的意義大打折扣。 第 4 頁共 5 頁 較為理想的疊前成像方法是基於波場延拓的波動方程成像技術其優點是能夠處理各種復雜的波動傳播因此成像精度較高且具有保幅能力但只有計算機技術的迅速發展這項技術的普及才成為可能。 疊前時間偏移和疊前深度偏

⑤ 　疊前深度偏移技術

疊前深度偏移技術是在深度域對每個共偏移距剖面先用已建偏移速度場進行疊前深度偏移，後從每個偏移後的共偏移距剖面抽取共反射點道集，如道集曲線被拉平，則將各道反射波疊加，這就是在深度域先偏移後疊加的技術。它既克服了地層傾角對疊後偏移疊加或偏移成像不佳的影響，又克服了速度橫向變化對反射層形態畸變的影響。在時間域由於速度陷阱的存在，使地震地質解釋成果與地下實際地質情況不符，這為正確客觀地認識地下地質情況帶來巨大困難。特別是對於逆沖構造、鹽下構造和復雜的斷裂構造，由於地震射線按斯奈爾定理折曲，反射波的時距曲線已非雙曲線，疊後偏移在理論和實際上就不能使其正確成像，因此就不能正確地解釋。為此，對復雜構造必須進行疊前深度偏移，這是物探界早已形成的共識。10多年前，其方法和演算法就已成熟。但由於當時計算機發展水平和運算速度的限制，以及在建立速度深度模型上存在檢驗和精度問題，疊前深度偏移技術沒應用到實際生產中去。1996年到現在，由於計算機技術水平和運算速度大幅度提高，基於RISC技術的並行計算機和微機群及高速計算機網路的應用，計算機運算速度達100×10⁸～1000×10⁸次/s（浮點），且成本大為降低。因而，疊前深度偏移技術為解決復雜構造的油氣勘探問題開始投入實際生產。國外的一些大油公司建立了自己的疊前深度偏移系統，為本公司的復雜構造油氣勘探目標服務。因此，他們所研製的疊前深度偏移技術軟體系統是不出售的，也不具備商品化。

以色列PARADIGM地球物理公司的疊前深度偏移交互處理系統Geedepth，是最早推出的商品化的交互疊前深度偏移處理軟體包。該軟體包具有方法思路先進、完全交互化、高精度、高效率和二維疊前深度偏移可在工作站平台上運行等特點。為解決海上復雜構造的油氣勘探問題，1995～1999年，中國海油先後引進二維疊前深度偏移Geodepth軟體包和三維疊前深度偏移技術軟體（Geovista和SIRIUS）。

在引進基礎上，通過消化、吸收和結合實際的創新，在中國海域部分層速度強烈橫向變化和復雜的斷裂構造上，實踐了二維或三維疊前深度偏移技術，獲得了較好的處理效果。

一、疊前深度偏移技術描述

該技術是解決地層速度橫向變化強烈和地質構造復雜地區的地震反射波正確成像、歸位、消除速度陷阱的有效技術手段。但二維疊前深度偏移仍不能解決側面波和不垂直構造走向剖面反射波正確歸位問題。為了闡明疊前深度偏移的主要作用，我們設計了如圖6-85(a）的地質模型，它由淺到深由3層層速度界面構成4套不同層速度的地層，其中，第二層為水平層面，之後用自激自收法作圖6-85(a）地質模型的正演合成地震疊加剖面圖6-85(b）。由圖可見，由於受表層下凹加厚的低速層影響，水平層面下凹畸變、平層同相軸及向斜聚焦都出現了繞射波影像。用已知的速度對圖6-85(b）的數據進行時間偏移，獲時間偏移合成地震剖面圖6-85(c），由圖可見，最淺的反射層偏移效果最好，因該層的層速度是均勻無橫向變化的；第二個反射層面則有下凹畸變，且有殘余的繞射影響；而第三個反射層面則存在明顯的成像誤差。用已知的地層深度－速度模型對圖6-85(b）的數據作波動方程深度偏移處理，得圖6-85(d）的深度偏移剖面。由圖可見，第三個反射層面的成像位置及形態與地質模型非常吻合，繞射影像也都消失。

圖6-98扇三角洲的分布形態圖

⑥ 匯編語言的段地址和偏移地址問題

物理地址1和物理地址2是相同的，沒問題
他們指的是同一個地址空間，只是演算法不同
不會產生問題

⑦ 求走迷宮問題的演算法，要求用非遞歸回溯的方法寫

public class MyMaze { private class Point { //自定義數組下標記錄類型 int x = 0;
int y = 0; public Point() {
this(0, 0);
} public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Point p) {
return (x == p.x) && (y == p.y);
} @Override
public String toString() {
return "(" + x + "," + y + ")";
}
} private int[][] maze = null; //迷宮圖
private java.util.Stack<Point> stack = new java.util.Stack<Point>();
//保存路徑的棧 public MyMaze(int[][] maze) {
this.maze = maze;
} public void go() {
Point out = new Point(maze.length-1, maze[0].length-1); //出口
Point in = new Point(0,0); //入口
Point curNode = in; //當前點為入口
Point nextNode = null; //下一個訪問點(目標點) while(!curNode.equals(out)) {
nextNode = new Point(curNode.x,curNode.y); //設置目標點為當前點，便於下面偏移
if((curNode.x+1)<maze.length&&maze[curNode.x+1][curNode.y]==0) { //如果下方是空的，則目標點向下偏移
nextNode.x++;
} else if((curNode.y+1)<maze[0].length&&maze[curNode.x][curNode.y+1]==0) { //如果右邊是空的，則目標點向右偏移
nextNode.y++;
} else if((curNode.x-1)>=0&&maze[curNode.x-1][curNode.y]==0) { //如果上方是空的，則目標點向上偏移
nextNode.x--;
} else if((curNode.y-1)>=0&&maze[curNode.x][curNode.y-1]==0) { //如果左邊是空的，則目標點向左偏移
nextNode.y--;
} else { //這里是沒有路的狀態
maze[curNode.x][curNode.y] = 3; //標記為死路
if(stack.isEmpty()) { //判斷棧是否為空
System.out.println("Non solution");
return;
}
curNode = stack.pop(); //彈出上一次的點
continue; //繼續循環
} //如果有路的話會執行到這里
stack.push(curNode); //當前點壓入棧中
maze[curNode.x][curNode.y] = 2; //標記為已走
curNode = nextNode; //移動當前點
} if(nextNode.equals(out)) {
stack.push(nextNode); //將出口點添加到當前路勁中
maze[nextNode.x][nextNode.y] = 2; //標記為已走
}
System.out.println("\n該迷宮的一條可行路勁為：");
System.out.println("\n"+stack);
} public static void main(String[] args) {
int[][] maze = {
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 }
};
new MyMaze(maze).go();
}
}

⑧ 導線和電纜截面的如何選擇

選擇導線必須滿足的四個原則：
1）近距離和小負荷按發熱條件選擇導線截面（安全載流量），用導線的發熱條件控制電流，截面積越小，散熱越好，單位面積內通過的電流越大。
2）遠距離和中等負荷在安全載流量的基礎上，按電壓損失條件選擇導線截面，遠距離和中負荷僅僅不發熱是不夠的，還要考慮電壓損失，要保證到負荷點的電壓在合格範圍，電器設備才能正常工作。
3）大檔距和小負荷還要根據導線受力情況，考慮機械強度問題，要保證導線能承受拉力.
4）大負荷在安全載流量和電壓降合格的基礎上，按經濟電流密度選擇，就是還要考慮電能損失，電能損失和資金投入要在最合理范圍。

導線的安全載流量
為了保證導線長時間連續運行所允許的電流密度稱安全載流量。
一般規定是：銅線選5～8A／mm²；鋁線選3～5A／mm²。
安全載流量還要根據導線的芯線使用環境的極限溫度、冷卻條件、敷設條件等綜合因素決定。
一般情況下，距離短、截面積小、散熱好、氣溫低等，導線的導電能力強些，安全載流選上限；
距離長、截面積大、散熱不好、氣溫高、自然環境差等，導線的導電能力弱些，安全載流選下限；
如導電能力，裸導線強於絕緣線，架空線強於電纜，埋於地下的電纜強於敷設在地面的電纜等等。

⑨ cad 多線設置4條線時添加的線如何計算偏移量,這個演算法是怎樣的，求高手指點。

你好，你說的4條線偏移量，是這4條線之間的偏移量是在線型設定時確定的。用MLSTYLE命令可以修改的。上面有偏移量的數值。要想4條線同時偏移現在還沒有支持命令。不知說明白了沒有。祝你順利。

⑩ 求八數碼問題演算法，並說明下該演算法優缺點，要演算法，不是源代碼（可以沒有）。

八數碼問題

一.八數碼問題
八數碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標有1至8的某一數字，不同棋子上標的數字不相同。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態和一個目標狀態，找出一種從初始轉變成目標狀態的移動棋子步數最少的移動步驟。所謂問題的一個狀態就是棋子在棋盤上的一種擺法。棋子移動後，狀態就會發生改變。解八數碼問題實際上就是找出從初始狀態到達目標狀態所經過的一系列中間過渡狀態。
八數碼問題一般使用搜索法來解。搜索法有廣度優先搜索法、深度優先搜索法、A*演算法等。這里通過用不同方法解八數碼問題來比較一下不同搜索法的效果。

二.搜索演算法基類
1.八數碼問題的狀態表示
八數碼問題的一個狀態就是八個數字在棋盤上的一種放法。每個棋子用它上面所標的數字表示，並用0表示空格，這樣就可以將棋盤上棋子的一個狀態存儲在一個一維數組p[9]中，存儲的順序是從左上角開始，自左至右，從上到下。也可以用一個二維數組來存放。
2.結點
搜索演算法中，問題的狀態用結點描述。結點中除了描述狀態的數組p[9]外，還有一個父結點指針last，它記錄了當前結點的父結點編號，如果一個結點v是從結點u經狀態變化而產生的，則結點u就是結點v的父結點，結點v的last記錄的就是結點u的編號。在到達目標結點後，通過last 可以找出搜索的路徑。
3.類的結構
在C++中用類來表示結點，類將結點有關的數據操作封裝在一起。
不同的搜索演算法具有一定共性，也有各自的個性，因此這里將不同搜索演算法的共有的數據和功能封裝在一個基類中，再通過繼承方式實現不同的搜索演算法。
4.結點擴展規則
搜索就是按照一定規則擴展已知結點，直到找到目標結點或所有結點都不能擴展為止。
八數碼問題的結點擴展應當遵守棋子的移動規則。按照棋子移動的規則，每一次可以將一個與空格相鄰棋子移動到空格中，實際上可以看作是空格作相反移動。空格移動的方向可以是右、下、左、上，當然不能移出邊界。棋子的位置，也就是保存狀態的數組元素的下標。空格移動後，它的位置發生變化，在不移出界時，空格向右、下、左和上移動後，新位置是原位置分別加上1、3、-1、-3，如果將空格向右、下、左和上移動分別用0、1、2、3表示，並將-3、3、-1、1放在靜態數組d[4]中，空格位置用spac表示，那麼空格向方向i移動後，它的位置變為spac+d[i]。空格移動所產生的狀態變化，反映出來則是將數組p[]中，0的新位置處的數與0交換位置。
5.八數碼問題的基類

八數碼問題的基類及其成員函數的實現如下：
#define Num 9
class TEight
{
public:
TEight(){}
TEight(char *fname); //用文件數據構造節點
virtual void Search()=0; //搜索
protected:
int p[Num];
int last,spac;
static int q[Num],d[],total;
void Printf();
bool operator==(const TEight &T);
bool Extend(int i);
};
int TEight::q[Num];//儲存目標節點
int TEight::d[]={1,3,-1,-3};//方向
int TEight::total=0;//步數

TEight::TEight(char *fname)
{
ifstream fin;
fin.open(fname,ios::in);
if(!fin)
{
cout<<"不能打開數據文件!"<<endl;
return;
}
int i;
for(i=0;i<Num;)//得到源節點
fin>>p[i++];
fin>>spac;
for(i=0;i<Num;)//得到目標節點
fin>>q[i++];
fin.close();
last=-1;
total=0;
}

void TEight::Printf()//把路徑列印到結果文件
{
ofstream fout;
fout.open("eight_result.txt",ios::ate|ios::app);
fout<<total++<<"t";
for(int i=0;i<Num;)
fout<<" "<<p[i++];
fout<<endl;
fout.close();
}

bool TEight::operator==(const TEight &T)//判斷兩個狀態是否相同
{
for(int i=0;i<Num;)
if(T.p[i]!=p[i++])
return 0;
return 1;
}

bool TEight::Extend(int i)//擴展
{
if(i==0 && spac%3==2 || i==1 && spac>5
|| i==2 && spac%3==0 || i==3 && spac<3)
return 0;
int temp=spac;
spac+=d[i];
p[temp]=p[spac];
p[spac]=0;
return 1;
}

數據文件的結構：
一共三行，第一行是用空格隔開的九個數字0~8，這是初始狀態。第二行是一個數字，空格（數字0）的位置，第三行也是用空格隔開的九個數字0~8，這是目標狀態。

三.線性表
搜索法在搜索過程中，需要使用一個隊列存儲搜索的中間結點，為了在找到目標結點後，能夠找到從初始結點到目標結點的路徑，需要保留所有搜索過的結點。另一方面，不同問題甚至同一問題的不同搜索方法中，需要存儲的結點數量相差很大，所以這里採用鏈式線性表作為存儲結構，同時，為適應不同問題，線性表設計成類模板形式。
template<class Type> class TList; //線性表前視定義

template<class Type> class TNode //線性表結點類模板
{
friend class TList<Type>;
public:
TNode(){}
TNode(const Type& dat);
private:
TNode<Type>* Next;
Type Data;
};

template<class Type> class TList
{
public:
TList(){Last=First=0;Length=0;} //構造函數
int Getlen()const{return Length;} //成員函數，返回線性表長度
int Append(const Type& T); //成員函數，從表尾加入結點
int Insert(const Type& T,int k); //成員函數，插入結點
Type GetData(int i); //成員函數，返回結點數據成員
void SetData(const Type& T,int k); //成員函數，設置結點數據成員
private:
TNode<Type> *First,*Last; //數據成員，線性表首、尾指針
int Length; //數據成員，線性表長度
};

template<class Type> int TList<Type>::Append(const Type& T)
{
Insert(T,Length);
return 1;
}

template<class Type> int TList<Type>::Insert(const Type& T,int k)
{
TNode<Type> *p=new TNode<Type>;
p->Data=T;
if(First)
{
if(k<=0)
{
p->Next=First;
First=p;
}
if(k>Length-1)
{
Last->Next=p;
Last=Last->Next;
Last->Next=0;
}
if(k>0 && k<Length)
{
k--;
TNode<Type> *q=First;
while(k-->0)
q=q->Next;
p->Next=q->Next;
q->Next=p;
}
}
else
{
First=Last=p;
First->Next=Last->Next=0;
}
Length++;
return 1;
}

template<class Type> Type TList<Type>::GetData(int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
return p->Data;
}

template<class Type> void TList<Type>::SetData(const Type& T,int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
p->Data=T;
}
線性表單獨以頭文件形式存放。

四.廣度優先搜索法
在搜索法中，廣度優先搜索法是尋找最短路經的首選。
1.廣度優先搜索演算法的基本步驟
1）建立一個隊列，將初始結點入隊，並設置隊列頭和尾指針
2）取出隊列頭（頭指針所指）的結點進行擴展，從它擴展出子結點，並將這些結點按擴展的順序加入隊列。
3）如果擴展出的新結點與隊列中的結點重復，則拋棄新結點，跳至第六步。
4）如果擴展出的新結點與隊列中的結點不重復，則記錄其父結點，並將它加入隊列，更新隊列尾指針。
5）如果擴展出的結點是目標結點，則輸出路徑，程序結束。否則繼續下一步。
6）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步。
2.搜索路徑的輸出
搜索到目標結點後，需要輸出搜索的路徑。每個結點有一個數據域last，它記錄了結點的父結點，因此輸出搜索路徑時，就是從目標結點Q出發，根據last找到它的父結點，再根據這個結點的last找到它的父結點，....,最後找到初始結點。搜索的路徑就是從初始結點循相反方向到達目標結點的路徑。
3.廣度優先搜索法TBFS類的結構
廣度優先搜索法TBFS類是作為TEight類的一個子類。其類的結構和成員函數的實現如下：
class TBFS:public TEight
{
public:
TBFS(){}
TBFS(char *fname):TEight(fname){}
virtual void Search();
private:
void Printl(TList<TBFS> &L);
int Repeat(TList<TBFS> &L);
int Find();
};

void TBFS::Printl(TList<TBFS> &L)
{
TBFS T=*this;
if(T.last==-1)
return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}

int TBFS::Repeat(TList<TBFS> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}

int TBFS::Find()
{
for(int i=0;i<Num;)
if(p[i]!=q[i++])
return 0;
return 1;
}

void TBFS::Search()
{
TBFS T=*this;
TList<TBFS> L;
L.Append(T);
int head=0,tail=0;
while(head<=tail)
{
for(int i=0;i<4;i++)
{
T=L.GetData(head);
if(T.Extend(i) && T.Repeat(L)>tail)
{
T.last=head;
L.Append(T);
tail++;
}
if(T.Find())
{
T.Printl(L);
T.Printf();
return;
}
}
head++;
}
}
4.廣度優先搜索法的缺點
廣度優先搜索法在有解的情形總能保證搜索到最短路經，也就是移動最少步數的路徑。但廣度優先搜索法的最大問題在於搜索的結點數量太多，因為在廣度優先搜索法中，每一個可能擴展出的結點都是搜索的對象。隨著結點在搜索樹上的深度增大，搜索的結點數會很快增長，並以指數形式擴張，從而所需的存儲空間和搜索花費的時間也會成倍增長。

五、A*演算法
1.啟發式搜索
廣度優先搜索和雙向廣度優先搜索都屬於盲目搜索，這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分龐大時，它們的效率實在太低，往往都是在搜索了大量無關的狀態結點後才碰到解答，甚至更本不能碰到解答。
搜索是一種試探性的查尋過程，為了減少搜索的盲目性引，增加試探的准確性，就要採用啟發式搜索了。所謂啟發式搜索就是在搜索中要對每一個搜索的位置進行評估，從中選擇最好、可能容易到達目標的位置，再從這個位置向前進行搜索，這樣就可以在搜索中省略大量無關的結點，提高了效率。
2.A*演算法
A*演算法是一種常用的啟發式搜索演算法。
在A*演算法中，一個結點位置的好壞用估價函數來對它進行評估。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值（也稱為最小耗費或最小代價），h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以實際上使用的是下面的估價函數：
f(n) = g(n) + h(n)
其中g(n)是從初始結點到節點n的實際代價，h(n)是從結點n到目標結點的最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息，因為g(n)是已知的。用f(n)作為f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。這樣必須滿足兩個條件：（1）g(n)>=g'(n)（大多數情況下都是滿足的，可以不用考慮），且f必須保持單調遞增。（2）h必須小於等於實際的從當前節點到達目標節點的最小耗費h(n)<=h'(n)。第二點特別的重要。可以證明應用這樣的估價函數是可以找到最短路徑的。
3.A*演算法的步驟
A*演算法基本上與廣度優先演算法相同，但是在擴展出一個結點後，要計算它的估價函數，並根據估價函數對待擴展的結點排序，從而保證每次擴展的結點都是估價函數最小的結點。
A*演算法的步驟如下：
1）建立一個隊列，計算初始結點的估價函數f，並將初始結點入隊，設置隊列頭和尾指針。
2）取出隊列頭（隊列頭指針所指）的結點，如果該結點是目標結點，則輸出路徑，程序結束。否則對結點進行擴展。
3）檢查擴展出的新結點是否與隊列中的結點重復，若與不能再擴展的結點重復（位於隊列頭指針之前），則將它拋棄；若新結點與待擴展的結點重復（位於隊列頭指針之後），則比較兩個結點的估價函數中g的大小，保留較小g值的結點。跳至第五步。
4）如果擴展出的新結點與隊列中的結點不重復，則按照它的估價函數f大小將它插入隊列中的頭結點後待擴展結點的適當位置，使它們按從小到大的順序排列，最後更新隊列尾指針。
5）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步。
4.八數碼問題的A*演算法的估價函數
估價函數中，主要是計算h，對於不同的問題，h有不同的含義。那麼在八數碼問題中，h的含意是各什麼？八數碼問題的一個狀態實際上是數字0~8的一個排列，用一個數組p[9]來存儲它，數組中每個元素的下標，就是該數在排列中的位置。例如，在一個狀態中，p[3]=7，則數字7的位置是3。如果目標狀態數字3的位置是8，那麼數字7對目標狀態的偏移距離就是3，因為它要移動3步才可以回到目標狀態的位置。
八數碼問題中，每個數字可以有9個不同的位置，因此，在任意狀態中的每個數字和目標狀態中同一數字的相對距離就有9*9種，可以先將這些相對距離算出來，用一個矩陣存儲，這樣只要知道兩個狀態中同一個數字的位置，就可查出它們的相對距離，也就是該數字的偏移距離：
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
8 4 3 2 3 2 1 2 1 0
例如在一個狀態中，數字8的位置是3，在另一狀態中位置是7，那麼從矩陣的3行7列可找到2，它就是8在兩個狀態中的偏移距離。
估價函數中的h就是全體數字偏移距離之和。顯然，要計算兩個不同狀態中同一數字的偏移距離，需要知道該數字在每個狀態中的位置，這就要對數組p[9]進行掃描。由於狀態發生變化，個數字的位置也要變化，所以每次計算h都沿線掃描數組，以確定每個數字在數組中的位置。為了簡化計算，這里用一個數組存儲狀態中各個數字的位置，並讓它在狀態改變時隨著變化，這樣就不必在每次計算h時，再去掃描狀態數組。
例如，某個狀態中，數字5的位置是8，如果用數組r[9]存儲位置，那麼就有r[5]=8。
現在用數組r[9]存儲當前狀態的數字位置，而用s[9]存儲目標狀態的數字位置，那麼當前狀態數字i對目標狀態的偏移距離就是矩陣中r[i]行s[i]列對應的值。
5.A*演算法的類結構
A*演算法的類聲明如下：
class TAstar:public TEight
{
public:
TAstar(){} //構造函數
TAstar(char *fname); //帶參數構造函數
virtual void Search(); //A*搜索法
private:
int f,g,h; //估價函數
int r[Num]; //存儲狀態中各個數字位置的輔助數組
static int s[Num]; //存儲目標狀態中各個數字位置的輔助數組
static int e[]; //存儲各個數字相對距離的輔助數組
void Printl(TList<TAstar> L); //成員函數，輸出搜索路徑
int Expend(int i); //成員函數，A*演算法的狀態擴展函數
int Calcuf(); //成員函數，計算估價函數
void Sort(TList<TAstar>& L,int k); //成員函數，將新擴展結點按f從小到大順序插入待擴展結點隊列
int Repeat(TList<TAstar> &L); //成員函數，檢查結點是否重復
};

int TAstar::s[Num],TAstar::e[Num*Num];

TAstar::TAstar(char *fname):TEight(fname)
{
for(int i=0;i<Num;)
{
r[p[i]]=i; //存儲初始狀態個個數字的位置
s[q[i]]=i++; //存儲目標狀態個個數字的位置
}
ifstream fin;
fin.open("eight_dis.txt",ios::in); //打開數據文件
if(!fin)
{
cout<<"不能打開數據文件!"<<endl;
return;
}
for(int i=0;i<Num*Num;i++) //讀入各個數字相對距離值
fin>>e[i];
fin.close();
f=g=h=0; //估價函數初始值
}

void TAstar::Printl(TList<TAstar> L)
{
TAstar T=*this;
if(T.last==-1) return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}

int TAstar::Expend(int i)
{
if(Extend(i)) //結點可擴展
{
int temp=r[p[r[0]]]; //改變狀態後數字位置變化，存儲改變後的位置
r[p[r[0]]]=r[0];
r[0]=temp;
return 1;
}
return 0;
}

int TAstar::Calcuf()
{
h=0;
for(int i=0;i<Num;i++) //計算估價函數的 h
h+=e[Num*r[i]+s[i]];
return ++g+h;
}

void TAstar::Sort(TList<TAstar>& L,int k)
{
int n=L.Getlen();
int i;
for(i=k+1;i<n;i++)
{
TAstar T=L.GetData(i);
if(this->f<=T.f)
break;
}
L.Insert(*this,i);
}

int TAstar::Repeat(TList<TAstar> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}

void TAstar::Search()
{
TAstar T=*this; //初始結點
T.f=T.Calcuf(); //初始結點的估價函數
TList<TAstar> L; //建立隊列
L.Append(T); //初始結點入隊
int head=0,tail=0; //隊列頭和尾指針
while(head<=tail) //隊列不空則循環
{
for(int i=0;i<4;i++) //空格可能移動方向
{
T=L.GetData(head); //去隊列頭結點
if(T.h==0) //是目標結點
{
T.Printl(L);//輸出搜索路徑
T.Printf(); //輸出目標狀態
return; //結束
}
if(T.Expend(i)) //若結點可擴展
{
int k=T.Repeat(L); //返回與已擴展結點重復的序號
if(k<head) //如果是不能擴展的結點
continue; //丟棄
T.last=head; //不是不能擴展的結點，記錄父結點
T.f=T.Calcuf(); //計算f
if(k<=tail) //新結點與可擴展結點重復
{
TAstar Temp=L.GetData(k);
if(Temp.g>T.g) //比較兩結點g值
L.SetData(T,k); //保留g值小的
continue;
}
T.Sort(L,head) ; //新結點插入可擴展結點隊列
tail++; //隊列尾指針後移
}
}
head++; //一個結點不能再擴展，隊列頭指針指向下一結點
}
}

六、測試程序
A*演算法的測試：
int main()
{
TAstar aStar("eight.txt");
aStar.Search();
system("pauze");
return 0;
}
eight.txt文件中的數據（初始態和目標態）：
一共三行，第一行是用空格隔開的九個數字0~8，這是初始狀態。第二行是一個數字，空格（數字0）的位置，第三行也是用空格隔開的九個數字0~8，這是目標狀態。

8 3 5 1 2 7 4 6 0
8
1 2 3 4 5 6 7 8 0

eight_dis.txt中的數據（估計函數使用）
0 1 2 1 2 3 2 3 4
1 0 1 2 1 2 3 2 3
2 1 0 3 2 1 4 3 2
1 2 3 0 1 2 1 2 3
2 1 2 1 0 1 2 1 2
3 2 1 2 1 0 3 2 1
2 3 4 1 2 3 0 1 2
3 2 3 2 1 2 1 0 1
4 3 2 3 2 1 2 1 0

eight_Result.txt中的結果（運行後得到的結果）

七、演算法運行結果
1.BFS演算法只能適用於到達目標結點步數較少的情況，如果步數超過15步，運行時間太長，實際上不再起作用。
2.對於隨機生成的同一個可解狀態，BFS演算法最慢，DBFS演算法較慢，A*演算法較快。但在15步以內，DBFS演算法與A*演算法相差時間不大，超過15步後，隨步數增加，A*演算法的優勢就逐漸明顯，A*演算法要比DBFS演算法快5倍以上，並隨步數增大而增大。到25步以上，DBFS同樣因運行時間過長而失去價值。
3.一般來說，解答的移動步數每增加1，程序運行時間就要增加5倍以上。由於八數碼問題本身的特點，需要檢查的節點隨步數增大呈指數形式增加，即使用A*演算法，也難解決移動步數更多的問題。

八、問題可解性
八數碼問題的一個狀態實際上是0~9的一個排列，對於任意給定的初始狀態和目標，不一定有解，也就是說從初始狀態不一定能到達目標狀態。因為排列有奇排列和偶排列兩類，從奇排列不能轉化成偶排列或相反。
如果一個數字0~8的隨機排列871526340，用F(X)表示數字X前面比它小的數的個數，全部數字的F(X)之和為Y=∑(F(X))，如果Y為奇數則稱原數字的排列是奇排列，如果Y為偶數則稱原數字的排列是偶排列。
例如871526340這個排列的
Y=0+0+0+1+1+3+2+3+0=10
10是偶數，所以他偶排列。871625340
Y=0+0+0+1+1+2+2+3+0=9
9是奇數，所以他奇排列。
因此，可以在運行程序前檢查初始狀態和目標狀態的窘是否相同，相同則問題可解，應當能搜索到路徑。否則無解。

PS:整理自網路