《人工智能：一种现代的方法》实例(一) |
您所在的位置：网站首页 › 八数码问题a*算法python › 《人工智能：一种现代的方法》实例(一) |
《人工智能：一种现代的方法》实例(一)
|
文章目录
前言1 问题描述2 问题求解2.0 代码的一些功能函数2.1 广度优先搜索2.2 深度有限搜索2.3 启发式搜索：不在位的数码数或曼哈顿距离之和
前言
本实例是对第三章的总结与应用，分别利用无信息搜索和有信息搜索对八数码问题进行求解，加深对不同策略的特点的印象与理解。 1 问题描述在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定随机的初始状态，需要几步能到达目标状态（用0表示空格），目标状态如图2所示。  图1 随机初始状态  图2 目标状态
状态空间:状态描述指明8个棋子以及空格在棋盘9个方格上的分布。初始状态:任何状态都可能是初始状态，注意要到达任何一个给定的目标。后继函数（行动空间+转移模型）:用来产生通过四个行动(把空位向Left、Right、Up或Down移动）能够达到的合法状态。目标测试:用来检测状态是否能匹配上图2中所示的目标布局。路径耗散:每一步的耗散值为1，因此整个路径的耗散值是路径中的步数。
2 问题求解
2.0 代码的一些功能函数
关键结构体的定义
/*
*描述：声明一个节点，存储当前九宫格状态
* 以目标状态为例，puzzle: {{0,0,0},{0,1,1},{0,2,2},
{1,0,3},{1,1,4},{1,2,5},
{2,0,6},{2,1,7},{2,2,8},}
nextActionList: {[1,0] 向上移动
[-1,0] 向下移动
[0,1] 向左移动
[0.-1]} 向右移动
nextAxtionList的大小
int result[2] = { 0,0 };
cout
//从队列头部取出结点
PUZZLE_NODE currentPuzzleNode = puzzleNodeQueue.front();
//若当前结点状态和目标状态一致，则打印正确结果；若不一致则继续扩展结点查找
if (checkObject(currentPuzzleNode, objPuzzleNode))
{
//将该节点的前继动作按顺序打印，得到并输出移动的步骤
for (int i = 0; i
cout
currentPuzzleNode = updatePuzzleNodeActionList(currentPuzzleNode);
}
//将当前结点pop出
puzzleNodeQueue.pop();
//循环动作序列，扩展可走相邻结点
for (int i = 0; i
for (int actionIndex = 0; actionIndex
continue;
}
//结点深度+1
nextPuzzleNode.depth = currentPuzzleNode.depth + 1;
//将可走结点放到队列中
puzzleNodeQueue.push(nextPuzzleNode);
}
}
}
return result;
}
2.2 深度有限搜索
算法流程 利用深度有限搜索，与深度优先类似，只是设置了一个深度上限，防止无限地扩展。 这里每次只扩展一个新的结点，而这个新的结点是从前继结点的可走动作序列中选择一个可走的动作进行更新的，更新后则需要将该新结点压入栈中。 在进入下一轮循环中，利用栈的后进先出性质，取出栈顶的结点，标为已访问后，同样先判断是否达到目标状态，若不是则在扩展新结点之前，需利用已访问的结点来更新当前结点的可走动作序列（保证每一次更新的状态都是有效的），重复上述步骤直至找到目标状态。关键代码展示
int* depthFirstSearch(PUZZLE_NODE initialNode, PUZZLE_NODE objPuzzleNode)
{
int result[2] = { 0,0 };
cout
//从栈顶取出结点
PUZZLE_NODE currentPuzzleNode = puzzleNodeStack.top();
//若当前结点状态和目标状态一致，则打印正确结果；若不一致则继续扩展结点查找
if (checkObject(currentPuzzleNode, objPuzzleNode) && currentPuzzleNode.depth
//寻找相邻子节点并任意找一个结点放入stack中
visited[visitedNum(currentPuzzleNode)] = 1;
//更新该结点的可走动作
if (currentPuzzleNode.nextActionList.size() == 0)
{
currentPuzzleNode = updatePuzzleNodeActionList(currentPuzzleNode);
}
//遍历访问过的结点，对当前结点的可走动作序列进行剪枝
for (int i = 0; i
currentPuzzleNode.nextActionList.erase(currentPuzzleNode.nextActionList.begin() + i);
i = i - 1;//**注意vector容量的变化
}
}
//每次选择可走动作的第一个，若达到最深结点，需要将现有结点删除
if (currentPuzzleNode.depth
PUZZLE_NODE nextPuzzleNode = moveToPuzzleNode(currentPuzzleNode.nextActionList[0], currentPuzzleNode);
//将前继动作放入当前的nextPuzzleNode，便于移动步骤的回查
if (!currentPuzzleNode.precedeActionList.empty())
{
for (int actionIndex = 0; actionIndex
//若无可走动作，则将当前结点pop出
puzzleNodeStack.pop();
}
}
else
{
//若达到最大搜索深度，则将当前结点pop出
puzzleNodeStack.pop();
}
}
}
return result;
}
2.3 启发式搜索：不在位的数码数或曼哈顿距离之和
算法流程 启发式搜索是一种有信息的搜索策略，与无信息搜索最大不同就是其在进行状态转移时需要评估可走状态到目标状态的距离（h(n)），这里的启发式用的A*搜索，与贪婪算法不同就是它的评估函数(f(n))需要加上行动的代价，保证了其最优性，之前的笔记也说过，多提一嘴。 扩展结点时与BFS类似，扩展该节点的所有可走的状态，重点就是这里需要一个open列表来放置待扩展的结点，那么真正执行动作的依据是什么呢？则需要比较该open列表中所有状态的启发式函数，取出最小的一个进行扩展，然后重复上述步骤，将扩展出来的结点放入open列表中，此时就继续比较（open列表此时有所有之前待扩展的结点），重复循环，直至找到目标状态。关键代码展示
int* heuristicSearchInformedByIncorrectNum(PUZZLE_NODE initialNode, PUZZLE_NODE objPuzzleNode)
{
int result[2] = { 0,0 };
cout
//从openlist中取出头部结点
PUZZLE_NODE currentPuzzleNode = openList.front();
//若当前结点状态和目标状态一致，则打印正确结果；若不一致则继续扩展结点查找
if (checkObject(currentPuzzleNode, objPuzzleNode))
{
//判断是否达到目标状态后，将该节点的前继动作按顺序打印，得到并输出移动的步骤
//由于与前面代码有重复，不重复展示
}
else
{
//将已访问过的结点标记为1
visited[visitedNum(currentPuzzleNode)] = 1;
if (currentPuzzleNode.nextActionList.size() == 0)
{
currentPuzzleNode = updatePuzzleNodeActionList(currentPuzzleNode);
}
//只对走过（从openlist pop出来）的结点进行剪枝
for (int i = 0; i
currentPuzzleNode.nextActionList.erase(currentPuzzleNode.nextActionList.begin() + i);
i = i - 1;//**注意vector容量的变化
}
}
//循环当前结点的可走动作序列扩张结点
for (int i = 0; i
if (visitedNum(nextPuzzleNode) == visitedNum(openList[i]))
{
t_isExist = 1;
break;
}
}
if (t_isExist)
{
continue;
}
//把新节点的前继动作加上
if (!currentPuzzleNode.precedeActionList.empty())
{
for (int actionIndex = 0; actionIndex
//对openlist里面的启发式进行排序，找最小
if (t_minh == -1)
{
t_minh = openList[i].m_f1;
t_minNode = i;
}
else if (openList[i].m_f1 |
【本文地址】
今日新闻 |
推荐新闻 |