?? a_star_8.c
字號:
/*********************************************************************************
* 程 序 說 明 *
* 功能: 用A*算法求解8數碼問題 *
* 說明: *
* 本程序按照《人工智能導論》一書所介紹的A*算法求解8數碼問題。 *
* 表示：用3*3矩陣表示8數碼的一個狀態，左上角位置為(0, 0), 右下角位置為(2, 2), *
* 1~8表示8個數碼，0表示空白位置。 *
* *
* 注意: 該程序盡可能用與算法一致的思路實現算法, 力求簡單明了, 注重算法的清晰性，*
* 而沒有考慮算法的效率問題。 *
* *
* 作者：馬少平 *
* 單位：清華大學智能技術與系統國家重點實驗室 *
* 時間：2004年8月15日 *
*********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
struct NODE
{
char a[3][3]; //表示8數碼狀態的矩陣
int i0; //(i0,j0)表示0所在的位置
int j0; //
double g; //該節點的g值
double f; //該節點的f值
struct NODE *pFather; //指向該節點的父節點
struct NODE *pNext; //在OPEN表或者CLOSED表中，指向下一個元素
};
struct NODE *g_pOpen = NULL; //全程變量，OPEN表
struct NODE *g_pClosed = NULL; //全程變量，CLOSED表
struct NODE g_Goal = {{{1, 2, 3}, {8, 0, 4}, {7, 6, 5}},
1, 1, 0, 0, NULL, NULL}; //初始化一個目標節點
int Equal(struct NODE *pNode1, struct NODE *pNode2)
/******************************************************
* 功能：判斷兩個節點所表示的狀態是否相等 *
* *
* 入口參數： *
* pNode1：指向節點1的指針 *
* pNode2：指向節點2的指針 *
* *
* 返回值：當兩個節點所表示的狀態相等時，返回1，否則 *
* 返回0 *
******************************************************/
{
int i, j;
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
if (pNode1->a[i][j] != pNode2->a[i][j])
return 0;
}
}
return 1;
}
struct NODE *NewNode(int i00, int i01, int i02,
int i10, int i11, int i12,
int i20, int i21, int i22)
/******************************************************
* 功能：動態產生一個節點 *
* *
* 入口參數： *
* i00~i22：給出8數碼問題的一個狀態，分別為狀態矩陣 *
* [0,0]~ [2,2]元素 *
* *
* 返回值：指向新產生的節點的指針，或者空間不夠用時， *
* 返回NULL *
******************************************************/
{
struct NODE *pNode = NULL;
int i, j;
int bEnd = 0;
pNode = malloc(sizeof(struct NODE));
if (pNode == NULL) return NULL; //當申請不到空間時，返回NULL
pNode->a[0][0] = i00;
pNode->a[0][1] = i01;
pNode->a[0][2] = i02;
pNode->a[1][0] = i10;
pNode->a[1][1] = i11;
pNode->a[1][2] = i12;
pNode->a[2][0] = i20;
pNode->a[2][1] = i21;
pNode->a[2][2] = i22;
pNode->g = 0;
pNode->f = 0;
pNode->pFather = NULL;
pNode->pNext = NULL;
//找'0'所在的位置，并記錄
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
if (pNode->a[i][j] == 0)
{
pNode->i0 = i;
pNode->j0 = j;
bEnd = 1;
break;
}
}
if (bEnd) break;
}
return pNode;
}
void FreeList(struct NODE *pList)
/******************************************************
* 功能：釋放動態產生的鏈表 *
* *
* 入口參數： *
* pList：指向OPEN表或者CLOSED表的指針 *
* *
* 返回值：無 *
******************************************************/
{
struct NODE *pNode = NULL;
while (pList)
{
pNode = pList;
pList = pList->pNext;
free(pNode);
}
}
struct NODE *In(struct NODE *pNode, struct NODE *pList)
/******************************************************
* 功能：判斷一個節點是否在一個鏈表中 *
* *
* 入口參數： *
* pNode：指向給定節點的指針 *
* pList：指向給點鏈表的指針 *
* *
* 返回值：當pNode在pList中時，返回以pNode為首的鏈表 *
* 的后一部分；否則返回NULL *
******************************************************/
{
if (pList == NULL) return NULL;
if (Equal(pNode, pList)) return pList;
return In(pNode, pList->pNext);
}
struct NODE *Del(struct NODE *pNode, struct NODE *pList)
/******************************************************
* 功能：從鏈表pList中刪除節點pNode *
* *
* 入口參數： *
* pNode：指向給定節點的指針 *
* pList：指向給定的鏈表 *
* *
* 返回值：刪除給定節點后的鏈表 *
******************************************************/
{
if (pList == NULL) return pList;
if (Equal(pNode, pList)) return pList->pNext;
pList->pNext = Del(pNode, pList->pNext);
return pList;
}
struct NODE *AddToOpen(struct NODE *pNode, struct NODE *pOpen)
/******************************************************
* 功能：將一個節點按照f值（從小到大）插入到OPEN表中 *
* *
* 入口參數： *
* pNode: 指向給定節點的指針 *
* pOpen：指向OPEN表的指針 *
* *
* 返回值：指向插入給定節點后OPEN表的指針 *
* *
* 注意：同一個節點（具有相同指針的一個節點），只能向 *
* 表中添加一次，否則可能會造成循環鏈表 *
******************************************************/
{
if (pOpen == NULL) //OPEN表為空
{
pNode -> pNext = NULL;
return pNode;
}
if (pNode->f < pOpen->f) //給定節點的f值小于OPEN表第一個節點的f值
{
pNode->pNext = pOpen; //插入到OPEN的最前面
return pNode;
}
pOpen->pNext = AddToOpen(pNode, pOpen->pNext); //遞歸
return pOpen;
}
struct NODE *AddToClosed(struct NODE *pNode, struct NODE *pClosed)
/******************************************************
* 功能：將一個節點插入到CLOSED表中 *
* *
* 入口參數： *
* pNode: 指向給定節點的指針 *
* pClosed：指向CLOSED表的指針 *
* *
* 返回值：指向插入給定節點后CLOSED表的指針 *
* *
* 注意：同一個節點（具有相同指針的一個節點），只能向 *
* 表中添加一次，否則可能會造成循環鏈表 *
******************************************************/
{
pNode->pNext = pClosed;
return pNode;
}
void PrintNode(struct NODE *pNode)
/******************************************************
* 功能：在屏幕上打印一個節點，用于調試程序 *
* *
* 入口參數： *
* pNode：指向節點的指針 *
* *
* 返回值：無 *
******************************************************/
{
int i, j;
for (i = 0; i < 3; i++)
{
printf("|");
for (j = 0; j < 3; j++)
{
printf(" %1d", pNode->a[i][j]);
}
printf(" |\n");
}
printf("(i0 = %d, j0 = %d, g = %f, f = %f)\n",
pNode->i0, pNode->j0, pNode->g, pNode->f);
}
void PrintList(struct NODE *pList)
/******************************************************
* 功能：在屏幕上打印一個鏈表，用于調試程序 *
* *
* 入口參數： *
* pList：指向鏈表的指針 *
* *
* 返回值：無 *
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -