路径偏移算法

① 如何解决坐标转换，坐标偏移的问题

一、坐标体系
首先我们要明白，开发者能接触到哪些坐标体系呢？
第一种分类：
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:整理自网络