?? a_star_8.c
字號:
******************************************************/
{
while (pList) //依次打印鏈表
{
PrintNode(pList);
pList = pList->pNext;
}
}
void PrintPath(struct NODE *pNode)
/******************************************************
* 功能：在屏幕上打印解路徑。在搜索過程中，每個節(jié)點(diǎn)指 *
* 向其父節(jié)點(diǎn)，從目標(biāo)節(jié)點(diǎn)開始，遞歸打印各節(jié)點(diǎn)， *
* 既得到解路徑 *
* *
* 入口參數(shù)： *
* pGoal：指向求解得到的目標(biāo)節(jié)點(diǎn) *
* *
* 返回值：無 *
******************************************************/
{
if (pNode == NULL) return;
PrintPath(pNode->pFather);
PrintNode(pNode);
}
int IsGrandFather(struct NODE *pNode, struct NODE *pFather)
/******************************************************
* 功能：判斷一個節(jié)點(diǎn)是否與自己的祖父節(jié)點(diǎn)所表示的狀態(tài) *
* 一樣 *
* *
* 入口參數(shù)： *
* pNode：指向給定節(jié)點(diǎn)的指針 *
* pFather：指向給定節(jié)點(diǎn)的父節(jié)點(diǎn)的指針 *
* *
* 返回值：當(dāng)給定節(jié)點(diǎn)所表示的狀態(tài)與自己的祖父一樣時， *
* 返回1，否則返回0 *
******************************************************/
{
if (pFather == NULL) return 0;
if (pFather->pFather == NULL) return 0;
return Equal(pNode, pFather->pFather);
}
int IsGoal(struct NODE *pNode)
/******************************************************
* 功能：判斷給定節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn) *
* *
* 入口參數(shù)： *
* pNode：指向給定節(jié)點(diǎn)的指針 *
* *
* 返回值：當(dāng)給定節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時，返回1，否則返回0 *
******************************************************/
{
return Equal(pNode, &g_Goal);
}
int H_Function(struct NODE *pNode)
/******************************************************
* 功能：計算給定節(jié)點(diǎn)的h值，h = 不在位的將牌數(shù) *
* *
* 入口參數(shù)： *
* pNode：指向給定節(jié)點(diǎn)的指針 *
* *
* 返回值：h值 *
******************************************************/
{
int i, j, h = 0;
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
if (pNode->a[i][j] && (pNode->a[i][j] != g_Goal.a[i][j]))
{
h++;
}
}
}
return h;
}
struct NODE *Move(struct NODE *pNode, int i1, int j1)
/******************************************************
* 功能：[i1,j1]位置的將牌走到空格處，并產(chǎn)生一個新節(jié)點(diǎn)*
* *
* 入口參數(shù)： *
* pNode：指向原始節(jié)點(diǎn)的指針 *
* i1, j1：給出走動的將牌的位置 *
* *
* 返回值：返回新節(jié)點(diǎn)的指針，或者空間不夠時，返回NULL *
******************************************************/
{
int i0, j0, i, j;
struct NODE *pTempNode;
pTempNode = malloc(sizeof(struct NODE));
if (pTempNode == NULL) return NULL; //申請不到空間
//復(fù)制原始節(jié)點(diǎn)
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
pTempNode->a[i][j] = pNode->a[i][j];
}
}
pTempNode->i0 = pNode->i0;
pTempNode->j0 = pNode->j0;
//移動將牌，并記錄空格所在的位置
i0 = pTempNode->i0;
j0 = pTempNode->j0;
pTempNode->a[i0][j0] = pTempNode->a[i1][j1];
pTempNode->a[i1][j1] = 0;
pTempNode->i0 = i1;
pTempNode->j0 = j1;
return pTempNode;
}
struct NODE *Expand(struct NODE *pNode)
/******************************************************
* 功能：生成指定節(jié)點(diǎn)的所有子節(jié)點(diǎn) *
* *
* 入口參數(shù)： *
* pNode：指向給定節(jié)點(diǎn)的指針 *
* *
* 返回值：所有子節(jié)點(diǎn)形成的鏈表 *
******************************************************/
{
struct NODE *pSubNodeList = NULL, *m = NULL;
int i, j, i1, j1;
//以下兩重循環(huán)，試探空格周圍上下左右四個位置的將牌，走到空格處的情況
// 一次生成給定節(jié)點(diǎn)的所有子節(jié)點(diǎn)
for (i = -1; i <= 1; i++)
{
for (j = -1; j <= 1; j++)
{
//排除一些非法的位置
if (i == 0 && j == 0) continue;
if (i != 0 && j != 0) continue;
i1 = pNode->i0 + i;
j1 = pNode->j0 + j;
if (i1 < 0 || j1 < 0 || i1 > 2 || j1 > 2) continue;
m = Move(pNode, i1, j1); //產(chǎn)生下一個狀態(tài)m
if (m == NULL) return NULL; //空間不夠用，失敗退出
if (IsGrandFather(m, pNode))//如果m與他的祖父狀態(tài)相同，或者是一個非法狀態(tài)，則舍棄m
{
free(m);
continue;
}
//對于節(jié)點(diǎn)m
m->pFather = pNode; //標(biāo)記其父節(jié)點(diǎn)為n
m->g = pNode->g + 1; //其g值為其父節(jié)點(diǎn)的g值加1
m->f = m->g + H_Function(m); //計算其f值，f = g+h
m->pNext = pSubNodeList; //將m加入到子節(jié)點(diǎn)鏈表中
pSubNodeList = m;
}
}
return pSubNodeList;
}
struct NODE *A_Star(struct NODE *s)
/******************************************************
* 功能：A*算法主函數(shù) *
* *
* 入口參數(shù)： *
* s：指向初始節(jié)點(diǎn)的指針 *
* *
* 返回值：指向求解得到的目標(biāo)節(jié)點(diǎn)的指針，或者返回NULL *
* 表示空間不夠用或者找不到問題的解 *
******************************************************/
{
struct NODE *n = NULL, *m = NULL, *pNode = NULL, *pSubNodeList = NULL;
g_pOpen = s; //初始化OPEN表和CLOSED表
g_pClosed = NULL;
while (g_pOpen) //OPEN表不空
{
n = g_pOpen; //取出OPEN表的第一個元素n
if (IsGoal(n)) return n; //如果n為目標(biāo)節(jié)點(diǎn)，則成功結(jié)束
g_pOpen = g_pOpen->pNext; //否則，從OPEN表中刪除n
g_pClosed = AddToClosed(n, g_pClosed); //將n加入到CLOSED中
pSubNodeList = Expand(n); //擴(kuò)展節(jié)點(diǎn)n，得到其所有子節(jié)點(diǎn)
while (pSubNodeList)
{
m = pSubNodeList;
pSubNodeList = pSubNodeList->pNext;
if (pNode = In(m, g_pOpen)) //如果m已經(jīng)出現(xiàn)在OPEN表中
{
if (m->f < pNode->f) //如果m的f值小于OPEN表中相同狀態(tài)的f值
{
//則將該節(jié)點(diǎn)從OPEN表中刪除，并將m加入到OPEN表中。
g_pOpen = AddToOpen(m, Del(pNode, g_pOpen));
free(pNode);
}
else //否則舍棄m
{
free(m);
}
}
else if (pNode = In(m, g_pClosed)) //如果m已經(jīng)出現(xiàn)在CLOSED中
{
if (m->f < pNode->f) //如果m的f值小于CLOSED表中相同狀態(tài)的f值
{
//則將該節(jié)點(diǎn)從CLOSED表中刪除，并重新添加到OPEN表中
g_pClosed = Del(pNode, g_pClosed);
g_pOpen = AddToOpen(m, g_pOpen);
free(pNode);
}
else //否則舍棄m節(jié)點(diǎn)
{
free(m);
}
}
else //其他情況，將m加入到OPEN表中
{
g_pOpen = AddToOpen(m, g_pOpen);
}
}
}
//如果OPEN表空了，還沒有找到目標(biāo)節(jié)點(diǎn)，則搜索以失敗結(jié)束，
//返回NULL
return NULL;
}
void main(void)
{
struct NODE *s;
s = NewNode(2, 1, 6, 4, 0, 8, 7, 5, 3); //設(shè)置初始節(jié)點(diǎn)
s = A_Star(s); //A*搜索
if (s) PrintPath(s); //如果找到問題的解，則輸出解路徑
else printf("找不到問題的解！\n");
FreeList(g_pOpen); //釋放動態(tài)節(jié)點(diǎn)
FreeList(g_pClosed);
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -