人工智能实验报告.doc

人工智能实验报告

八数码演示程序
1. 问题描述
1.1八数码问题的解释
八数码问题是人工智能经典难题之一。问题是在3×3 方格盘上，放有八个数码，剩下一个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。本文介绍用A星算法，采用估计值h（n）（曼哈顿距离）和g(m)(当前深度)的和作为估计函数。
1.2八数码问题的搜索形式描述

初始状态：初始状态向量，规定向量中各分量对应的位置，各位置上的初始数字
后继函数：移动规则，按照某条规则移动数字得到的新向量
转移到
目标测试：新向量是否是目标状态，也即为
路径耗散函数：在搜索时，每深入一层则当前步数代价加1，代价总和由当前步数和可能还需要移动的步数之和。
1.3 解决方案介绍
首先，A*算法需要个估价(评价)函数:
f(x)=g(x)+h(x)
…………