人工智能实验一梵塔问题实验

华清学院软件工程专业人工智能实验指导书西安建筑科技大学信控学院目录第1章课程简介，实验项目及学时安排 (1)第2章实验设备简介 (2)第3章人工智能课程实验 (47)实验一熟悉Visual Prolog 软件开发平台 (47)实验二使用Visual Prolog求解Fibonacci序列问题 (49)实验三使用Visual Prolog求解梵塔问题 (50)实验四使用Visual Prolog求解装错信封问题 (51)2人工智能实验指导书第1章课程简介，实验项目及学时安排一．课程简介人工智能、专家系统、决策支持系统、智能机器、神经网络等等，都是近几年来国内外计算机界十分活跃的研究领域；它们是计算机科学、控制论、信息论、神经生物学、心理学、语言学等多学科相互渗透发展起来的综合性学科。

把它们反映到教学活动之中，可开拓学生的视野，了解计算机的新兴发展方向，对实现“宽专业、厚基础”的培养目标十分必要。

通过本课程的学习，将向学生介绍人工智能、专家系统、知识工程的发展简历、核心课题和具体应用领域；讲授知识的有关基本概念和知识的各种逻辑表示方法、常用的计算机问题求解搜索策略；学习智能系统的组成结构和开发工具、方法，掌握小型智能系统的构造原理和调试方法。

因此，《人工智能实验》的主要目的是使学生达到3个层次的实验训练要求：1. 加深理解人工智能的基本概念和方法，掌握一种智能型系统开发软件——Visual Prolog的基本安装、配置及其使用方法。

2. 结合课程内容，掌握使用Visual Prolog完成小规模人工智能程序设计的一般过程和方法。

3.在上述实验的基础上，达到巩固并加深对人工智能基本原理和概念的理解。

4.通过实验，培养学生的自主意识、动手能力、查阅文献能力、思维能力、想象能力和表达能力。

二．实验项目及学时安排- 3 -第2章 Visual Prolog 语言介绍Prolog是英文“PROgramming in LOGic”的缩写。

关于梵塔问题陈熙梵塔问题（也被称为汉诺塔问题或河内塔问题）在几乎任何一种计算机高级程序设计语言的书籍中，都用作解题的典型例子，因此已广为人知。

图1为梵塔游戏的玩具样式。

本文就来主要讨论有关梵塔问题的种种有趣现象与规律。

图1: 梵塔游戏的玩具样式1.梵塔问题的起源梵塔问题起源于中东地区的一个古老的传说：在梵城地下有一个僧侣的秘密组织，他们有3个大型的塔柱，左边的塔柱上由大到小套着64 个金盘。

僧侣们的工作是要把这64个金盘从左边塔柱转移到右边塔柱上去。

但转移过程有严格规定，即每次只能搬动一只盘子；盘子只能在3个塔柱上安放，不允许放地上去；在每个塔柱上，只允许把小盘子叠在大盘子上，而不允许大盘子压在小盘子上。

据传说，僧侣们完成这个任务时，世界的末日就来临了。

19 世纪的法国大数学家鲁卡斯曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金盘的总次数（把1个金盘从某个塔柱转移到另1 个塔柱叫做1 次）为264 -1 = 18446744073709551615假设僧侣们个个身强力壮，每天24 小时不知疲倦地不停工作，而且动作敏捷快速，1 秒钟就能移动1个金盘，那么，完成这个任务也得花5800 亿年！2. 梵塔问题与国际象棋的传说( 264 -l ）是正确解决梵塔问题的最少步数。

因为根据移动金盘的规则，显然，对于最大的那个1 号盘而言，它只需移动1 次。

当把它上面的63 个金盘都在中间塔柱上码放好，而右边塔柱也正好空出来的时候，1 次把它从左边塔柱移到右边塔柱就行了。

对于次大的2 号金盘，它需要移动2 次。

当把它上面的62个金盘都在右边塔柱上码放好，中间塔柱空出来的时候，把它从左边塔柱上移到中间塔柱上，这是1 次。

如前所述，当1 号金盘从左边塔柱移到右边塔柱时，中间塔柱上有63个金盘，待通过反复转移，把上面62个金盘在左边塔柱上码放好时，2 号金盘就可以“脱身”，移到右边塔柱的1 号金盘上就位了，这是它的第2 次也是最后1 次移动。

1．在回溯法求解径时，当前状态的所有可用规则按某种固定原则排序，而不是对各可用规则进行评价，将可用规则按到达目标状态的可能性排序。

( √×)2．在 2 阶梵塔问题中，若小盘和大盘分别表示为 A 和 B，初始状态为（AB, —,—），即第 1 个柱上有两个盘，其他两个柱上无盘，另外，目标状态为（— , AB, —），请画出回溯算法的搜索树。

3．深度优先和宽度优先是两个特别的图搜索法，即待扩展结点插入 OPEN 表的位置按某种固定原则确定。

如果新扩展出的结点不在 OPEN 或 CLOSED 中，深度优先法将其放在OPEN 表的，宽度优先法将其放在OPEN 表的。

4．在 A 算法中，评价函数 f(n)一般表示为 g(n) + h(n) 。

g(n)是 g*(n)的估计， g*(n)的含义是，g(n)一般按计算。

h(n)是 h*(n)的估计， h*(n)的含义是，h(n)根据计算。

5．在 A 算法中，有两个辅助的表，即OPEN 和 CLOSED 表。

OPEN 表存放，且结点按排序，即优先扩展结点，CLOSED 表存放。

6． A 算法中，如果新扩展出的结点已在CLOSED 表，通常将此结点放回 OPEN 表，而不是考虑修改其子结点的指针。

( √×)7．在分支界限法中， f(n) = g(n)，即 h(n) = 0，故分支界限法也是一种 A*算法。

( √×)8．在分支界限法中，将初始结点到各叶子结点的所有路径存入一个队列，且队列按路径耗散非递减排序，若八城市间距如教材图1.11，起始结点为 s、目标结点为t，请画出采用分支界限法的搜索（图）树。

9．动态规划法是对分支界限法的一种改进，即只保留到叶子结点的最短路径。

若八城市间距如教材图 1.11，起始结点为s、目标结点为 t，请画出采用动态规划法的搜索（图）树。

10． A*算法是 A 算法的特例，即规定，A*算法一定能在找到到目标结点的最佳路径（即f(t) = f*(s)）时结束。

《人工智能》课后习题答案第一章绪论1.1答：人工智能就是让机器完成那些如果由人来做则需要智能的事情的科学。

人工智能是相对于人的自然智能而言，即用人工的方法和技术，研制智能机器或智能系统来模仿延伸和扩展人的智能，实现智能行为和“机器思维”，解决需要人类专家才能处理的问题。

1.2答：“智能”一词源于拉丁“Legere”，意思是收集、汇集，智能通常用来表示从中进行选择、理解和感觉。

所谓自然智能就是人类和一些动物所具有的智力和行为能力。

智力是针对具体情况的，根据不同的情况有不同的含义。

“智力”是指学会某种技能的能力，而不是指技能本身。

1.3答：专家系统是一个智能的计算机程序，他运用知识和推理步骤来解决只有专家才能解决的复杂问题。

即任何解题能力达到了同领域人类专家水平的计算机程序度可以称为专家系统。

1.4答：自然语言处理—语言翻译系统，金山词霸系列机器人—足球机器人模式识别—Microsoft Cartoon Maker博弈—围棋和跳棋第二章知识表达技术2.1解答：（1）状态空间(State Space)是利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组（S，O，S0，G）：S—状态集合;O—操作算子集合;S0—初始状态,S0⊂S;G—目的状态,G⊂S,(G可若干具体状态，也可满足某些性质的路径信息描述)从S0结点到G结点的路径被称为求解路径。

状态空间一解是一有限操作算子序列，它使初始状态转换为目标状态：O1 O2 O3 OkS0→−−−S1→−−−S2→−−−……→−−−G其中O1，…，Ok即为状态空间的一个解(解往往不是唯一的)（2）谓词逻辑是命题逻辑的扩充和发展，它将原子命题分解成客体和谓词两个部分。

与命题逻辑中命题公式相对应，谓词逻辑中也有谓词（命题函数）公式、原子谓词公式、复合谓词公式等概念。

一阶谓词逻辑是谓词逻辑中最直观的一种逻辑。

（3）语义网络是一种采用网络形式表示人类知识的方法。

梵塔问题实验报告实验目的1.熟悉和掌握问题规约法的原理、实质和规约过程2.理解规约图的表示方法3.熟悉并掌握递归解决问题的思想实验原理1.利用问题规约法的原理进行问题的分析与描述2.利用递归思想进行问题的解决实验条件1.Window NT/xp/7及以上的操作系统2.内存在512M以上3.CPU在奔腾II以上实验内容梵塔问题源于印度古老的一个传说.相传开天辟地的神勃拉玛创造世界时在印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下,其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。

值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。

实验分析我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64.僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：1.命令僧人63将63个盘子从A座移到C座2.自己将最底下的最大的一个盘子从A座移到C座3.再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座.他是这样做的：1.命令僧人62将62个盘子从A移动到C2.自己将一个盘子从A座移动到B座3.再命令僧人62将62个盘子移到B座再进行一次递归.如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。

最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，该烦他问题得到解决.实验步骤⑴主程序流程图主程序流程图⑵梵塔求解流程图梵塔问题递归过程流程图程序代码#include <stdio.h〉#include 〈graphics.h>#include 〈time.h>#include <dos。

实验一利用问题归约法实现Hanoi塔问题（一）教学要求理解问题归约法的原理和方法，掌握用问题归约表示问题的步骤，并能够对实际问题给出具体的实现。

（二）知识点提示主要知识点：分解、归约、本原问题、与树、或树、与或树、等价变换、用与或树表示问题的步骤。

重点：用与或树表示问题的步骤、Hanoi塔问题的实现。

难点：问题归约法的实现。

（三）教学内容利用问题归约法实现Hanoi塔，主要包括主函数、函数hanoi与搬移函数move，要求在主函数中接收盘子数目并调用hanoi函数。

（四）思考题1. 当盘子数目越来越多时，运行时间有何变化？2. 什么是本原问题？实验二利用状态空间搜索法实现八数码问题（一）教学要求理解状态空间知识表示方法，掌握搜索方法的基本原理，并能够对八数码问题给出具体的实现。

（二）知识点提示主要知识点：状态、状态空间、算符、用状态空间表示问题的步骤、用状态空间求解问题的过程、搜索、宽度优先搜索、有界深度优先搜索、启发式搜索。

重点：状态空间、用状态空间求解问题的过程、宽度优先搜索、有界深度优先搜索、启发式搜索。

难点：用状态空间法求解八数码问题的实现过程。

（三）教学内容用状态空间搜索法求解问题的基本思想是将适用的算符作用于初始状态，以产生新的状态；然后再把一些适用的算符作用于新的状态，重复该过程，直至产生的状态为目标状态为止。

实验内容包括：1．定义状态的描述形式，并给出初始状态和目标状态；2．定义一组算符；3. 利用搜索算法对状态不断扩展，直至得到目标状态为止。

（四）思考题1. 如何使用产生式表示该问题中的算符？2. 使用不同搜索算法求解该问题的性能如何？实验三机器人搬盒子问题（一）教学要求理解谓词逻辑知识表示的方法，掌握一阶谓词逻辑知识表示的基本原理，能够利用归结原理求解简单问题。

（二）知识点提示主要知识点：谓词、原子公式、谓词公式、子句、子句集、空子句、归结原理。

重点：谓词公式、子句集和归结原理的实现。

关于梵塔问题的算法探讨摘要：本文首先介绍梵塔问题的部分主流算法，然后重点探讨A算法在解决梵塔问题中的应用，并简要比较这些算法的优劣。

关键字：梵塔 A算法估价函数Abstract：This article describes some of the mainstream algorithm of Hanoi Tower problem , and then focus on the A algorithm to solve Tower of Hanoi Problem, and briefly compare the merits and drawbacks of these algorithms.Key words:Hanoi Tower A algorithm Evaluation function引言：梵塔问题最初起源于一个传说，相传在印度的贝纳雷斯有座大寺庙，寺庙内有一块红木板，上面插着三根钻石棒，在盘古开天地，世界刚创造不久之时，神便在其中的一根钻石棒上放了64枚纯金的圆盘。

有一个叫婆罗门的门徒，不分日夜地向这座寺庙赶路，抵达后，就尽力将64枚纯金的圆盘移到另一根钻石棒上。

等到婆罗门完成这项工作，寺庙和婆罗门本身都崩溃了，世界在一声霹雳中也毁灭了。

我们对问题加以抽象，于是得到：有三根柱子A、B、C,柱A为柱源，上面插着n个直径各不相同的盘子1、2、3、⋯、n，其中盘1直径最小，盘n直径最大，大盘在下，小盘在上，并按照下列规定将这n个盘子通过中间柱B到柱C。

规定1：每次只准移动一个盘子。

规定2：大盘不能移到小盘上。

一、解法探讨：1、递归求解提到汉诺塔问题，无疑大家第一个想到的就是递归求解，这里只做简要介绍，不做详细分析。

先定义递归方法hanoi (int n，char one，char two，char three)，按如下步骤进行解题(设初始盘子个数为N)：若A塔上仅仅只有一个盘子(N=1)，则直接从A移动到C，问题完全解决。