数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 131 学号：1308060312 学生姓名：谢进 指导教师：叶洁 2015年7 月12 日
设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 1、熟悉树的二叉树的存储结构及其特点。 2、掌握建立哈夫曼树和哈夫曼编码的方法。 设计内容： 欲发一封内容为AABBCAB ……(共长 100 字符,字符包括A 、B 、C 、D 、E 、F六种字符)，分别输入六种字符在报文中出现的次数（次数总和为100），对这六种字符进行哈夫曼编码。 设计要求： 对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： 1.以二叉链表存储， 2.建立哈夫曼树； 3.求每个字符的哈夫曼编码并显示。
博弈树的启发式搜索问题 A方、B方必须是完备博弈，它有三个条件： 1、A，B双方轮流博弈。博弈的结果只有三种情况：A胜，B败；A败，B胜；A，B平手。 2、任一方都了解当前的棋局和历史的棋局。 3、任一方都分析当前的棋局，并能作出有利于自己，而不利于对方的策略。 我们描述博弈过程采用与/或树 1、博弈的初始棋局作为初始节点 2、‘或’节点与‘与’节点逐层交替出现。自己一方扩展节点之间是‘或’，对方扩展节 点之间是‘与’。双方轮流扩展。 3、所有能使自己获胜的终局都是本原问题，相应的节点是可解节点。 本问题其实是一个构造博弈树的问题。对给定的棋局，该棋局中A，B方的棋子数相等，并且轮到A方下。这样构成一个初始棋局，称一个状态。当A或B下一个棋子后，又形成一个新的状态。 任何一方都希望自己取得胜利，因此当某一方有多个方案可供选择时，他总是跳最有利于自己而最不利对方的方案。此时我们站在A的立场上看，可供A选择的方案之间是‘或’的关系，可供B的方案之间是‘与’的关系。因为主动权在A上，A必须考虑任何一个可能被B选中的方案。 极大极小分析方法的特点： 1、它是为其中一方寻找一个最优的行动方案的方法 2、为了当前最优的方案，需要对各个方案能产生的后果进行比较，具体地说就是考虑每个方案实施后，对方可能采取的行动，并计算可能的得分 4、为了计算得分，需要根据问题的特性定义一个估价函数，用来计算当前博弈树端节点的 得分，该得分也称静态估值 5、当端节点估值后，再推算父节点的得分，推算方法是对于‘或’节点，选择子节点中最 大的得分作为自己的得分，对于‘与’节点，选择子节点中最小的得分作为自己的得分，父节点得得分也称倒退值 6、若某一个行动方案能获得最大得倒退值，则它就是当前最好得方案 在本问题中，假设棋盘为4*4的矩阵，A方的棋子为1，B方的棋子为－1，空格为0。 我们定义估价函数为：在某一棋局状态，A方棋子可能占满的整行，整列，整斜线总和与B 方棋子可能占满的整行，整列，整斜线总和的差。这儿的可能是指棋局上留出的空格让A 方或B方全摆放它的棋子。显然如果A方的大。它的下棋选择的策略范围就大。 对某个棋局用极大极小分析后，得出A下一步的最佳策略，同时也给出B的最不利A 的策略，这样一直循环，直到棋局上无空格，如果棋局上A已经胜出了。那么就意味着B 如何采取对A最不利的策略，A也能胜出，表明A处于必胜状态。 程序说明： 编写语言：Matlab6.5 主函数：Chess.m
博弈树 实现计算机与人对弈，诸如象棋、围棋等双方对垒的游戏，是一件饶有趣味的事情。在这里，我们将讨论实现这种人机完备信息博弈时常用的树型结构及其基本算法。所谓人机完备信息博弈，是指人机对垒，依次轮流走步，而且双方的走步信息完全公开。 为了引起对弈者的兴趣，计算机一方必须尽可能多地知道对方己经走过的棋步和将可能走的棋步。对于编程者来说，要使得计算机能懂得比赛规则并记住当前格局，就得建立恰当的数据结构；要使得计算机能在对弈中选择最可能致胜的走步，就得为之设计一个“聪明”的算法。 博弈树适应了这两个需要，它将对垒的初始格局作为根结点，把所有由初始格局经过合法一步得到的新格局作为其子结点，然后以新格局为根，由此新格局产生的格局为其子结点，依次类推，得到一棵包罗对垒中各种可能格局变化的树，并通过对这棵树的遍历，分析确定计算机的走步。这棵树就是这里所说的博弈树。 [例1]井字棋游戏 问题描述： 从一个空的3*3的棋盘开始，甲乙二人轮流放置棋子到棋盘上未被占据的方格中。如果甲第一个放，他把棋子放在中央方格里；然后轮到乙放，他把棋子放在第一行中间的方格里；于是又轮到甲放，……，如此进行下去，判定胜负的方法是：若某一游戏者若有3枚棋子占据了一横线或一竖线，或一对角线，则该游戏者获胜；若至整个棋盘被占满还没有一方获胜，则为平局。 算法分析： 我们让计算机模拟甲方，称为max选手，与计算机对手的乙方称min选手，上述博弈由这两位选手对垒，双方依次轮流走步。 博弈树以棋盘状态作为结点。开始时空棋盘作为树根，max先放。max选择某个空格放置棋子后的棋盘所有可能状态，都作为根的子结点出现在树的第一层。第二层的结点是min 方走完后的可能棋盘状态，min方从第一层的某个结点出发，选择某个空格放置棋子后的所有可能棋盘状态都作为该结点的子结点出现在第二层。下图的树称作博弈树，树根并不是空棋盘，这棵树的第二层并不是游戏终止时的棋盘状态，我们还可以画出第三层、第四层、……的结点，但在一般情况下，由于计算机存储器大小和运算速度的限制，不能把博弈树构造到游戏终止时的棋盘状态，而只能构造到某一特定的深度。
习题八: 根树及其应用 1．从简单有向图的邻接矩阵怎样去决定它是否为根树。如果是根树，怎样定出它的树根和树叶。 2．求出对应于图7-8.9所给出的树的二叉树。 3．证明在完全二叉树中，边的总数等于)1(2-t n ，式中t n 是树叶数。 4．在一棵t 叉树中，其外部通路长度与内部通路长度之间有什么关系。 5．给定权1，4，9，16，25，36，49，64，81，100 a ）构造一棵最优二叉树。 b ）构造一棵最优三叉树。 c ）说明如何构造一棵最优t 叉树。 6．构造一个与英文字母e y o g d b ,,,,,对应的前缀码，并画出该前缀码对应的二叉树，再用此六个字母构成一个英文短语，写出此短语的编码信息。 7．设A 是二进制序列的集合。我们将A 划分为两个子集0A 和1A ，这里0A 是A 中第一个数字是0的序列的集合，1A 是A 中第一个数字是1的序列的集合，然后我们根据序列中的第二个数字将0A 划分成两个子集，对1A 也用同样方法加以划分。运用不断的将序列的集合划分成子集的方法来证明：如果A 是前缀码，则存在一棵二叉树，其中从每个分枝点射出的两条边分别标号0和1，使得赋于树叶的0和1的序列是A 中的序列。 8．给出公式（))(())(R Q P Q P P ?∧∨?∧∧?∨的根树表示。 9．（1）求带权为1，1，2，3，3，4，5，6，7的最优三元树。 （2）求带权为1，1，2，3，3，4，5，6，7，8的最优三元树。 10．在通信中要传输八进制数字0，1，2，…，7。这些数字出现的频率为0：30%；1：20%； 2：15%；3：10%；4：10%；5：6%；6：5%；7：4%。 编一个最佳前缀码，使通信中出现的二进制数字尽可能地少。具体要求如下： （1） 画出相应的二元树。 （2） 写出每个数字对应的前缀码。 图7-8.9
南京信息工程大学 研究生实验报告 课程名称人工智能与专家系统 实验名称利用α-β搜索过程的博弈树搜索算法编写一字棋游戏学生姓名王灿田 学号 20111221332 院系信息与控制学院 专业系统分析与集成 任课教师梅平 2012年6月10日
利用α-β搜索过程的博弈树搜索算法编写一字棋游戏 1.α-β搜索过程 在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加承指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？ 设某博弈问题如下图所示，应用极小极大方法进行搜索。假设搜索的顺序为从下到上，从左到右。当计算完a的值为0后，由于b是极大节点，马上就可以知道b的值大于等于0。接下来求c的值。由于c是极小节点，由d的值为-3，知道c的值小于等于-3。而a和c都是b的子节点，所以即便不扩展节点e，也可以知道b的值一定为0了。所以在这种情况下，没有生成节点e的必要。同样，在知道b的值为0后，由于k是极小节点，所以立即知道k的值要小于等于0。而通过节点f、g，知道h的值至少为3。这样即便不扩展A所包围的那些节点，也能知道k的值一定为0。所以A包围的那些节点也没有生成的必要，不管这些节点取值如何，都不影响k的值。如果在搜索的过程中，充分利用这些信息，不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程正是这样一种搜索方法。 图1 MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。如图1中，其中一个MIN节点要全部生成A、B、C、D四个节点，然后还要逐个计算其静态估值，最后在求倒推值阶段，才赋给这个MIN节点的倒推值－∞。其实，如果生成节点A后，马上进行静态估值，得知f（A）＝－∞之后，就可以断定再生成其余节点及进行静态计算是多余的，可以马上对MIN节点赋倒推值－∞，而丝毫不会影响MAX的最好优先走步的选择。这是一种极端的情况，实际上把生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早修剪掉一些无用的分枝，同样可获得类似的效果，这就是α-β过程的基本思想。
6一个猎人要带着一只狼、一只羊、一捆草过河，但是人不在的时候，狼会吃羊、羊会吃草，猎人每次只能带一样东西过河。试用状态空间图求出他们能顺利过河的方案。 解：用四元组（f ，w ，s ，g ）表示状态，其中f 表示猎人，w 表示狼，s 表示羊，g 表示草，其中每个元素都可以为0或1，表示在左案，1表示在 右岸。四元组可表示的状态共有16种，其中合法状态为10种： （0，0，0，0）（0，0，0，1）（0，0，1，0）（0，1，0，0）（0，1，0，1） （1，0，1，0）（1，0，1，1）（1，1，0，1）（1，1，1，0）（1，1，1，1） 初始状态为（0，0，0，0）目标状态为（1，1，1，1） 共有七种操作：从左岸到右岸三种，从右岸到左岸四种 操作符 条件 动作 p 1 f=0，w=0，s 和g 相异 f=1，w=1 p 2 f=0，s=0， f=1，s=1 p 3 f=0，g=0，w 和s 相异 f=1，g=1 q 0 f=1，s 和g 相异，w 和s 相异 f=0 q 1 f=1，w ＝1，s 和g 相异 f=0，w ＝0 q 2 f=1，s ＝1， f=0，s ＝0 q 3 f=1，g ＝1，w 和s 相异 f=0，g ＝0 (0,0,0,0)(1,0,1,0) p 2 q 2 (0,0,1,0)(1,1,1,0)p 1 q 1 (1,0,1,1) (0,0,0,1)q 0 p 3 q 3(0,1,0,0) q 2p 2 (1,1,0,1)p 3 q 3 q 2 p 2 p 2 q 2 (0,1,0,1) (1,1,1,1) p 2 q 2 q 0 方案有两种：p2→ q0 → p3→ q2 → p2 → q0 → p2 p2→ q0 → p1→ q2 → p3→ q0→ p2 8.琴键翻动 （供参考）解：引入一个三元组(q0,q1,q2)来描述总状态，开状态为0，关状态为1，全部可能的状态为 ： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。 翻动琴键的操作抽象为改变上述状态的算子，即F ＝{a, b, c} a:把第一个琴键q0翻转一次 b:把第二个琴键q1翻转一次 c:把第三个琴键q2翻转一次 问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}> 问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。
实验4 树、图及其应用 ————二叉树的遍历 一、任务和目的 具体任务，达到的目的。 设计一个程序演示在二叉树上进行三种遍历的过程。 【基本要求】 （1）从键盘上输入二叉树的每一个结点，演示二叉树T的建立过程。 （2）演示各种遍历的遍历过程。 二、概要设计 主要数据结构定义，函数功能及各参数用途。 #include
常用的生成树协议：STP（Spanning Tree Protocol)由IEEE802.1D定义，RSTP(Rapidly Spanning Tree Protocol)由IEEE802.1W定义，MSTP（Multiple Spanning Tree Protocol)由IEEE802.1S定义。 生成树严格意义上来讲属于应用层的东西，但是是为了解决二层的广播风暴问题，所以也可以看成是二层的东西。 STP STP生成树计算原则： 1.确定环路中的根桥。 根桥由BID（bridge ID)来确定（BID=2字节的网桥优先级+网桥的MAC地址构成，优先级默认为32768），具备最小的BID的交换机成为根桥。 2.确定根端口。 根端口选举原则是确定非根桥到根桥最小开销的端口。（Root path cost).一般情况下，接口带宽越大则开销值越小。 选举原则：a.比较Root Path Cost（根路径开销），越小越优先，一样则 b.端口上行交换机的Bridge ID（桥ID），越小越优先，一样则 c.端口上行端口的Port Identifier，越小越优先（端口标识，端口标识号由1字节优先级+1字节端口号构成） 3.确定指定端口。 为每个网段选出一个指定端口（Designated Port），指定端口为每个网段转发发往根交换机方向的数据，且转发由根交换机方向发往该网段的数据。 选举原则：a.比较Root Path Cost（根路径开销），越小越优先，相同则 b.端口所属Bridge ID，越小越优先，相同则 c.端口的Port ID。 4.确定阻塞端口。 环路中剩下的端口成为阻塞端口（Alternate Port),当指定端口有问题，就启用阻塞端口。 数据的转发路径：由下级非根交换机的指定端口到上级非根交换机的根端口，一直到根交换机的指定端口。（这样就可以避免环路） STP端口状态描述 状态数据帧MAC 生成树计算BPDU 收发Disable No No No No No Blocking No No No Yes No Listening No No Yes Yes Yes
第三章 搜索策略课后习题及答案 一、选择题： 1. 启发式搜索中，通常OPEN表上的节点按照它们f函数值的_____顺序排列。 （ D ） A平均值 B 递减 C 最小 D递增 2. 按尼尔逊(Nilsson)提出的有序搜索基本算法指出,一个节点的希望程度大，则f值_____。 （ B ） A 不变化 B 小 C 大 D 为0 3. 如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为_____。（ B ） A A*算法 B A算法 C有序搜索 D启发式搜索 4. 在与或树和与或图中，我们把没有任何父辈节点的节点叫做_____。 （ C ） A 叶节点 B端节点 C根节点 D 起始节点 5. 对于八数码问题： 起始棋局 —> 目标局棋 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 取h(n)=W(n)， W(n)用来计算对应于节点n的数据库中错放的棋子个数。请问需要扩展多少个节点才能到达目标？ （ C ） A 20 B 13 C 6 D 11
6. α-β剪枝技术中，一个MIN节点的β值等于其后继节点当前（ ）的最终倒 推值。 （ A ） A 最小 B 最大 C 平均 D α值 7. α-β剪枝技术中，“或”节点n的α值如果不能降低其父节点的β值，则对节点n以下的分枝可停止搜索，并使节点n的倒推值为α。这种剪枝称为_____。 （ A ） A β剪枝 B α剪枝 C α-β剪枝 D极小极大分析法 8. 宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的_____途径(如果有路径存在时)。 （ B ） A 可行 B 最短 C 最长 D 解答 9. A*算法是一种_____。 （ ABD ） A 图搜索策略 B 有序搜索算法 C 盲目搜索 D 启发式搜索 10. 应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法的算法就叫做_____。 （ C ） A 盲目搜索 B 深度优先搜索 C 有序搜索算法 D 极小极大分析法 二、 填空题： 1. OPEN表用于存放未扩展的节点，CLOSED表存放_已扩展_的节点。 2. 通常OPEN表记录了节点及其___ 父_节点。
树形结构及其应用 树形结构及其应用实验题目：树型结构的建立与遍历设计成绩报告成绩指导老师 一、实验目的1、学会二叉树这一数据结构的用法，掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。2、熟练掌握二叉树与广义表之间的相互转换方法。3、熟练掌握二叉树的先序、中序、后序，递归与非递归遍历算法。4、学会二叉树线索化方法，并掌握线索二叉树的存储结构。5、熟练掌握线索二叉树的先序、中序、后序的遍历算法。 二、实验要求及实验环境1、实验要求：(1) 至少用两种方法，编写建立二叉树的二叉链表存储结构的程序，并用广义表的形式显示并保存二叉树；(2) 采用二叉树的二叉链表存储结构，编写程序实现二叉树的先序、中序和后序遍历的递归和非递归算法以及层序遍历算法，并显示二叉树和相应的遍历序列；(3) 在二叉树的二叉链表存储结构基础上，编写程序实现二叉树的先序、中序和后序线索链表存储结构建立的算法，并用广义表的形式显示和保存二叉树的线索链表；(4) 在二叉树的线索链表存储结构上，编写程序分别实现求一个结点的先序（中序、后序）的后继结点的算法；(5) 在 (4)
基础上，编写程序实现对线索二叉树进行先序、中序和后序遍历的非递归算法，并显示线索二叉树和相应的遍历序列。2、实验环境：Windows下的dev-c++、 三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）Create a bit- tree1．逻辑设计主程序流程递归中序线索化线索化递归中序线索化递归先序线索化以广义表格式输出树递归非递归先序遍历递归非递归中序遍历递归非递归后序遍历输出节点的后继节点遍历后序线索化遍历中序线索化遍历先序线索化线索二叉树链式结构定义typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; bool LTag,RTag; }bnode,*btree;2．物理设计Btree create()创建一棵树并赋值应用数组栈btree a[MAX]Void printBTree(btree T)以广义表形式打印树Void preorder(btree t)先序递归遍历Void inorder(btree t)中序递归遍历Void postorder(btree t)后序递归遍历btree copy(btree t)复制二叉树Int main（）主函数Void preorder2(btree t)先序非递归遍历Void inorder2(btree t)中序非递归遍历Void postorder2(btree t)后序非递归遍历层序遍历void levelorder(btree t)void prethreading(btree p)先序线索化Btree preorderthreading(btree prehead,btrreeT);先序线索化void prethreading(btree p)先序线索化Btree inorderthreading(btree prehead,btrreeT);中序线索化void
1.树式搜索：a,盲目搜索（穷举式搜索）{ 广度优先深度优先} b,启发式搜索{全局择优、局部择优，分支界限、最近择优、A 算法、A*算法} 线式搜索：a,盲目搜索{随即碰撞、回溯穷举} b,启发式搜索{不回溯、智能回溯} 2.盲目搜索，也就是无导向搜索。在搜索过程中，没有任何背景知识作指导不 考虑任何与解有关的信息，随机的或按预定顺序机械地搜索，并判断是否为所求的解，直到找到解或是证明问题无解为止。盲目搜索效率太低，一般只适用于求解比较简单的问题。 3.启发式搜索，即为有导向的搜索，利用“启发性信息”引导搜索。所谓的启 发性信息就是与问题有关的有利于找到问题解的信息或知识。启发函数，是用来估计搜索树上节点与目标节点接近程度的一种函数，通常即为h(x)。 4. OPEN表：动态数据结构，登记记录当前待考察的节点。 CLOSED表：动态数据结构，记录考察过得节点。 5.深度优先搜索算法的特点是 ①般不能保证找到最优解； ②当深度限制不合理时，可能找不到解，可以将算法改为可变深度限 制； ③法与问题无关，具有通用性； ④于图搜索方法 广度优先搜索算法的特点是 ② 问题有解时，一定能找到解； ②当问题为单位耗散值，并且问题有解时，一定能找到最优解；③效率 低；④方法与问题无关，具有通用性；⑤属于图搜索方法。 6.解：用四元组(f、w、s、g)表示状态， f 代表农夫，w 代表狼，s 代表羊，g 代表菜，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。 初始状态S0：(0,0,0,0) 目标状态：(1,1,1,1) 不合法的状态:(1,0,0,*),(1,*,0,0),(0,1,1,*),(0,*,1,1) 操作集F={P1，P2，P3，P4，Q1，Q2，Q3，Q4} 操作符条件动作
实验二：利用α-β搜索过程的博弈树搜索算法编写一字棋游戏 一、实验目的与要求 （1）了解极大极小算法的原理和使用方法，并学会用α-β剪枝来提高算法的效率。 （2）使用C语言平台，编写一个智能井字棋游戏。 （3）结合极大极小算法的使用方法和α-β剪枝，让机器与人对弈时不但有智能的特征，而且计算的效率也比较高。 二、实验原理 一字棋游戏是一个流传已久的传统游戏。游戏由两个人轮流来下，分别用“X”和“O”来代替自身的棋子。棋盘分9个格，双方可以在轮到自己下的时候，可以用棋子占领其中一个空的格子。如果双方中有一方的棋子可以连成一条直线，则这一方判胜，对方判负。当所有的格子都被占领，但双方都无法使棋子连成一条直线的话，则判和棋。 这是一个智能型的一字棋游戏，机器可以模拟人与用户对弈。当轮到机器来下的时候，机器会根据当前棋局的形势，利用极大极小算法算出一个评价值，判断如何下才对自身最有利，同时也是对方来说对不利的，然后下在评价值最高的地方。另外利用α-β剪枝，使机器在搜索评价值的时候不用扩展不必要的结点，从而提高机器计算的效率。 在用户界面方法，用一个3×3的井字格来显示用户与机器下的结果。当要求用户输入数据的时候会有提示信息。用户在下的过程中可以中途按下“0”退出。当用户与计算机分出了胜负后，机器会显示出比赛的结果，并按任意键退出。如果用户在下棋的过程中，输入的是非法字符，机器不会做出反应。 三、实验步骤和过程 1.α-β搜索过程 在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加承指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？设某博弈问题如下图所示，应用极小极大方法进行搜索 MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。如图1中，其中一个MIN节点要全部生成A、B、C、D四个节点，然后还要逐个计算其静态估值，最后在求倒推值阶段，才赋
3.3 博弈树搜索 3.3.1 博弈概述 诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的"二人零和、全信息、非偶然"博弈，其特征如下： (1) 对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。 (2) 在对垒过程中，任何一方都了解当前的格局及过去的历史。 (3) 任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。 在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是"或"关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是"与"关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN 方选中，MAX方必须应付每一种情况的发生。 这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵"与或树"。描述博弈过程的与或树称为博弈树，它有如下特点： (1) 博弈的初始格局是初始节点。 (2) 在博弈树中，"或"节点和"与"节点是逐层交替出现的。自己一方扩展的节点之间是"或"关系，对方扩展的节点之间是"与"关系。双方轮流地扩展节点。 (3) 所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。 我们假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。 3.3.2 极小极大分析法 在二人博弈问题中，为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案，就需要对当前的情况以及将要发生的情况进行分析，通过某搜索算法从中选出最优的走步。在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树，如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的，比如曾有人估计，西洋跳棋完整的博弈树约有1040个节点。 最常使用的分析方法是极小极大分析法。其基本思想或算法是： (1) 设博弈的双方中一方为MAX，另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。 (2) 为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。 (3) 为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。 (4) 当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。 (5) 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。 在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。试图
一、根系类型 （一）主根、侧根和不定根 根据根的发生部位不同，可以分为主根、侧根和不定根三类。种子萌发时胚根首先突破种皮、向下生长，这种由胚根直接生长形成的根，称为主根。有时也称为直根。当主根生长到一定长度时，就会从内部侧向生出许多支根，称为侧根。侧根与主根往往形成一定角度，当侧根生长到一定长度时，又能生出新的次一级的侧根，这样的多次反复分枝，形成整株植物的根系，例如棉花、菜豆、油菜等双子叶植物的根系，主根和侧根都从植物体固定部位生长出来的，均属于定根。此外还有许多植物除产生定根外，还能从茎、叶老根或胚轴上生出根来，这些根发生的位置不固定，都称为不定根（图4-1）。不定根也能不断地产生分枝，即侧根。禾本科植物的种子萌发时形成的主根，存活期不长，以后由胚轴上或茎的基部所产生的不定根所代替。农、林、园艺工作上，利用枝条、叶、地下茎等能产生不定根的习性，而进行大量的扦插、压条等营养繁殖。 （二）直根系和须根系 一株植物地下部分所有根的总和，也就是包含主根和它分枝的各级侧根或不定根和它分枝的各级侧根，称为根系。 根系有直根系和须根系两种。有明显主根和侧根区别的根系，称为直根系，如棉花、菜豆、油菜、蒲公英等绝大多数双子叶植物的根系。无明显的主根与侧根区分的根系，即主根不发达，或根系全部由不定根及其分枝组成的，粗细相差不多，形成比较均匀的根系，似胡须一样，称为须根系，如小麦、水稻、葱、蒜等单子叶植物的根系。
在适宜的土壤条件下，树木的多数根集中分布在地下40一80cm深 范围内；具吸收功能的根，则分布在20cm左有深的土层内。就树种而言，根系在地下分布 的深浅差异甚大。有些树木，如直根系和多数乔木树种，它们的根系垂直向下生长特别旺 盛、根系分布较深，常被称为深根性树种；而主根不发达，侧根水平方向生长旺盛*大部 分报分布于土上层的树木，如部分须根系和灌木树种，则被称为浅根性树种。深根性树种 能更充分地吸收利用土壤深处的水分与养分，耐旱、抗风能力较强，但起苗、移栽难度大。 生产上，多通过移栽、强权等措施，来抑制主根的垂直向下生长，以保证栽植成活率。浅 根性树种则起苗、移栽相对容易，并能适应含水量较高的土坡条件，但抗旱、抗风及与杂 草竞争力较弱，其中有部分树木根系因分布太浅，随着根的不断生长挤压，会使近地层土 壤疏松，并向上凸起，容易造成路面的破坏。园林生产上，可以将深根性与浅根性树种进
第三章 搜索策略课后习题 一、选择题： 1. 启发式搜索中，通常OPEN表上的节点按照它们f函数值的_____顺序排列。 （ ） A平均值 B 递减 C 最小 D 2. 递增按尼尔逊(Nilsson)提出的有序搜索基本算法指出,一个节点的希望程度大，则f值 。 （ ） A 不变化 B 小 C 大 D 为0 3. 如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为_____。 （ ） A A*算法 B A算法 C有序搜索 D启发式搜索 4. 在与或树和与或图中，我们把没有任何父辈节点的节点叫做_____。 （ ） A 叶节点 B端节点 C根节点 D 起始节点 5. 对于八数码问题： 起始棋局 —> 目标局棋 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 取h(n)=W(n)， W(n)用来计算对应于节点n的数据库中错放的棋子个数。请问需要扩展多少个节点才能到达目标？ （ ）
A 20 B 13 C 6 D 11 6. α-β剪枝技术中，一个MIN节点的β值等于其后继节点当前（ ）的最终倒推值。 （ ） A 最小 B 最大 C 平均 D α值 7. α-β剪枝技术中，“或”节点n的α值如果不能降低其父节点的β值，则对节点n以下的分枝可停止搜索，并使节点n的倒推值为α。这种剪枝称为_____。 （ ） A β剪枝 B α剪枝 C α-β剪枝 D极小极大分析法 8. 宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的_____途径(如果有路径存在时)。 （ ） A 可行 B 最短 C 最长 D 解答 9. A*算法是一种_____。 （ ） A 图搜索策略 B 有序搜索算法 C 盲目搜索 D 启发式搜索 10. 应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法的算法就叫做_____。 （ ） A 盲目搜索 B 深度优先搜索 C 有序搜索算法 D 极小极大分析法 二、 填空题： 1. OPEN表用于存放未扩展的节点，CLOSED表存放_ _的节点。
问题：指事件或事物的已知或当前状态与目标状态之间的有差异。问题求解：指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一直。 问题求解所需的知识（求解框架）：叙述性知识、描述客观事物的特点及关系。过程性知识、通常是解决问题的操作步骤和过程的知识，也称为操作性知识。控制性知识、求解问题的方法和技巧的知识，确定解决问题的策略。 知识表示:研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。 常用的知识表示形式:状态空间图，与或图，谓词逻辑，产生式，框架，语义网络 盲目搜索：无向导的搜索，也称穷举搜素。在搜索过程中，没有任何背景知识作指导，不考虑任何与解有关的信息，随机地或按预先规定的顺序（如广度优先和深度优先）机械地生成树的节点，并判断是否为解，直到找到解或证明问题无解为止。 特点：搜索效率太低，所以在实际中往往是不可行的。 启发函数：通过函数计算来评价每种选择的价值大小，用以指导搜索过程。 启发式搜索：利用问题本身的“启发性信息”不断地改变或调整搜索的方向，使搜索朝着问题本身最希望的方向进行，加速问题的求解并找到最优解。特点：重排OPEN表，选择最有希望的节点加以扩展。 启发式搜索—全局择优算法：也叫做最好优先搜索，在启发性知识导航下的广度优先搜索，在OPEN表中保留所有已生成而为考察的节点，对其中的每个节点x计算启发函数h（x）,从全部节点中选出最优节点进行扩展，而不管这个结点出现的搜索树的什么地方。 步1、把初始几点S。放入OPEN表中，计算h(S。)； 步2、若OPEN表为空，则搜索失败，退出。 步3、否则，移出OPEN表中第一节点N放入CLOSED表中，并冠以序号n; 步4、若目标结点S。=N，则搜索成功，利用CLOSED表中的返回指针找出S。到N的路径即为所求解，退出。 步5、若N不可扩展，则转步2； 步6、否则，扩展N，计算N的每个子节点x的启发函数h(x)，并将N所有子节点x配以指向N的返回指针后放入OPEN表中，依据启发函数值h(x)对节点的计算，对OPEN表中所有节点按其启发函数值的大小以升序排列，转步2. 局部择优：是启发性知识导航下的深度优先搜索，在OPEN表中保留所有已生成为为考察的节点，对其中新生成的每个子节点x计算启发函数h(x),从全部子节点中选出最优节点进行扩展，其选择下一个要考察的结点的范围是刚刚生成的全部子节点。 步6、否则，扩展N，计算N的每个子节点x的启发函数值h(x),并将N的所有子节点x配以指向节点N的指针后，将全部子节点按数值升序排列后反之OPEN表的首部，转步2. 盲目和启发搜索的的不同：对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。 在图搜索算法中，OPEN表，CLOSED表的作用各是什么 OPEN表：专门登记已经生成但还没有考察的节点，即待考察节点。算法执行时总是从OPEN 表的首部取出节点，不同控制策略就是通过节点在OPEN表中的不同排序来实现的。CLOSED表：用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号（返回指针）。搜索结束时，可以利用节点之间的关系，找到问题的解路径或解树。实际上，CLOSED表中存放的就是一定搜索策略下的搜索树。 广度优先搜索的特点： 广度优先中OPEN表是一个队列，广度优先搜索又称为宽度优先或横向搜索。广度优先策
中南大学 数据结构实验报告 题目：树结构及其应用学生姓名：张雨欣 学号：0902150323 指导老师：余腊生 学院：信息科学与工程学院专业班级：计科工试1501班 完成时间：2016年12月27日指导老师评定：签名：
需求分析 二叉树的建立与遍历（验证性实验） 问题描述： 建立一棵二叉树，并对其进行遍历（先序，中序和后序），打印输出遍历结果 基本要求： 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序，中序和后序），将遍历结果打印输出。 测试数据： AB.CE..G.D.F.H..则输出结果为：先序为ABCEGDFH,中序为BECGADFH,后序为EGCBHFDA 源程序 #include
char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(BitTree)malloc(sizeof(BitNode)); (*bt)->data=ch; CreatBiTree(&((*bt)->LChild)); CreatBiTree(&((*bt)->RChild)); } } void Visit(char ch)//访问根节点 { printf("%c ",ch); } void PreOrder(BitTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { Visit(root ->data); /*访问根结点*/ PreOrder(root ->LChild); /*先序遍历左子树*/ PreOrder(root ->RChild); /*先序遍历右子树*/ } } void InOrder(BitTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { InOrder(root ->LChild); /*中序遍历左子树*/ Visit(root ->data); /*访问根结点*/ InOrder(root ->RChild); /*中序遍历右子树*/ } } void PostOrder(BitTree root) /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/ { if(root!=NULL) { PostOrder(root ->LChild); /*后序遍历左子树*/ PostOrder(root ->RChild); /*后序遍历右子树*/ Visit(root ->data); /*访问根结点*/ }
目录 摘要 (2) 第一部分设计总概 (2) 一．设计目的 (2) 二．设计要求及内容 (3) 三．设计方法 (3) 四．系统分析与设计 (3) 一. 概要设计 (3) 二. 详细设计 (3) 第二部分数据结构设计 (4) 一：主系统的函数 (4) 二：头文件 (4) 第三部分功能实现与程序调试 (4) 一：程序实现的功能流程图 (5) 二：程序实现源代码 (5) 1. 头文件 (5) 2.cpp文件代码 (8) 三．程序实现截图 (9) 1.界面 (9) 2. 进入游戏开始下棋 (9) 3.判断棋局胜负： (11) 4：结束游戏： (11) 第四部分完成设计 (12) 一、实验总结 (12)
摘要 用所学的语言，设计简单的一字棋游戏。 关键字：博弈，启发式搜索 第一部分设计总概 一．设计目的 理解和掌握博弈树的启发式搜索过程，能够用选定的编程语言实现简单的博弈游戏。
二．设计要求及内容 设计一个不少于3行3列的棋盘，自己给出估价函数，采用极大极小搜索方法。采用人机对弈的方式，一方走步够等待对方，对弈过程的棋局变化在屏幕上显示。 三．设计方法 采用c语言编写程序实现 四．系统分析与设计 一. 概要设计 A：进入主界面 主界面包括导语及游戏操作步骤及其规则 B：进入游戏，开始下棋 C：判断输赢，结束游戏 D：判断是否重新开始游戏 是则返回B步骤 否则结束游戏 二. 详细设计 1.进入vs2010，选择win32项目，新建程序
2．界面设计 利用所学的c语言知识，设计一个简单的棋盘游戏界面3.函数设计 利用所学的算法，编写棋盘分析函数 第二部分数据结构设计 一：主系统的函数 窗口创建函数，消息响应函数皆放在主函数cpp里面二：头文件 存放具体的操作步骤及其函数 第三部分功能实现与程序调试