?? alpha_beta.c
字號:
/*********************************************************************************
* 程 序 說 明 *
* 功能: Alpha_Beta剪枝程序，該程序只涉及剪枝部分，不涉及博弈部分的內(nèi)容 *
* *
* 說明: *
* 本程序?qū)崿F(xiàn)《人工智能導論》一書所介紹Alpha_Beta剪枝算法，不涉及具體的博弈 *
* 問題，博弈樹用一個給定的樹代替。 *
* 樹用文件表示，讀入內(nèi)容后建立樹結(jié)構(gòu)。 *
* 文件的表示如下： *
* *
* ROOT A //表示A是根節(jié)點 *
* A B1 B2 B3 END //A的子節(jié)點為B1 B2 B3 *
* B1 C1 C2 END //B1的子節(jié)點為C1 C2 *
* B2 C3 C4 C5 END //B2的子節(jié)點為C3 C4 C5 *
* ...... *
* VALUE //賦值標志，為葉節(jié)點賦估計值 *
* D1 7 //D1的估計值為7 *
* D2 8 //D2的估計值為8 *
* D3 -4 //D3的估計值為-4 *
* ...... *
* END //結(jié)束標志 *
* *
* tree1.txt和tree2.txt是兩個給定的樹文件的例子。 *
* 注意: 該程序盡可能用與《人工智能導論》中介紹的算法一致的思路實現(xiàn), 力求簡單明 *
* 了, 注重算法的清晰性，而沒有考慮算法的效率問題。 *
* Alpha_Beta_1.c實現(xiàn)了一個效率更高一些的算法，供參考。 *
* *
* 作者：馬少平 *
* 單位：清華大學智能技術(shù)與系統(tǒng)國家重點實驗室 *
* 時間：2004年8月15日 *
* 修改：2005年9月13日 *
*********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_INT 32767 //定義最大整數(shù)
#define MIN_INT -32768 //定義最小整數(shù)
#define MAX 1 //極大層節(jié)點標志
#define MIN 0 //極小層節(jié)點標志
//以下結(jié)構(gòu)定義了樹結(jié)構(gòu)的一個節(jié)點。
//樹結(jié)構(gòu)的表示如下：
//每個節(jié)點指向其父節(jié)點
//每個節(jié)點指向其子節(jié)點鏈表
//一個節(jié)點的所有子節(jié)點，形成一個兄弟鏈表，其父節(jié)點指向該兄弟鏈表的第一個
//節(jié)點，但是兄弟鏈表中的每個節(jié)點，都指向其父節(jié)點
struct NODE
{
char name[10]; //節(jié)點名
int value; //節(jié)點的值
int level; //節(jié)點處在極大層，還是極小層
struct NODE *pFrom; //該節(jié)點的值來自于哪個子節(jié)點
struct NODE *pFather; //指向父節(jié)點
struct NODE *pChildren; //指向子節(jié)點鏈表
struct NODE *pNext; //指向兄弟鏈表的下一個節(jié)點
};
struct NODE *NewNode(char *name, int level)
/******************************************************
* 功能：動態(tài)產(chǎn)生一個節(jié)點，其狀態(tài)值由參數(shù)name, level *
* 給定。 *
* *
* 入口參數(shù)： *
* name：節(jié)點名 *
* level：節(jié)點是極大節(jié)點還是極小節(jié)點 *
* *
* 返回值：指向新產(chǎn)生的節(jié)點的指針，或者空間不夠時，返 *
* 回NULL *
******************************************************/
{
struct NODE *pNode = NULL;
pNode = malloc(sizeof(struct NODE));
if (pNode == NULL) return NULL;
strcpy(pNode->name, name);
if (level == MAX)
{
pNode->value = MIN_INT;
}
else
{
pNode->value = MAX_INT;
}
pNode->level = level;
pNode->pFrom = NULL;
pNode->pFather = NULL;
pNode->pChildren = NULL;
pNode->pNext = NULL;
return pNode;
}
struct NODE *Search(char *name, struct NODE *pTree)
/******************************************************
* 功能：從已經(jīng)建立的樹中，查找給定名字的節(jié)點，并返回 *
* 指向該節(jié)點的指針 *
* *
* 入口參數(shù)： *
* name：節(jié)點名 *
* pTree: 指向樹根節(jié)點的指針 *
* *
* 返回值：指向給定節(jié)點的指針 *
******************************************************/
{
struct NODE *pNode = NULL;
if (pTree == NULL) return NULL;
if (! strcmp(name, pTree->name)) return pTree; //如果根節(jié)點就是待查找的節(jié)點，則返回該節(jié)點
if (pNode = Search(name, pTree->pNext)) //否則從該節(jié)點的兄弟節(jié)點中遞歸查找
{
return pNode; //如果找到，則返回該節(jié)點
}
if (pNode = Search(name, pTree->pChildren)) //否則在子節(jié)點中遞歸查找
{
return pNode; //如果找到則返回該節(jié)點
}
return NULL; //以上均找不到的話則返回NULL
}
struct NODE *ReadTree(FILE *pFile)
/******************************************************
* 功能：從一個文本文件中讀入一個樹 *
* *
* 入口參數(shù)： *
* pFile：文件指針 *
* *
* 返回值：返回指向樹根節(jié)點的指針，或者空間不夠時，返 *
* 回NULL *
* *
* 文本文件格式說明： *
* ROOT A //表示A是根節(jié)點 *
* A B1 B2 B3 END //A的子節(jié)點為B1 B2 B3 *
* B1 C1 C2 END //B1的子節(jié)點為C1 C2 *
* B2 C3 C4 C5 END //B2的子節(jié)點為C3 C4 C5 *
* ...... *
* VALUE //賦值標志，為葉節(jié)點賦估計值 *
* D1 7 //D1的估計值為7 *
* D2 8 //D2的估計值為8 *
* D3 -4 //D3的估計值為-4 *
* ...... *
* END //結(jié)束標志 *
******************************************************/
{
char name[256];
int value;
struct NODE *pNode = NULL, *pRoot = NULL, *pFNode = NULL, *pLast = NULL;
//在樹文件中，尋找ROOT標志
while (!feof(pFile))
{
fscanf(pFile, "%s", name);
if (feof(pFile)) return NULL;
if (! strcmp(name, "ROOT")) break;
}
fscanf(pFile, "%s", name); //得到根節(jié)點名字
pRoot = NewNode(name, MAX); //建立根節(jié)點
if (pRoot == NULL) return NULL; //如果空間不夠則返回NULL
//讀文本文件，建立樹結(jié)構(gòu)
while (!feof(pFile))
{
fscanf(pFile, "%s", name); //name得到父節(jié)點名字
if (feof(pFile)) return NULL;
if (! strcmp(name, "VALUE")) break;
pFNode = Search(name, pRoot); //得到父節(jié)點在樹中的指針
if (pFNode == NULL) return NULL; //如果樹中不存在該節(jié)點則返回NULL
pLast = NULL;
//讀子節(jié)點，建立父子關(guān)系和兄弟關(guān)系
while (!feof(pFile))
{
fscanf(pFile, "%s", name); //得到子節(jié)點名
if (feof(pFile)) return NULL;
if (! strcmp(name, "END")) break;
pNode = NewNode(name, !pFNode->level); //建立子節(jié)點
if (pNode == NULL) return NULL; //空間不夠用時返回NULL
if (pLast == NULL) //如果是第一個子節(jié)點，其父節(jié)點指向該節(jié)點
{
pFNode->pChildren = pNode;
}
else
{
pLast->pNext = pNode; //否則將該節(jié)點鏈接到兄弟鏈表中
}
pLast = pNode;
pNode->pFather = pFNode; //設(shè)置該節(jié)點的父節(jié)點
}
}
//為葉節(jié)點賦初始估計值
while (!feof(pFile))
{
fscanf(pFile, "%s", name); //得到葉節(jié)點名
if (feof(pFile)) return NULL;
if (! strcmp(name, "END")) break; //END為結(jié)束標志
fscanf(pFile, "%d", &value); //得到葉節(jié)點的初始估計值
if (feof(pFile)) return NULL;
pNode = Search(name, pRoot); //從樹中得到該節(jié)點的指針
if (pNode == NULL) return NULL; //如果樹中沒有該節(jié)點，則返回NULL
pNode->value = value; //為該節(jié)點賦初始估計值
}
return pRoot; //返回樹根節(jié)點
}
void PrintTree(struct NODE *pRoot)
/******************************************************
* 功能：顯示一個樹 *
* *
* 入口參數(shù)： *
* pTree: 指向樹根節(jié)點的指針 *
* *
* 返回值：無 *
* 說明：顯示格式如下(舉例)： *
* A: *
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -