昆明理工大学 八数码实验报告
昆明理工大学信息工程与自动化学院学生实验报告
（ 2014 — 2015 学年第 1 学期）
课程名称：人工智能及其应用开课实验室：信自楼504 2014年11月 26日年级、专业、班计科122班学号201210405204 邹华宇成绩
实验项目名称八数码问题指导教师吴霖
教
师
评
语
该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□
该同学的实验能力： A.强□ B.中等□ C.差□
该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□
实验报告是否规范： A.规范□ B.基本规范□ C.不规范□
实验过程是否详细记录： A.详细□ B.一般□ C.没有□
教师签名：
年月日
一、上机目的及内容
1.上机内容：
求解八数码问题。
问题描述：八数码难题，问题描述：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允许位于空格左，上，右，下方的牌移入空格。用广度优先搜索策略寻找从初始状态到目标状态的解路径。
2.上机目的:
（1）复习程序设计和数据结构课程的相关知识；
（2）熟悉人工智能系统中的问题求解过程；
（3）熟悉对八码数问题的建模、求解及编程语言的运用。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点的表中；
（2）建立一个叫做CLOSED的已扩展节点表，其初始为空表；
（3）LOOP:若OPEN表是空表，则失败退出；
（4）选择OPEN表上的第一个节点，把它从OPEN表移除并放进CLOSED表中，称此节点为节点n；
（5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；
（6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点舔到图中；
（7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN表或CLOSED表上的成员，确定是否需要更改通到n的指针方向；
（8）按某一任意方式或按某个探视值，重排OPEN表。
宽度优先算法实现过程
（1）把起始节点放到OPEN表中；
（2）如果OPEN是个空表，则没有解，失败退出；否则继续；
（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；
（4）扩展节点n。如果没有后继节点，则转向（2）；
（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转（2）。
深度优先实现过程
（1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得一个解；
（2）如果OPEN为一空表，则失败退出；
（3）把第一个节点从OPEN表移到CLOSED表；
（4）如果节点n的深度等于最大深度，则转向（2）；
（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；
（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUAL C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程）
1、先创建项目，新建Source File文件：main.cpp。
#include
#include "Node.h"
#include "Queue.h"
#include "Search.h"
#include "Tree.h"
void CreateNode1(std::vector
{
s.push_back(2);
s.push_back(8);
s.push_back(3);
s.push_back(1);
s.push_back(0);
s.push_back(4);
s.push_back(7);
s.push_back(6);
s.push_back(5);
}
void CreateNode4(std::vector
d.push_back(2);
d.push_back(8);
d.push_back(3);
d.push_back(1);
d.push_back(6);
d.push_back(4);
d.push_back(7);
d.push_back(0);
d.push_back(5);
}
void CreateNode8(std::vector
d.push_back(0);
d.push_back(2);
d.push_back(3);
d.push_back(1);
d.push_back(8);
d.push_back(4);
d.push_back(7);
d.push_back(6);
d.push_back(5);
}
void CreateNode20(std::vector
d.push_back(2);
d.push_back(0);
d.push_back(8);
d.push_back(1);
d.push_back(4);
d.push_back(3);
d.push_back(7);
d.push_back(6);
d.push_back(5);
}
void CreateNode27(std::vector
d.push_back(1);
d.push_back(2);
d.push_back(3);
d.push_back(8);
d.push_back(0);
d.push_back(4);
d.push_back(7);
d.push_back(6);
d.push_back(5);
}
void CreateNode_test1(std::vector
d.push_back(7);
d.push_back(6);
d.push_back(5);
d.push_back(4);
d.push_back(0);
d.push_back(1);
d.push_back(3);
d.push_back(8);
d.push_back(2);
}
void test_expand()
{
std::vector
CreateNode1(s);
std::vector
CreateNode4(d);
Node source(s);
Node dest(d);
source.Display();
Search search(&source);
std::cout << source.Expand(dest, search); }
void test_search()
{
std::vector
CreateNode1(s);
std::vector
CreateNode4(d);
Node source(s);
Node dest(d);
source.Display();
dest.Display();
Search search(&source);
search.Find( & dest);
search.DisplayRoute();
}
void test_search2level()
{
std::vector
CreateNode1(s);
std::vector
CreateNode8(d);
Node source(s);
Node dest(d);
source.Display();
dest.Display();
Search search(&source);
search.Find( & dest);
search.DisplayRoute();
}
八数码问题求解--实验报告讲解
实验报告 一、实验问题 八数码问题求解 二、实验软件 VC6.0 编程语言或其它编程语言 三、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 四、实验数据及步骤 （一、）实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始状态(b) 目标状态 图1 八数码问题示意图 （二、）基本数据结构分析和实现 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{
int digit[ROW][COL]; int dist; // distance between one state and the destination一 个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成： (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down, index);//向下扩展的节点 int dist_down = MAXDISTANCE; (3)将当前状态的空格左移 Node node_left; Assign(node_left, index);//向左扩展的节点 int dist_left = MAXDISTANCE; (4)将当前状态的空格右移 Node node_right; Assign(node_right, index);//向右扩展的节点 int dist_right = MAXDISTANCE; 通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。 3.图的搜索策略 经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。 （三、）广度(宽度)优先搜索原理 1. 状态空间盲目搜索——宽度优先搜索 其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。
用A算法解决八数码问题演示教学
用A算法解决八数码 问题
用A*算法解决八数码问题 一、 题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个 棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态：任何状态都可以被指定为初始状态。 操作符：用来产生4个行动（上下左右移动）。 目标测试：用来检测状态是否能匹配上图的目标布局。 路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对 于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价 值，即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--； 这样估价函数f 在g 值一定的情况下，会或多或少的受估价值h 的制 约，节点距目标点近，h 值小，f 值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。
A star算法在静态路网中的应用 2.算法伪代码 创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 )
昆明理工大学电机学实验报告..
昆明理工大学实验报告 实验课程名称： 电机学实验 开课实验室： 电机实验室 2013年7月5日 年级、专业、班 电自11级 3 班 学号 201110901141 姓名 刘盼 成绩 实验项目名称 电机综合实验 指导教师 教 师 评 语 教师签名 2013年 7 月 5 日 实验一、变压器综合实验 三相变压器并联运行 一、 实验目的 1.学习三相变压器投入并联运行的方法。 2.测试三相变压器并联运行条件不满足时的空载电流。 3.研究三相变压器并联运行时负载的分配规律。 二、 实验原理 理想的并联运行的变压器应满足以下条件： 1、空载时，各变压器的相应的次级电压必须相等而且同相位。为满足此条件，并联个变压器应有相同电压变比：即k1=k2=k3…kn 且属于相同的连接组，不同连接组别的变压器不能并联运行。 2、在有负载时，各变压器的所分担的负载电流英语他们的容量成正比。为满足此条件，保证各个变压器所分担的负载电流与其容量成正比例，各变压器应该有相同的短路电压标幺值。 3、各变压器的负载电流都应同相位。为满足此条件，要求各变压器短路电阻与短路电抗的比值相等。即要求阻抗电压降的有功分量和无功分量分别相等，即各个变压器应该有相同的短路电压有功分量和无功分量。 4．变压器并联运行时的负载分配 。当变压器并联运行时，通常短路电压标幺值随着容量的不同而不相同，大容量的变压器有较大的短路电压。各个并联运行的变压器实际分担负载的计算公式： 由此可见，各个变压器的负载分配与该变压器的额定容量成正比，与短路电压成反比。如果各个变压器的短路电压相同，则变压器的负载分配只与额定容量成正比。
三、实验线路 图A－1 实验线路 四、实验结果及分析 1、测试两台三相变压器满足理想条件并联运行时的空载电流实验参数： 图A－2 实验参数设置Ⅰ
八数码问题人工智能实验报告
基于人工智能的状态空间搜索策略研究 ——八数码问题求解 （一）实验软件 TC2.0 或VC6.0编程语言或其它编程语言 （二）实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 （三）需要的预备知识 1. 熟悉TC 2.0或VC6.0 编程语言或者其它编程语言； 2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法； 3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用； 4. 熟悉计算机常用人机接口设计。 （四）实验数据及步骤 1. 实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 图1 八数码问题示意图 请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A 算法或A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。 2. 实验步骤 （1）分析算法基本原理和基本流程； 程序采用宽度优先搜索算法，基本流程如下：
（2）确定对问题描述的基本数据结构，如Open表和Closed表等；
（3）编写算符运算、目标比较等函数； （4）编写输入、输出接口； （5）全部模块联调； （6）撰写实验报告。 （五）实验报告要求 所撰写的实验报告必须包含以下内容： 1. 算法基本原理和流程框图； 2. 基本数据结构分析和实现； 3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等； 4. 程序运行结果，含使用的搜索算法及搜索路径等； 5. 实验结果分析； 6. 结论； 7. 提供全部源程序及软件的可执行程序。 附：实验报告格式 一、实验问题 二、实验目的 三、实验原理 四、程序框图 五、实验结果及分析 六、结论
A星算法求八数码问题试验报告
人工智能实验报告实验名称：八数码问题 姓名：xx 学号：2012210xx xx计算机学院
2014年1月14日 一．实验目的． 的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一掌握A* 个状态转为另状态的路径。 二．实验内容且要求在有限步的操作内，使其转化为目标状态，给定九宫 格的初始状态，并打印出求解路径。例如(即移动的步数最少)所得到的解是代 价最小解 3 8 2 4 6 1 5 0 7 3 2 8 4 6 1 5 0 7 A*三、算法思想：1、思想：估价值与实际A*算法是一种静态路网中求 解最短路最有效的直接搜索方法。值越接近，估价函数取得就越好、原理：2 f(n)=g(n)+h(n), 估价函数公式表示为：是在状态空g(n) 是从初始点经由节点n到目标点的估价函数，其中 f(n) 到目标节点最佳路径的估计nh(n) 是从间中从初始节点到n节点的实际代价，h(n)的选取：代价。保证找到最短路径（最优解的）条件，关键在于估价函数到目标节点的距离实际值，这种情况下，搜索的点数多，搜索估价值h(n)<= n等于h(n)范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计如
果估那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。最短距离， ,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。价值>实际值 四、算法流程：
1、使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。 关键代码： bool CreateChild(NOExtend ns[],NOExtend ne){
昆明理工大学进程管理实验报告
昆明理工大学信息工程与自动化学院学生实验报告 （2010 —2011 学年第二学期） 课程名称：操作系统开课实验室：年月日 目录 一、实验目的 (1) 二、实验原理及基本技术路线图 (1) 1. 进程的状态转换图 (2) 2. 各原语的功能说明 (2) 3.多级反馈队列调度算法的描述 (3) 4. 程序功能结构图 (4) 5. 流程图 (4) 6. 数据结构定义 (5) 7. 主要变量的说明 (6) 8. 函数的说明 (6) 四、实验方法、步骤 (6) 五、实验过程原始记录 (18) 六、实验结果、分析和结论 (21) 一、实验目的 通过编写进程管理的算法，要求学生掌握整个进程管理的各个环节，进程的数据结构描述，进程的各种状态之间的转换，以及进程的调度算法。以加深对进程的概念及进程调度算法的理解，并且提高链表的应用能力，达到提高编程能力的目的。 二、实验原理及基本技术路线图（方框原理图） 用C语言或C++语言开发。需要定义PCB的数据结构，用链表的形式管理进程，采用
多级反馈队列调度的算法模拟进程的控制。要求有创建、撤销、调度、阻塞、唤醒进程等功能。 1.进程的状态转换图： 2.各原语的功能说明: -进程创建原语：进程创建是调用创建原语来实现。创建原语扫描系统的PCB链表，在找到一定PCB 链表之后，填入调用者提供的有关参数（这些参数包括：进程名、进程优先级P0、进程正文段起始地址d0、资源清单R0等），最后形成代表进程的PCB结构。 -进程撤销（终止）: 撤消原语首先检查PCB进程链或进程家族，寻找所要撤消的进程是否存在。如果找到了所要撤消的进程的PCB结构，则撤消原语释放该进程所占有的资源之后，把对应的PCB结构从进程链或进程家族中摘下并返回给PCB空队列。如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的PCB结构并释放子进程所占用的资源之后，再撤消当前进程的PCB结构和释放其资源。
八数码问题C语言A星算法详细实验报告含代码
一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： [ (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或 A* 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； % 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n) 这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数： f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已
知的。用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下： & 1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。 2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。 4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。 5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。 四、程序框图
C语言实现8数码问题
1、实验目的 (1)熟悉人工智能系统中的问题求解过程； (2)熟悉状态空间中的盲目搜索策略； (3)掌握盲目搜索算法，重点是宽度优先搜索和深度优先搜索算法。 2、实验要求 用VC语言编程，采用宽度优先搜索和深度优先搜索方法，求解8数码问题3、实验内容 （1）采用宽度优先算法，运行程序，要求输入初始状态 假设给定如下初始状态S0 2 8 3 1 6 4 7 0 5 和目标状态Sg 2 1 6 4 0 8 7 5 3 验证程序的输出结果，写出心得体会。 （2）对代码进行修改（选作），实现深度优先搜索求解该问题
提示：每次选扩展节点时，从数组的最后一个生成的节点开始找，找一个没有被扩展的节点。这样也需要对节点添加一个是否被扩展过的标志。 4 源代码及实验结果截图 #include
//------------------------------------------------------------------------ //添加节点函数入口，方法：通过插入排序向指定表添加 //------------------------------------------------------------------------ void Add_Node( struct Node *head, struct Node *p) { struct Node *q; if(head->next)//考虑链表为空 { q = head->next; if(p->f < head->next->f){//考虑插入的节点值比链表的第一个节点值小 p->next = head->next; head->next = p; } else { while(q->next)//考虑插入节点x，形如a<= x <=b { if((q->f < p->f ||q->f == p->f) && (q->next->f > p->f || q->next->f == p->f)){ p->next = q->next; q->next = p; break; } q = q->next; } if(q->next == NULL) //考虑插入的节点值比链表最后一个元素的值更大 q->next = p; }
昆明理工大学进程管理实验报告
理工大学信息工程与自动化学院学生实验报告 （ 2010—2011学年第二学期） 课程名称：操作系统开课实验室：年月日 目录 一、实验目的1 二、实验原理及基本技术路线图1 1.进程的状态转换图2 2.各原语的功能说明2 3.多级反馈队列调度算法的描述3 4.程序功能结构图4 5.流程图4 6.数据结构定义5 7.主要变量的说明6 8.函数的说明6 四、实验方法、步骤6 五、实验过程原始记录18 六、实验结果、分析和结论21 一、实验目的 通过编写进程管理的算法，要求学生掌握整个进程管理的各个环节，进程的数据结构描述，进程的各种状态之间的转换，以及进程的调度算法。以加深对进程的概念及进程调度算法的理解，并且提高链表的应用能力，达到提高编程能力的目的。 二、实验原理及基本技术路线图（方框原理图） 用C语言或C++语言开发。需要定义PCB的数据结构，用链表的形式管理进程，采用多
级反馈队列调度的算法模拟进程的控制。要求有创建、撤销、调度、阻塞、唤醒进程等功能。 1.进程的状态转换图： 2.各原语的功能说明: -进程创建原语：进程创建是调用创建原语来实现。创建原语扫描系统的PCB链表，在找到一定PCB 链表之后，填入调用者提供的有关参数（这些参数包括：进程名、进程优先级P0、进程正文段起始地址d0、资源清单R0等），最后形成代表进程的PCB结构。 -进程撤销（终止）: 撤消原语首先检查PCB进程链或进程家族，寻找所要撤消的进程是否存在。如果找到了所要撤消的进程的PCB结构，则撤消原语释放该进程所占有的资源之后，把对应的PCB结构从进程链或进程家族中摘下并返回给PCB空队列。如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的PCB结构并释放子进程所占用的资源之后，再撤消当前进程的PCB结构和释放其资源。 -阻塞原语：当发生引起阻塞的事件时，该原语被该进程自己调用来阻塞自己。阻塞
八数码问题C语言A星算法详细实验报告含代码
八数码问题C语言A星算法详细实验报告含代 码 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或 A* 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数： f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f'(n)的近似，也就是用g(n)代替 g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费 h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下： 1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。
启发式搜索算法解决八数码问题(C语言)
1、程序源代码 #include
A星算法求八数码问题实验报告
人工智能实验报告 实验名称：八数码问题 姓名：xx 学号：2012210xx xx计算机学院 2014年1月14日
一．实验目的 掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。 二．实验内容 给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 7 0 5 三、A*算法思想： 1、思想： A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好 2、原理： 估价函数公式表示为： f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
四、算法流程： 是 是，输出路径 否，生成n 的所有子状态 Heuristic_Search(启发式搜索) While （未拓展表不为空？） 从未拓展表中删除第一个状态n N 为目标状态？ Case:此子状态 不在拓展表和 未拓展表中 Case:此子状态在未拓展表中 Case:此子状态在拓展表 计算该子状态的估价函数值； 记录比已有的路径更短 的路径 记录比已有的路径更短的路径 返回
用盲目搜索技术解决八数码问题
. 用盲目搜索技术解决八数码问题 题目 在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上 标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 算法流程 使用宽度优先搜索 从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜 索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面， 后进入的节点排在后面。 宽度优先算法如下： 把初始结点S0放入OPEN表中 若OPEN表为空，则搜索失败，问题无解 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 若目标结点，则搜索成功，问题有解N?Sg若N无子结点，则转2 扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转2 源程序 #include
using namespace std; const int ROW = 3;//行数 const int COL = 3;//列数 const int MAXDISTANCE = 10000;//最多可以有的表的数目const int MAXNUM = 10000; typedef struct _Node{ int digit[ROW][COL]; int dist;//distance between one state and the destination 一个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置} Node; Node src, dest;// 父节表目的表 vector
昆明理工大学数据库实验报告
《数据库原理》上机实验报告 专业：自动化、测控 学号： 姓名： 班级： 指导老师：杨彪 昆明理工大学信息工程与自动化学院 2014年12月
一、实验目的与要求： ●熟练使用SQL定义子语言、操纵子语言命令语句 ●掌握关系模型上的完整性约束机制 ●掌握一定的数据库管理技术 ●能完成简单的数据库应用开发 二、实验内容及学时安排（总学时：8） （一）数据定义子语言实验（2学时） 实验1：利用SQL语句创建Employee数据库 程序：create database employee 结果： 实验2：利用SQL语句在Employee数据库中创建人员表person、月薪表salary 及部门表dept。 要求：按表1、表达、表3中的字段说明创建 表1 person表结构 字段名数据类型字段长度允许空否字段说明 P_no Char 6 Not Null 工号，主键 P_name Varchar 10 Not Null 姓名 Sex Char 2 Not Null 性别 Birthdate Datetime 8 Null 出生日期 Prof Varchar 10 Null 职称 Deptno Char 4 Not Null 部门代码，外键（参照dept表） 表2 salary表结构 字段名数据类型字段长度允许空否字段说明 P_no Char 6 Not Null 工号，主键，外键（参照person表）Base Dec 5 Null 基本工资 Bonus Dec 5 Null 奖金，要求>50 Fact Dec 5 Null 实发工资=基本工资+奖金Month Int 2 Not Null 月份 表3 dept表结构 字段名数据类型字段长度允许空否字段说明 Deptno Char 4 Not Null 部门代码，主键，
八数码问题实验报告讲解
《八数码问题》实验报告 一、实验目的： 熟练掌握启发式搜索A *算法。 二、实验内容： 使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 三、实验原理： 1. 问题描述： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述： 启发式搜索 （1）原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 （2）估价函数
计算一个节点的估价函数，可以分成两个部分： 1、 已经付出的代价（起始节点到当前节点）； 2、 将要付出的代价（当前节点到目标节点）。 节点n 的估价函数)(n f 定义为从初始节点、经过n 、到达目标节点的路径的最小代价 的估计值，即)(* n f = )(* n g + )(* n h 。 )(*n g 是从初始节点到达当前节点n 的实际代价； )(*n h 是从节点n 到目标节点的最佳路径的估计代价。 )(*n g 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，)(*n h 的比重越大， 表示启发性能就越强。 （3）算法描述： ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。 （3）算法流程图：
启发式搜索 八数码问题
启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ，A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度，深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。
八数码问题报告
八数码问题分析 班级：计算机1041 学号：01 姓名：李守先 2013年9月26日
摘要 八数码问题（Eight-puzzle Problem ）是人工智能中一个很典型的智力问题。 本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java 算法与实现的思想, 分析了A*算法的可采纳性等及系统的特点。 关键词 九宫重排, 状态空间, 启发式搜索, A*算法 1 引言 九宫重排问题（即八数码问题）是人工智能当中有名的难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。状态转换的规则：空格周围的数移向空格,我们可以看作是空格移动,它最多可以有４个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。 图1 许多学者对该问题进行了有益的探索[1,2,4,6]。给定初始状态,9个数在3×3中的放法共有９！＝362880种,其状态空间是相当大的。因此, 有必要考虑与问题相关的启发性信息来指导搜索,以提高搜索的效率。当然,还有个很重要的问题：每个初始状态都存在解路径吗？文献给出了九宫重排问题是否有解的判别方法：九宫重排问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义把三行数展开排成一行,并且丢弃数字 0 不计入其中,ηi 是第 i 个数之前比该数小的数字的个数,则 η=Σηi 是该状态的逆序数,图2说明了逆序数计算的过程 。 本文介绍用JAVA 编写九宫重排问题游戏。游戏规则是,可随机产生或由用户设置初始状态,由初始状态出发,不断地在空格上下左右的数码移至空格,若能排出目标状态,则成功。为了避免对无解节点进行无用搜索,首先对初始节点进行逆序数分析,对有解的节点进行搜索,从而节省了资源,也提高了效率。本文内容安排: 第2部分介绍几个相关的概念和A*算法以及可采纳性 ;
昆明理工大学机电系统设计模块PLC实验报告
三、验证型实验 1、电动机Y/△降压起动控制 （1）工作原理 按下启动按钮SB１，KM1、KM３、时间继电器通电并自保,电动机接成Y 型起动，2ｓ后,时间继电器动作,使KM3断电,KM2通电吸合，电动机接成△型运行。按下停止按扭ＳB1,电动机停止运行。 图1电动机Ｙ/△减压起动控制主电路 (２）Ｉ／Ｏ分配 输入元件分配地址输出元件分配地址 停止按钮SB1 I０.０KＭ1 Q0.0 启动按钮SB2 Ｉ0.1 KM2 Q0.1 过载保护FR I0.2 KM３Ｑ0.２ (3）梯形图
图2梯形图程序 (3）程序说明 按下启动按钮SB2,触点I0.1闭合内部辅助线圈M0.0通电 常开触点M0.０闭合,形成自锁 常开触点M0．0闭合,线圈Q0．0通电 常开触点Ｍ0．０闭合,线圈Q0．2通电，定时器T38通电开始计时 常闭触点Q0.2断开，形成互锁
2s后,T３８断开,Ｑ0.2断电;T38闭合,Q0.1通电并自锁(4)语句表 图３语句表程序 (5）仿真结果 图4 状态表
图５工程图 2、用PLC构成交通灯控制系统 （1）控制要求 如图所示，起动后,南北红灯亮并维持2５ｓ。在南北红灯亮的同时，东西绿灯也亮,１s后,东西车灯即甲亮。到20s时，东西绿灯闪亮，３s后熄灭，在东西绿灯熄灭后东西黄灯亮，同时甲灭。黄灯亮2ｓ后灭东西红灯亮。与此同时,南北红灯灭，南北绿灯亮。1s后，南北车灯即乙亮。南北绿灯亮了25s后闪亮，3s 后熄灭，同时乙灭，黄灯亮2ｓ后熄灭,南北红灯亮,东西绿灯亮,循环。
图6 十字路口交通灯 (2)Ｉ/O分配 输入元件分配地址输出元件分配地址启动按钮I0.0 南北红灯Ｑ０.０ 南北黄灯Q0.1 南北绿灯Q0.2 东西红灯Ｑ０.3 东西黄灯Ｑ0．４ 东西绿灯Q0.5 南北车灯Q０.６ 东西车灯Q０.７(3)程序设计 起动I0.0 东西绿灯Q0.5 东西车灯甲Q0.7 东西黄灯Q0.4 东西红灯Q0.3 南北绿灯Q0.2 南北车灯乙Q0.6 南北黄灯Q0.1 南北红灯Q0.0 图7十字路口交通信号灯的时序图
昆明理工大学计算机实验报告
昆明理工大学《程序设计语言（Java）》课程实验报告 学院名称：材料科学与工程专业年级： 学生姓名：学号： 联系电话：Email: 实验项目名称：Java基础实验指导教师王樱子 实验目的： 1. 掌握Java程序的编辑、编译、调试和运行方法，熟悉常见编程工具的使用； 2. 掌握if语句，switch语句，for语句，while语句和do…while语句的用法； 3. 掌握一维数组和二维数组的使用方法。 实验内容： 1. 编译两种运行方式：just-in-time编译器，简称JIT编译器。多线程，动态执行，丰富的API文档和类库。 采用UltraEdit为编程工具，对教材例1-1的程序进行编辑、编译和运行。熟悉JDK API 文档的使用方法。 2. if语句，是单重选择，最多只有两个分支。if关键字之后的逻辑表达式必须得到一个逻辑值，不能象其他语言那样以数值来代替。因为Java不提供数值与逻辑值之间的转换。else子句属于逻辑上离它最近的if语句。 switch语句含义与嵌套的if语句是类似的，格式更加简捷。表达式的计算结果必须是int型或字符型，即是int型赋值相容的。当用byte、short或char类型时，要进行提升。switch语句不允许使用浮点型或long型表达式。c1、c2、…、ck是int型或字符型常量。default子句是可选的，并且，最后一个break语句完全可以不写。switch语句和if语句可以互相代替。当主程序执行时，如果第一个命令行参数的首字符分别是数字、小写字母及大写字母时，系统会显示这个首字符。如果输入的是非数字或字母，则显示不是数字或字母。 三种循环语句：for语句、while语句和do语句 for语句的语义是：先执行初始语句，判断逻辑表达式的值，当逻辑表达式为真时，执行循环体语句，执行迭代语句，然后再去判别逻辑表达式的值。直到逻辑表达式的值为假时，循环结束。 while循环 for语句中常常用循环控制变量显式控制循环的执行次数。当程序中不能明确地指明循环的执行次数时，可以仅用逻辑表达式来决定循环的执行与否。这样的循环可用while语句来实现
- 昆明理工大学关于印发学分制管理文件的通知 .doc
- 昆明理工大学研究生国家奖学金评选及管理办法(试行)【模板】
- 6、科研项目分类
- 昆明理工大学关于印发双专业双学位教育管理办法的通知
- 大学生创新创业训练计划项目管理办法
- 昆明理工大学教师专业技术职务评审条件
- 大学科技计划(专项)项目经费管理实施细则
- 1、昆明理工大学教师高级职务破格推荐评审条件(昆理工大校人字〔2014〕28号)
- 大学关于印发学科方向团队建设计划设施办法
- 公务卡管理办法
- 昆明理工大学关于2015年学校推免名额下达的通知(学院)
- 科研项目分类
- 重修报名及选课通知
- 昆明理工大学优秀科技成果培育实施办法
- 6、科研项目分类
- 昆明理工大学学分制管理系列文件
- 科研项目分类
- 昆明理工大学研究生省政府奖学金评选及管理办法(试行)
- 昆明理工大学研究生学业奖学金评选及管理办法(试行)
- 大学印发学科方向团队建设计划设施办法