人工智能实验报告

实验名称：模糊方法实现电热箱的闭环控制实验

    模糊逻辑控制(Fuzzy Logic Control)简称模糊控制(Fuzzy Control)，是以模糊集合论、模糊语言变量和模糊逻辑推理为基础的一种计算机数字控制技术。1965年，美国的L.A.Zadeh创立了模糊集合论；1973年他给出了模糊逻辑控制的定义和相关的定理。1974年，英国的E.H.Mamdani首先用模糊控制语句组成模糊控制器，并把它应用于锅炉和蒸汽机的控制，在实验室获得成功。这一开拓性的工作标志着模糊控制论的诞生。
    模糊控制实质上是一种非线性控制，从属于智能控制的范畴。模糊控制的一大特点是既具有系统化的理论，又有着大量实际应用背景。模糊控制的发展最初在西方遇到了较大的阻力；然而在东方尤其是在日本，却得到了迅速而广泛的推广应用。近20多年来，模糊控制不论从理论上还是技术上都有了长足的进步，成为自动控制领域中一个非常活跃而又硕果累累的分支。其典型应用的例子涉及生产和生活的许多方面，例如在家用电器设备中有模糊洗衣机、空调、微波炉、吸尘器、照相机和摄录机等；在工业控制领域中有水净化处理、发酵过程、化学反应釜、水泥窑炉等的模糊控制；在专用系统和其它方面有地铁靠站停车、汽车驾驶、电梯、自动扶梯、蒸汽引擎以及机器人的模糊控制等。       

     模糊控制是以模糊集合论、模糊语言变量和模糊逻辑推理为基础的微机数字控制。它能模拟人的思维,构成一种非线性控制,以满足复杂的、不确定的过程控制的需要,是一种典型的智能控制。    模糊控制系统类似于常规的微机控制系统,如下图所示:

图1 模糊控制系统的构成图

一、实验目的

    1. 学习由已知对象建立一个双入单出模糊控制器;
    2. 掌握利用模糊控制器实现温度控制的方法。

二、实验原理及内容

    模糊控制器最常用的都是二维的,其输入变量有两个(X1,X2),输出变量只有一个(Y)。在实际控制系统中,X1一般取为误差信号,X2一般取误差的变化,由于同时考虑到误差和误差变化的影响,所以才能保证系统稳定,不致于产生振荡。模糊控制系统的方框图如下图所示:

图2 模糊控制系统结构框图

      图中,E为实际误差,EC为实际误差变化,U为控制量。下面就以电热箱为控制对象,介绍双入单出模糊控制器的设计。
     1. 模糊控制器设计
      (1) 模糊化
      误差E∈[-30℃,230℃],且L＝7,误差的比例因子α=7/230,这样就有E=α·E。采用就近取整原则,得E的论域为:X={-1,0,+1,+2,+3,+4,+5}。
      而误差的语言变量在论域X中有7个语言值,即:

          含义: 正大大大 正大大 正大 正中 正小 零 负小

          符号:   PBBB    PBB    PB   PM   PS  ZO  NS
      误差变化EC∈[0℃,9℃],且L＝6,误差的比例因子β=6/9,这样就有EC=β·EC。同样得到EC的论域为:EC={0,+1,+2,+3,+4,+5}。
          符号: ZO  PS  PM  PB  PB  PBBB
      输出量U的基本论域为:U={7fH,66H,4dH,34H,19H,00H}。
          符号: ZO  PS  PM  PB  PB  PBBB
      (2) 模糊控制表

表1 模糊控制系统结构框图

      为便于控制,使系统在微机实时控制中在线运行,可事先对各种误差和误差变化用微机离线计算好一个控制表,如上表所示。按测量输入的误差(E)和误差变化(EC),查模糊控制表就可输出控制量(U),完成控制温度的任务。模糊控制器里的模糊控制规则表是基于手动操作经验来建立的,而另一个与模糊控制表有关的还有模糊化接口和清晰化接口,也即误差(E)、误差变化(EC)、控制量(U)三个变量的论域的设定。这些都需要通过不断的做实验,从实验中找到反馈值和控制量之间的关系和规律,才能找到比较合适的论域。
    2. 模糊控制器实验线路图设计
    参照图2的模糊控制系统框图,设计如下图所示的实验线路图:

图3 模糊控制器实验线路图

    以8088控制机中的8255 PB0口输出的PWM脉冲信号为控制量,经驱动电路驱动固态继电器的吸合使电烤箱加热。温度测量使用了10K热敏电阻,经A/D转换构成反馈量,在参数给定的情况下,经双入单出模糊控制器,由误差(E)、误差变化(EC)查找模糊控制规则表得到相应的控制量,使烤箱温度稳定在给定值。其中OPKLK为1.1625MHz时钟信号,经8253的2号通道分频输出10ms的方波,一方面作为A/D的定时启动信号,一方面接入8259产生IRQ6中断,作为系统采样时钟。
    3. 模糊控制器的实现
    下图是模糊控制器实现的参考程序流程图:

图4 参考程序流程图

    主程序主要完成系统初始化、查表并输出控制量等功能;IRQ7中断子程序是为了处理A/D转换完后产生的中断;IRQ6中断子程序是为了给采样周期计时,并且每一次中断产生一次PWM脉冲。

三、实验设备

1. 电热箱一台;

2. PC机一台,TD-ACC系列教学实验系统一套。

四、实验步骤

    1. 参考流程图编写程序,汇编、链接、装载;
    2. 按照图3接线,检查接线无误后,运行程序;
    3. 用系统提供的专用图形显示窗口观察响应曲线,记录超调和过渡时间。

五．实验图表

六、实验分析

模糊控制器的设计内容

1.选择模糊控制器的设计内容与原则

一般选取误差信号E（或e）和误差变化信号EC(或ec)作为模糊控制器的输入变量，而把受控变量的变化y作为输出变量。

2.选取模糊控制的规则

（1）选择描述控制器输入和输出变量的语义词汇。

（2）规定模糊集。

（3）确定模糊控制状态表。

3.确定模糊化的解模糊策略，制定控制表。

在求得误差和误差变化的模糊集E和EC之后，控制量的模糊集U可由模糊推理综合算法获得：

U=E×EC°R

式中：R为模糊关系矩阵。控制量的模糊集U可被变换为精确值。

4.确定模糊控制器的参数

    模糊控制的基本思想是利用计算机来实现人的控制经验，而这些经验多是用语言表达的具有相当模糊性的控制规则。模糊控制器(Fuzzy Controller，即FC)获得巨大成功的主要原因在于它具有如下一些突出特点：
 
   模糊控制是一种基于规则的控制。它直接采用语言型控制规则，出发点是现场操作人员的控制经验或相关专家的知识，在设计中不需要建立被控对象的精确数学模型，因而使得控制机理和策略易于接受与理解，设计简单，便于应用。
   由工业过程的定性认识出发，比较容易建立语言控制规则，因而模糊控制对那些数学模型难以获取、动态特性不易掌握或变化非常显著的对象非常适用。
   基于模型的控制算法及系统设计方法，由于出发点和性能指标的不同，容易导致较大差异；但一个系统的语言控制规则却具有相对的独立性，利用这些控制规律间的模糊连接，容易找到折中的选择，使控制效果优于常规控制器。
   模糊控制算法是基于启发性的知识及语言决策规则设计的，这有利于模拟人工控制的过程和方法，增强控制系统的适应能力，使之具有一定的智能水平。
   模糊控制系统的鲁棒性强，干扰和参数变化对控制效果的影响被大大减弱，尤其适合于非线性、时变及纯滞后系统的控制

七、实验结论

      本次实验是在室温环境下进行的,其中电烤箱预设温度为100ºC(64H),起始温度为室温。根据实验现象可以看出,模糊控制在控制大滞后系统时比常规PID控制的效果要好。一个方面是被控对象是一个大滞后系统,所以在控制量发生改变时,被控对象不能立即表现出来,它要经过一段时间才能对上一个控制量作出反应;另一个方面常规PID的控制是一种线性控制,在PID算法中,它的积分项是一个误差累加值,当系统误差为零或为负值时,虽然积分项的值开始下降,但在误差为正值时,积分项可能已经累加到了一个很大的值,这使得积分项的值不能很快地减下来,因而在控制上就出现了惯性,因此当误差为零或为负值时,控制量不可能很快为零或为负值,系统则出现了超调和调整时间过长。当积分项累加值大过一定值时,系统则还会出现积分饱和现象,系统将振荡下去而不稳定。
      模糊控制是模拟人的思维,是一种非线性控制,它的输出量是阶跃的,因而在控制方面不存在惯性和滞后问题。因为没有误差的累加,模糊控制系统也就不会出现积分饱和现象。       

   

实验名称：  单神经元自适应闭环控制实验

     所谓神经网络控制，即基于神经网络控制或简称神经控制，是指砸控制系统中采用神经网络这一工具对难以精确描述的复杂的非线性对象进行建模，或充当控制器，或优化计算，或进行推理，或故障诊断等，遗迹同时兼有上述某些功能的适应组合，将这样的系统统称为神经网络的控制系统，将这种控制方式称为神经网络控制。

神经网络是由众多的神经元采用某种网络拓扑结构构成的,可以用来描述几乎任意的非线性系统,而且神经网络还具有自学习、自适应和并行分布处理等特点,在控制领域有着广阔的应用前景。单神经元作为神经网络的最基本单元,具有自学习、自适应能力,而且由单神经元构成的控制器结构简单,易于实时控制,因此其应用非常广泛。

一、实验目的

    1. 掌握单神经元控制器的设计方法;
         2. 观测单神经元控制器对时变对象系统的自适应控制能力。

二、实验原理及内容

      1. 单神经元的数学模型
      单神经元的数学模型由三部分组成:加权加法器、线性动态系统和非线性函数,如下图所示。Xi是神经元的输入,Wi是加权系数(或连接强度),Vi是加权加法器的输出,U是单神经元的输出。

图1 单神经元的数学模型

    神经元的学习过程就是为了获得期望的输出而不断地调整权值,权值的修正采用学习规则。
    2. 单神经元控制器设计
    图2是一个典型的单神经元控制器方框图:

图2 单神经元控制器结构图

    3. 实验线路图设计
    根据图2所示的单神经元控制器方框图,实验电路原理图及接线图可设计为:

图3 单神经元实验线路图

      这里,系统误差信号E通过A/D转换单元IN7端输入,计算机用8253定时器2来作为基准时钟(初始化为10ms),定时采集IN7端的信号,并通过8259的IRQ7中断8088控制机的运行,从8255A口读入信号E的数字量,并将采样值进行计算,分别求得X1、X2、X3并进行自适应算法学习,把得到的控制量直接送到D/A转换单元,在OUT端输出相应的模拟信号,控制对象系统。

   4. 参考流程图设计
        参照单神经元控制器线路原理图(图3),程序的参考流程图如下:

图4 单神经元程序参考流程图

    参考程序中规定采样周期T及学习速率P1,P2,P3的取值范围为:

    控制器中的参数可遵循如下的调节规律:
      (1) 初始加权系数W1(0)、W2(0)、W3(0)可以任意选取,参考程序中全部取为0100H;
      (2) 一般K值偏大将使系统响应超调过大,K值偏小使过渡过程时间加长,参考程序中K值取为1;
      (3) 学习速率的选择:由于采用了规范化学习算法,学习速率可以取得较大,同时此神经元控制器具有PID特性,学习速率的选择和PID参数的选择相似。若过渡过程时间太长,可增加η1和η3,若响应曲线下降低于给定值后又缓慢上升到稳态的时间太长,则减小η1。

三、实验设备

    PC机一台,TD-ACC系列教学实验系统一套。

四、实验步骤

 1. 单神经元闭环控制器实验
      (1). 参考流程图编写单神经元控制器程序,汇编、链接、装载到控制机中;
      (2). 按照实验线路图接线,调节信号源使其输出幅值为2V,周期6S的方波;
      (3). 检查无误后运行程序,用示波器观察输入端R和输出端C。若系统性能不太好,根据实验现象改变相应的学习速率直到满意为止,并记下此时的响应曲线;
      (4). 当响应曲线稳定后,断开“ST”和“S”端,使被控对象处于不锁零的状态;此时去掉被控对象中的10μF的电容(改变对象的时间常数),观察并记录此时的响应曲线。
    2. 常规数字PID闭环控制器实验
      (1). 编写数字PID控制器程序,汇编、链接、装载到控制机中;
      (2). (2) 按照单神经元闭环控制器实验步骤2～4进行操作。
    参考程序中部分参数取值范围:

五、实验图表

1.

2.断开“ST”和“S”端，使被控对象处于不锁零的状态。

3.去掉被控对象的10uf的电容（改变对象的时间常数）。

六、人工神经网络的特性：

（1）并行分布处理

（2）非线性映射

（3）通过训练进行学习

（4）适应与集成

（5）硬件实现

神经控制器的设计

(1)建立受控对象的数学计算模型或知识表示模型

(2)选择神经网络及其算法，进行初步辨识与训练

(3)设计深井控制器，包括控制器结构、功能表示与推理

(4)控制系统仿真实验，并通过试验结果改进设计

神经网络在控制中的作用分为以下几种：
　　1.在基于精度模型的各种控制结构中充当对象的模型。
　　2.在反馈控制系统中直接充当控制器的作用。
　　3.在传统控制系统中起优化计算的作用。
　　4.在与其他智能控制方法和优化算法，如模糊控制/专家考证及遗传算法等相融合中，为其提供非参数化对象模型、优化参数、推理模型及故障诊断等。

七、结论

    从实验结果可以看出:在系统开始阶段,数字PID控制的响应曲线超调和调节时间较小,这是由于数字PID控制器的参数是经过反复实验调试的结果,而单神经元控制器的参数需要一定的时间进行自学习。当对象时间常数发生变化后,尤其是较大的时常改变(例如实验中去掉10μF的电容),数字PID控制器的参数已经不能适应对象的改变,此时出现了系统不稳定现象。单神经元控制器实质上是一个变系数的PID复合控制器,而且学习算法是自适应的,所以本质上是非线性的;当被控对象由于外部条件而发生变化时,单神经元控制器可以通过自适应学习算法来改变当前的参数,因此它比常规PID控制器具有更好的鲁棒性、自适应性。         

 

第二篇：人工智能实验报告 八数码问题

实验一  启发式搜索算法

姓名：徐维坚学号：2220103484 日期：20##/6/29

一、实验目的：

熟练掌握启发式搜索算法及其可采纳性。

二、实验内容：

使用启发式搜索算法求解8数码问题。

1)        编制程序实现求解8数码问题算法，采用估价函数

，

其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。

2)        分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是的上界

的的定义，并测试使用该估价函数是否使算法失去可采纳性。

三、实验原理：

1.   问题描述：

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2.        原理描述：

2.1 有序搜索算法：

（1）原理：

在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。

在本例中，估价函数中的取节点深度，为节点n的状态与目标状态之间错放的个数，即函数。

（2）算法描述：

①       把起始节点S放到OPEN表中，并计算节点S的；

②       如果OPEN是空表，则失败退出，无解；

③       从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个

为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点；

④       把节点从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中；

⑤       如果是个目标节点，则成功退出，求得一个解；

⑥       扩展节点，生成其全部后继节点。对于的每一个后继节点：

计算；如果 既不在OPEN表中，又不在CLOCED表中，则用估价函数把

它添入OPEN表中。从加一指向其父节点的指针，以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则

(I)以此新值取代旧值。

(II)从指向，而不是指向他的父节点。

(III)如果节点在CLOSED表中，则把它移回OPEN表中。

⑦       转向②，即GOTO②。

（3）算法流程图：

2.2启发式搜索技术

（1）原理

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

（2）估价函数

计算一个节点的估价函数，可以分成两个部分：

1、  已经付出的代价（起始节点到当前节点）；

2、  将要付出的代价（当前节点到目标节点）。

节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即 = + 。

是从初始节点到达当前节点n的实际代价；

是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。

所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。

本实验中我们使用函数，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。

（3）算法描述：

参考有序搜索算法描述，基本相同。流程图亦参考有序算法流程图。

四、实验程序及其说明：

1）int goal[N][N]，struct Chessboard：

试验中我定义goal数组为目标状态——{1,2,3,8,0,4,7,6,5}。结构体Chessboard记录棋盘信息，其中变量pos数组坐标记录每个数码a的位置，其值为数码a。d表示该棋盘的深度，f为启发函数值，move为父节点移动到该节点的方式，以便在输出时告诉用户该如何移动棋子知道目标状态。

2）struct LNode：

定义节点LNode结构体，存放该节点状态时的棋盘信息board，和指向父节点、下一节点的指针(*parent,*next)，以及标记量flag——值为true时表示该节点是最佳路径上的节点。

3）int* Findzero(LNode* &Node)：

为方便找到空格，我设计了找到该函数Findzero(*&Node)，以便找到当前节点空格所在位置以利于接下来的程序执行。返回值为空格所在的行和列。

4）int Wrong(LNode *Node)和int pick(LNode *Node)：

分别为函数和。

5）LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose)

树形方式扩展节点。Node为要扩展的当前节点，depth为当前深度，zero存放该节点空格位置信息，moveflag即扩展节点的移动方式，Choose为选择函数还是。

6）void InitList(LNode* &Open,LNode* &Close)和int ListInsert(List &L,LNode* NewNode)

分别为表OPEN、CLOSE的创建和表的插入操作。

7）LNode* Getminf(List &L)

主要是实现从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中

有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点。

五、实验小结

通过本次试验，我对启发式搜索有了更加深入的了解。

在实验中，通过对两种启发式搜索所扩在的节点数来看，看来比更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数来说，它的定义趋向多元化，只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。

在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指针path来找到路径，这样节省了存储空间，更利于搜索。

通过实验结果来看，这两个函数都是可采纳的，尽管存在不必要的扩展。

六、实验代码及输出结果

1. 源代码：

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#define Overflow 1

#define N 3

int goal[N][N]={1,2,3,8,0,4,7,6,5};

int zero[2],NodeQTY=0;

int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列

typedef int Piece;

struct Chessboard{//棋盘信息

       Piece pos[N][N];//记录每个数码a的位置r行c列

       int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该节点的方式

};

struct LNode{

       Chessboard board;

       LNode *parent,*next;

       bool flag;

};

typedef LNode* List;

int* Findzero(LNode* &Node)

{

       int i,j,zr[2];

       int *z=zr;

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     if(Node->board.pos[i][j]==0){

                            zr[0]=i+1;

                            zr[1]=j+1;

                            break;

                     }

              }

       }

       return z;

}

int Wrong(LNode *Node)

{

       int w=0,i,j;

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0)

                            w++;

              }

       }

       return w;

}

int pick(LNode *Node)

{

       int w=0,i,j,ii,jj;

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0){

                            for(ii=0;ii<N;ii++)

                                   for(jj=0;jj<N;jj++)

                                          if(Node->board.pos[i][j]==goal[ii][jj]){

                                                 w=w+abs(ii-i)+abs(jj-j);

                                                 break;    

                                          }

                     }

              }

       }

       return w;

}

LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose)

{

       LNode* NewNode=new LNode;

       for(int i=0;i<N;i++){

              for(int j=0;j<N;j++){

                     NewNode->board.pos[i][j]=Node->board.pos[i][j];

              }

       }

       switch(moveflag)

       {

              case 1:     //向左移，不能出界：zero[1]>=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[1]-2];

                            NewNode->board.pos[zero[0]-1][zero[1]-2]=0;

                            break;

              case 2:     //向右移，不能出界：zero[1]<=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[1]];

                            NewNode->board.pos[zero[0]-1][zero[1]]=0;

                            break;

              case 3:     //向上移，不能出界：zero[0]>=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-2][zero[1]-1];

                            NewNode->board.pos[zero[0]-2][zero[1]-1]=0;

                            break;

              case 4:     //向下移，不能出界：zero[0]<=2

                            NewNode->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]][zero[1]-1];

                            NewNode->board.pos[zero[0]][zero[1]-1]=0;

                            break;           

       }

       NewNode->board.d=depth+1;

       switch(Choose){

              case 1:NewNode->board.f=NewNode->board.d+Wrong(NewNode);break;

              case 2:NewNode->board.f=NewNode->board.d+pick(NewNode);break;

       }

       NewNode->board.move=moveflag;

       NewNode->parent=Node;

       NodeQTY++;

       return NewNode;

}

void InitList(LNode* &Open,LNode* &Close)

{

       Open=(List)malloc(sizeof(LNode));

       Close=(List)malloc(sizeof(LNode));

       if(!Open&&!Close)

              exit(Overflow);

       Open->next=NULL;

       Close->next=NULL;

}

int ListInsert(List &L,LNode* NewNode)

{

       List p=L;

       while(p->next){

              p=p->next;

       }

       NewNode->next=p->next;

       p->next=NewNode;

       return true;

}

LNode* Getminf(List &L)

{    

       List p=L,q=L->next,r=L,min;

       min=q;//p,q寻找f最小值的指针，r指向表L中min前一个元素

       if(!q)

              return NULL;

       while(q)

       {

              if(min->board.f>q->board.f){

                     r=p;

                     min=q;

              }

              p=q;

              q=q->next;

       }

       r->next=min->next;

       min->next=NULL;

       return min;

}

int main()

{

       int i,j,choose;

       List Open,Close;

       LNode *Best,*current;

       LNode *Start=new LNode;

       printf("\t\t\t八 数 码 问 题 求 解\n");

       printf("\n请输入初始状态：");

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     scanf("%d",&(Start->board.pos[i][j]));

              }

       }

       printf("(注:The flag of movement--1:左移;2:右移;3:上移;4:下移)\n");

       printf("初始棋盘状态：\n");

       for(i=0;i<N;i++){

              for(j=0;j<N;j++){

                     printf("|%d",Start->board.pos[i][j]);

              }

              printf("|\n");

       }

       InitList(Open,Close);

      printf("请选择(1:A算法;2:A*算法):");

      scanf("%d",&choose);  

      Start->board.d=0;

       switch(choose){

              case 1:Start->board.f=Start->board.d+Wrong(Start);break;

              case 2:Start->board.f=Start->board.d+pick(Start);break;

       } //  Start->board.f=0+Wrong(Start);

       Start->board.move=0;

       Start->parent=NULL;

       Start->next=NULL;

       Start->flag=1;

       ListInsert(Open,Start);//将S加入到Open表中

       while(Open->next){

              Best=Getminf(Open);

              ListInsert(Close,Best);

              if(!(Best->board.f-Best->board.d)){

                     printf("$$$******有解！******$$$\n");

                     break;

              }

              z=Findzero(Best);

              zero[0]=*(z+0);zero[1]=*(z+1);

              if(zero[1]>=N-1&&Best->board.move!=2) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,1,choose));

              if(zero[1]<=N-1&&Best->board.move!=1) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,2,choose));

              if(zero[0]>=N-1&&Best->board.move!=4) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,3,choose));

              if(zero[0]<=N-1&&Best->board.move!=3) 

                     ListInsert(Open,extend(Best,Best->board.d,zero,4,choose));

       }

       printf("本算法搜索图中总共扩展的节点数为：%d\n",NodeQTY);

       printf("\t最佳路径如下所示：\n");

       if(Open->next)

       {

              while(Best->parent){

                     Best->flag=1;

                     Best=Best->parent;

              }

              List p=Close->next,q=Close->next;

              if(p==Start) q=p->next;

              else        exit(1);

              int Step=0;

              while(p&&q)//在Close表中依标记找到路径

              {

                     if(q->flag==1&&q->parent==p){

                            printf("Step %d:0 move as

the %d-flag of movement.\n",++Step,q->board.move);

                            for(i=0;i<N;i++){

                                   for(j=0;j<N;j++){

                                          printf("|%d",q->board.pos[i][j]);

                                   }    

                                   printf("|\n");

                            }

                            p=q;//记住父节点

                     }

                     q=q->next;    

              }

              printf("到达目标状态！\n");

       }

       else  printf("该问题无法求解！\n");

}

2. 输出结果：

2.1 A算法：

2.2 A*算法：