「八数码问题java」八数码问题java代码

今天给各位分享八数码问题java的知识，其中也会对八数码问题java代码进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、用Java实现8数码问题！
• 2、九宫格拼图·求此问题解法~~思路~代码都可~~就是关于其还原算法的·急~在线等~多谢哈
• 3、八数码问题，逆序数判定是否有解，需要考虑0吗？
• 4、求八数码问题算法，并说明下该算法优缺点，要算法，不是源代码（可以没有）。
• 5、用java写八数码难题，有一个鼠标mouseclick类用来生成一个随机数组，然后在另一个窗口组件

用Java实现8数码问题！

你可以先把你写的程序发上来，一方面是帮你修改一下，方便你学习，另一方面我的程序不一定适合你的要求。我们在上人工智能的时候写过与之类似的程序，八数码，八皇后，迷宫之类。

九宫格拼图·求此问题解法~~思路~代码都可~~就是关于其还原算法的·急~在线等~多谢哈

在一个3×3的九宫中有1－8这8个数及一个空格随机的摆放在其中的格子里，如图1－1所示。现在要求实现这个问题：将其调整为如图1－1右图所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。

（图1－1）

二、题目分析：

这是人工智能中的经典难题之一，问题是在3×3方格棋盘中，放8格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列（如下图1－2到图1－3的转换）。

（图1－2） （图1－3）

该问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。可以把一个随机排列的数组从左到右从上到下用一个一维数组表示，如上图1－2我们就可以表示成｛8，7，1，5，2，6，3，4，0｝其中0代表空格。

在这个数组中我们首先计算它能够重排列出来的结果，公式就是：

∑（F（X））＝Y，其中F（X）

是一个数前面比这个数小的数的个数,Y为奇数和偶数时各有一种解法。（八数码问题是否有解的判定 ）

上面的数组可以解出它的结果。

F（8）＝0；

F（7）＝0；

F（1）＝0；

F（5）＝1；

F（2）＝1；

F（6）＝3；

F（3）＝2；

F（4）＝3；

Y＝0＋0＋0＋1＋1＋3＋2＋3＝10

Y＝10是偶数，所以其重排列就是如图1－3的结果，如果加起来的结果是奇数重排的结果就是如图1－1最右边的排法。

三、算法分析

求解方法就是交换空格（0）位置，直至到达目标位置为止。图形表示就是：

（图3－1）

要想得到最优的就需要使用广度优先搜索，九宫的所以排列有9！种，也就是362880种排法，数据量是非常大的，使用广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，可以把数据进行适当的压缩。使用DWORD形式保存，压缩形式是每个数字用3位表示，这样就是3×9＝27个字节，由于8的二进制表示形式1000，不能用3位表示，使用了一个小技巧就是将8表示为000，然后用多出来的5个字表示8所在的位置，就可以用DWORD表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。

类结构如下：

class CNineGird

{

public:

struct PlaceList

{

DWORD Place;

PlaceList* Left;

PlaceList* Right;

};

struct Scanbuf

{

DWORD Place;

int ScanID;

};

struct PathList

{

unsigned char Path[9];

};

private:

PlaceList *m_pPlaceList;

Scanbuf *m_pScanbuf;

RECT m_rResetButton;

RECT m_rAutoButton;

public:

int m_iPathsize;

clock_t m_iTime;

UINT m_iStepCount;

unsigned char m_iTargetChess[9];

unsigned char m_iChess[9];

HWND m_hClientWin;

PathList *m_pPathList;

bool m_bAutoRun;

private:

inline bool AddTree(DWORD place , PlaceList* parent);

void FreeTree(PlaceList* parent);

inline void ArrayToDword(unsigned char *array , DWORD data);

inline void DwordToArray(DWORD data , unsigned char *array);

inline bool MoveChess(unsigned char *array , int way);

bool EstimateUncoil(unsigned char *array);

void GetPath(UINT depth);

public:

void MoveChess(int way);

bool ComputeFeel();

void ActiveShaw(HWND hView);

void DrawGird(HDC hDC , RECT clientrect);

void DrawChess(HDC hDC , RECT clientrect);

void Reset();

void OnButton(POINT pnt , HWND hView);

public:

CNineGird();

~CNineGird();

};

计算随机随机数组使用了vector模板用random_shuffle（，）函数来打乱数组数据，并计算目标结果是什么。代码：

void CNineGird::Reset()

{

if(m_bAutoRun) return;

vector vs;

int i;

for (i = 1 ; i 9 ; i ++)

vs.push_back(i);

vs.push_back(0);

random_shuffle(vs.begin(), vs.end());

random_shuffle(vs.begin(), vs.end());

for ( i = 0 ; i 9 ; i ++)

{

m_iChess[i] = vs[i];

}

if (!EstimateUncoil(m_iChess))

{

unsigned char array[9] = {1,2,3,8,0,4,7,6,5};

memcpy(m_iTargetChess , array , 9);

}

else

{

unsigned char array[9] = {1,2,3,4,5,6,7,8,0};

memcpy(m_iTargetChess , array , 9);

}

m_iStepCount = 0;

}

数据压缩函数实现：

inline void CNineGird::ArrayToDword(unsigned char *array , DWORD data)

{

unsigned char night = 0;

for ( int i = 0 ; i 9 ; i ++)

{

if (array[i] == 8)

{

night = (unsigned char)i;

break;

}

}

array[night] = 0;

data = 0;

data = (DWORD)((DWORD)array[0] 29 | (DWORD)array[1] 26 |

(DWORD)array[2] 23 | (DWORD)array[3] 20 |

(DWORD)array[4] 17 | (DWORD)array[5] 14 |

(DWORD)array[6] 11 | (DWORD)array[7] 8 |

(DWORD)array[8] 5 | night);

array[night] = 8;

}

解压缩时跟压缩正好相反，解压代码：

inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)

{

unsigned char chtem;

for ( int i = 0 ; i 9 ; i ++)

{

chtem = (unsigned char)(data (32 - (i + 1) * 3) 0x00000007);

array[i] = chtem;

}

chtem = (unsigned char)(data 0x0000001F);

array[chtem] = 8;

}

由于可扩展的数据量非常的大，加上在保存的时候使用的是DWORD类型，将每一步数据都记录在一个排序二叉树中，按从小到大从左到有的排列，搜索的时候跟每次搜索将近万次的形式比较快几乎是N次方倍，把几个在循环中用到的函数声明为内联函数，并在插入的时候同时搜索插入的数据会不会在树中有重复来加快总体速度。二叉树插入代码：

inline bool CNineGird::AddTree(DWORD place , PlaceList* parent)

{

if (parent == NULL)

{

parent = new PlaceList();

parent-Left = parent-Right = NULL;

parent-Place = place;

return true;

}

if (parent-Place == place)

return false;

if (parent-Place place)

{

return AddTree(place , parent-Right);

}

return AddTree(place , parent-Left);

}

计算结果是奇数排列还是偶数排列的代码：

bool CNineGird::EstimateUncoil(unsigned char *array)

{

int sun = 0;

for ( int i = 0 ; i 8 ; i ++)

{

for ( int j = 0 ; j 9 ; j ++)

{

if (array[j] != 0)

{

if (array[j] == i +1 )

break;

if (array[j] i + 1)

sun++;

}

}

}

if (sun % 2 == 0)

return true;

else

return false;

}

移动到空格位的代码比较简单，只要计算是否会移动到框外面就可以了，并在移动的时候顺便计算一下是不是已经是目标结果，这是用来给用户手工移动是给与提示用的，代码：

inline bool CNineGird::MoveChess(unsigned char *array , int way)

{

int zero , chang;

bool moveok = false;

for ( zero = 0 ; zero 9 ; zero ++)

{

if (array[zero] == 0)

break;

}

POINT pnt;

pnt.x = zero % 3;

pnt.y = int(zero / 3);

switch(way)

{

case 0 : //up

if (pnt.y + 1 3)

{

chang = (pnt.y + 1) * 3 + pnt.x ;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

case 1 : //down

if (pnt.y - 1 -1)

{

chang = (pnt.y - 1) * 3 + pnt.x ;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

case 2 : //left

if (pnt.x + 1 3)

{

chang = pnt.y * 3 + pnt.x + 1;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

case 3 : //right

if (pnt.x - 1 -1)

{

chang = pnt.y * 3 + pnt.x - 1;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

}

if (moveok !m_bAutoRun)

{

m_iStepCount ++ ;

DWORD temp1 ,temp2;

ArrayToDword(array , temp1);

ArrayToDword(m_iTargetChess , temp2);

if (temp1 == temp2)

{

MessageBox(NULL , "你真聪明这么快就搞定了!" , "^_^" , 0);

}

}

return moveok;

}

在进行广度搜索时候，将父结点所在的数组索引记录在子结点中了，所以得到目标排列的时候，只要从子结点逆向搜索就可以得到最优搜索路径了。用变量m_iPathsize来记录总步数，具体函数代码：

void CNineGird::GetPath(UINT depth)

{

int now = 0 , maxpos = 100 ;

UINT parentid;

if (m_pPathList != NULL)

{

delete[] m_pPathList;

}

m_pPathList = new PathList[maxpos];

parentid = m_pScanbuf[depth].ScanID;

DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);

while(parentid != -1)

{

if (now == maxpos)

{

maxpos += 10;

PathList * temlist = new PathList[maxpos];

memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));

delete[] m_pPathList;

m_pPathList = temlist;

}

DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);

parentid = m_pScanbuf[parentid].ScanID;

}

m_iPathsize = now;

}

动态排列的演示函数最简单了，为了让主窗体有及时刷新的机会，启动了一个线程在需要主窗体刷新的时候，用Slee（UINT）函数来暂停一下线程就可以了。代码：

unsigned __stdcall MoveChessThread(LPVOID pParam)

{

CNineGird * pGird = (CNineGird *)pParam;

RECT rect;

pGird-m_iStepCount = 0;

::GetClientRect(pGird-m_hClientWin , rect);

for ( int i = pGird-m_iPathsize ; i 0 ; i --)

{

memcpy(pGird-m_iChess , pGird-m_pPathList[i].Path , 9);

pGird-m_iStepCount ++;

InvalidateRect( pGird-m_hClientWin , rect , false);

Sleep(300);

}

char msg[100];

sprintf(msg , "^_^ ! 搞定了!\r\n计算步骤用时%d毫秒" , pGird-m_iTime);

MessageBox(NULL , msg , "~_~" , 0);

pGird-m_bAutoRun = false;

return 0L;

}

最后介绍一下搜索函数的原理，首先得到源数组，将其转换成DWORD型，与目标比较，如果相同完成，不同就交换一下数据和空格位置，加入二叉树，搜索下一个结果，直到没有步可走了，在搜索刚刚搜索到的位置的子位置，这样直到找到目标结果为止，函数：

bool CNineGird::ComputeFeel()

{

unsigned char *array = m_iChess;

UINT i;

const int MAXSIZE = 362880;

unsigned char temparray[9];

DWORD target , fountain , parent , parentID = 0 , child = 1;

ArrayToDword(m_iTargetChess , target);

ArrayToDword(array , fountain);

if (fountain == target)

{

return false;

}

if (m_pScanbuf != NULL)

{

delete[] m_pScanbuf;

}

m_pScanbuf = new Scanbuf[MAXSIZE];

AddTree(fountain ,m_pPlaceList);

m_pScanbuf[ 0 ].Place = fountain;

m_pScanbuf[ 0 ].ScanID = -1;

clock_t tim = clock();

while(parentID MAXSIZE child MAXSIZE)

{

parent = m_pScanbuf[parentID].Place;

for ( i = 0 ; i 4 ; i ++) // 0 :UP , 1:Down ,2:Left,3:Right

{

DwordToArray(parent , temparray);

if (MoveChess(temparray,i)) //是否移动成功

{

ArrayToDword(temparray , fountain);

if (AddTree(fountain, m_pPlaceList)) //加入搜索数

{

m_pScanbuf[ child ].Place = fountain;

m_pScanbuf[ child ].ScanID = parentID;

if (fountain == target) //是否找到结果

{

m_iTime = clock() - tim;

GetPath(child);//计算路径

FreeTree(m_pPlaceList);

delete[] m_pScanbuf;

m_pScanbuf = NULL;

return true;

}

child ++;

}

}

} // for i

parentID++;

}

m_iTime = clock() - tim;

FreeTree(m_pPlaceList);

delete[] m_pScanbuf;

m_pScanbuf = NULL;

return false;

}

重要函数的介绍结束;下面是程序的运行结果和运算结果：

八数码问题，逆序数判定是否有解，需要考虑0吗？

求逆序数的时候不要算0的。如果算上零的逆序数，对换之后奇偶性可能改变。

求八数码问题算法，并说明下该算法优缺点，要算法，不是源代码（可以没有）。

八数码问题

一.八数码问题

八数码问题也称为九宫问题。在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;iNum;)//得到源节点

finp[i++];

finspac;

for(i=0;iNum;)//得到目标节点

finq[i++];

fin.close();

last=-1;

total=0;

}

void TEight::Printf()//把路径打印到结果文件

{

ofstream fout;

fout.open("eight_result.txt",ios::ate|ios::app);

fouttotal++"t";

for(int i=0;iNum;)

fout" "p[i++];

foutendl;

fout.close();

}

bool TEight::operator==(const TEight T)//判断两个状态是否相同

{

for(int i=0;iNum;)

if(T.p[i]!=p[i++])

return 0;

return 1;

}

bool TEight::Extend(int i)//扩展

{

if(i==0 spac%3==2 || i==1 spac5

|| i==2 spac%3==0 || i==3 spac3)

return 0;

int temp=spac;

spac+=d[i];

p[temp]=p[spac];

p[spac]=0;

return 1;

}

数据文件的结构：

一共三行，第一行是用空格隔开的九个数字0~8，这是初始状态。第二行是一个数字，空格（数字0）的位置，第三行也是用空格隔开的九个数字0~8，这是目标状态。

三.线性表

搜索法在搜索过程中，需要使用一个队列存储搜索的中间结点，为了在找到目标结点后，能够找到从初始结点到目标结点的路径，需要保留所有搜索过的结点。另一方面，不同问题甚至同一问题的不同搜索方法中，需要存储的结点数量相差很大，所以这里采用链式线性表作为存储结构，同时，为适应不同问题，线性表设计成类模板形式。

templateclass Type class TList; //线性表前视定义

templateclass Type class TNode //线性表结点类模板

{

friend class TListType;

public:

TNode(){}

TNode(const Type dat);

private:

TNodeType* Next;

Type Data;

};

templateclass 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:

TNodeType *First,*Last; //数据成员，线性表首、尾指针

int Length; //数据成员，线性表长度

};

templateclass Type int TListType::Append(const Type T)

{

Insert(T,Length);

return 1;

}

templateclass Type int TListType::Insert(const Type T,int k)

{

TNodeType *p=new TNodeType;

p-Data=T;

if(First)

{

if(k=0)

{

p-Next=First;

First=p;

}

if(kLength-1)

{

Last-Next=p;

Last=Last-Next;

Last-Next=0;

}

if(k0 kLength)

{

k--;

TNodeType *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;

}

templateclass Type Type TListType::GetData(int k)

{

TNodeType *p=First;

while(k--0)

p=p-Next;

return p-Data;

}

templateclass Type void TListType::SetData(const Type T,int k)

{

TNodeType *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(TListTBFS L);

int Repeat(TListTBFS L);

int Find();

};

void TBFS::Printl(TListTBFS L)

{

TBFS T=*this;

if(T.last==-1)

return;

else

{

T=L.GetData(T.last);

T.Printl(L);

T.Printf();

}

}

int TBFS::Repeat(TListTBFS L)

{

int n=L.Getlen();

int i;

for(i=0;in;i++)

if(L.GetData(i)==*this)

break;

return i;

}

int TBFS::Find()

{

for(int i=0;iNum;)

if(p[i]!=q[i++])

return 0;

return 1;

}

void TBFS::Search()

{

TBFS T=*this;

TListTBFS L;

L.Append(T);

int head=0,tail=0;

while(head=tail)

{

for(int i=0;i4;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(TListTAstar L); //成员函数，输出搜索路径

int Expend(int i); //成员函数，A*算法的状态扩展函数

int Calcuf(); //成员函数，计算估价函数

void Sort(TListTAstar L,int k); //成员函数，将新扩展结点按f从小到大顺序插入待扩展结点队列

int Repeat(TListTAstar L); //成员函数，检查结点是否重复

};

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

TAstar::TAstar(char *fname):TEight(fname)

{

for(int i=0;iNum;)

{

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;iNum*Num;i++) //读入各个数字相对距离值

fine[i];

fin.close();

f=g=h=0; //估价函数初始值

}

void TAstar::Printl(TListTAstar 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;iNum;i++) //计算估价函数的 h

h+=e[Num*r[i]+s[i]];

return ++g+h;

}

void TAstar::Sort(TListTAstar L,int k)

{

int n=L.Getlen();

int i;

for(i=k+1;in;i++)

{

TAstar T=L.GetData(i);

if(this-f=T.f)

break;

}

L.Insert(*this,i);

}

int TAstar::Repeat(TListTAstar L)

{

int n=L.Getlen();

int i;

for(i=0;in;i++)

if(L.GetData(i)==*this)

break;

return i;

}

void TAstar::Search()

{

TAstar T=*this; //初始结点

T.f=T.Calcuf(); //初始结点的估价函数

TListTAstar L; //建立队列

L.Append(T); //初始结点入队

int head=0,tail=0; //队列头和尾指针

while(head=tail) //队列不空则循环

{

for(int i=0;i4;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(khead) //如果是不能扩展的结点

continue; //丢弃

T.last=head; //不是不能扩展的结点，记录父结点

T.f=T.Calcuf(); //计算f

if(k=tail) //新结点与可扩展结点重复

{

TAstar Temp=L.GetData(k);

if(Temp.gT.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:整理自网络

用java写八数码难题，有一个鼠标mouseclick类用来生成一个随机数组，然后在另一个窗口组件

通常我们传递值到另一个对象中时会使用两种方法：JavaBean的构造方法和set方法，其原理都是给对象中的某个属性赋值。例：

public class Bean {

     private int[] datas;

     //构造方法赋值

     public Bean(int[] datas) {

         this.datas = datas;

     }   

     //set方法赋值

     public void setDatas(int[] datas) {

         this.datas = datasa;

     }

}

在鼠标事件内传递数组，只需要通过上述两种方法传递即可。

import java.awt.event.ActionEvent;

import java.awt.event.ActionListener;

import java.util.Arrays;

import javax.swing.JButton;

import javax.swing.JFrame;

import javax.swing.JTextArea;

public class RandomArrayFrame extends JFrame {

    public static void main(String[] args) {

        new RandomArrayFrame();

    }

    public RandomArrayFrame() {

        setTitle("Hello");

        setBounds(100, 100, 500, 500);

        setVisible(true);

        JButton btn = new JButton("生成随机数组");

        getContentPane().add(btn);

        btn.addActionListener(new ActionListener() {

            @Override

            public void actionPerformed(ActionEvent e) {

                //点击事件，点击生成一个数组并将数组传递到另一个窗口中。

                int[] arr = { 1, 3, 456, 7, 8, 9 };

                new ShowRandomArrayFrame(arr).setVisible(true);

            }

        });

    }

}

class ShowRandomArrayFrame extends JFrame {

    public ShowRandomArrayFrame(int[] arr) {

        setTitle("Hello");

        setBounds(100, 100, 500, 500);

        JTextArea area = new JTextArea(Arrays.toString(arr));

        getContentPane().add(area);

    }

}

结果如图：

八数码问题java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于八数码问题java代码、八数码问题java的信息别忘了在本站进行查找喔。