人工智能导论 课件 第4章 问题求解与搜索

1

教材：

胡玉荣，余云霞，董尚燕，李俊梅，《人工智能导论》，清华大学出版社2025.9人工智能导论第4章问题求解与搜索4.1问题求解4.2状态空间4.3盲目搜索4.4启发式搜索4.5搜索问题的典型应用234.1问题求解4.1.1问题求解概念4.1.2搜索概述44.1.1问题求解概念1.定义：问题求解是运用特定方法和策略，使问题从初始状态过渡到目标状态的过程。问题求解的三个基本特征：一是目的性，问题求解须有明确目标；二是操作序列，涵盖发现、分析、提出假设和检验假设四个主要阶段；三是认知操作，涉及思维和认知活动。2.问题的表示。

“状态空间”是一个非常重要的概念，它用于描述问题求解过程中所有可能的状态以及状态之间的关系。3.求解方法。问题求解核心是搜索答案（目标状态），本质是探索状态空间找解决方案，此即搜索。54.1.2搜索概述按照一定的策略或规则,从知识库中寻找可利用的知识,从而构造出一条使问题获得解决的路线的过程,称为搜索。1.搜索的定义2.搜索的要素(1)搜索空间S，是问题所有可能解的集合。(2)起始状态S0，是行动者开始搜索时的状态。(3)目标测试F，用于判断当前状态与目标状态Sg是否相同的方法64.1.2搜索概述3.搜索的方向(1)数据驱动:从初始状态出发的正向搜索。(2)目的驱动:从目标状态出发的逆向搜索。(3)双向搜索:从初始状态出发作为正向搜索,同时又从目标状态出发作为逆向搜索,直到两条路径在中间的某处汇合为止。74.1.2搜索概述

下面通过迷宫问题了解搜索技术相关术语。如图4-1所示是一个迷宫，需要找到一条从入口S0开始到出口Sg的路径。图中的黑色实线代表障碍，行进时需要避开，虚线代表从入口到出口的一条行走路径。起点为S0,终点为Sg，状态空间图如右图所示。图4-1迷宫问题搜索过程4.1.2搜索概述如图4-2是八数码问题，在3×3的棋盘上,摆有8个棋子,每个棋子上标有1～8的某一数字(数字不重复)。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动步骤。在给定的初始状态中，从1到8的数字顺序是混乱的，不是有序的，而目标状态则是从1到8按顺时针有序排列。现在需要找到移动的办法，从初始状态到目标状态，这个问题的求解也需要使用搜索技术。8图4-2八数码问题状态空间图有许多问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题、路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。94.1.2搜索概述

1）盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。

2）启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。4.搜索技术分类

按问题的表示方式，搜索还可以分为状态空间搜索和与或树搜索。状态空间搜索是指用状态空间法求解问题时进行的搜索。与或树搜索是指用问题归约法求解问题时进行的搜索。本章主要介绍状态空间搜索。根据在问题求解过程中是否运用启发性知识，搜索分为盲目搜索和启发式搜索。104.2状态空间4.2.1状态空间方法4.2.2状态图搜索

4.2.1状体空间方法

1.状态空间定义

1）状态状态就是问题在任一确定时刻的状况，它表征了问题特征和结构等。状态在状态图中表示为节点。状态一般用一组数据表示。在程序中用字符、数字、记录、数组、结构、对象等表示。

2)操作符状态转换规则也叫操作符，就是能使问题状态改变的某种操作、规则、行为、变换、关系、函数、算子、过程等等。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。

一个问题的全体状态及其关系，就构成一个空间，称为状态空间。所以，状态图也称为状态空间图。一个问题的状态空间，是一个三元组

（S,F,G）其中S是问题的初始状态集合，F是问题的状态转换规则集合，G是问题的目标状态集合。4.2.1状体空间方法

2.状态空间表示

3.状态空间方法状态空间方法是将问题求解所涉及的每个可能的步骤表示成一个状态。全部状态以及状态之间的所有转换构成一个以图的形式来表示的状态空间。在状态空间中，存在两个或两组特殊的状态，分别是初始状态和目标状态。1）初始状态对应于问题的起始阶段。2）目标状态对应于问题的终止阶段。3）状态空间中任何一条从初始状态到目标状态的路径为一个可能的解。

于是，问题求解的过程是在状态空间中搜索一条最优的或可行的从初始状态到目标状态的路径的过程。

【例4.1】：迷宫问题的状态空间图表示。

以例迷宫为例。每个格子作为一个状态，并用其标识符作为其表示。那么，两个标识符组成的序对就是一个状态转换规则，如（S0，S4）。于是，该迷宫的状态图表示为:

初始状态集S：S0

状态转换规则集F：｛(S0,S4),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),

(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S2),(S2,S5),(S5,S6),

(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)｝

目标状态集G：Sg

4.2.1状体空间方法

4.2.1状体空间方法图4-3迷宫问题状态空间图迷宫问题状态空间图可以表示为图4-3。

4.2.1状体空间方法起点S0到达节点S4,记为（S0,S4)，然后节点S4可以分别到达节点S1、S5、S7

，记为(S4,S1)，(S4,S5)，(S4,S7)，我们可以选择其中任何一个节点继续往下搜索，但是在搜索过程中约定不能出现回路，即相同节点不能重复搜索，也就是说在搜索过程中,需记住已走过的节点,同时需明确下一步可走的节点,一步一步搜索。那么如果我们选择S5节点，下一个节点可以是S2,S6,S8，记为(S5,S8)，(S5,S2)，(S5,S6)，下一步继续选择S8，则可以到达S9，记为(S8,S9),经过S9最终到达目标节点Sg，记为(S9,Sg)。那么迷宫问题的一条搜索路径即为：S0,S4,S5,S8,S9,Sg。

在状态图中寻找目标或路径的基本方法就是搜索：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。

4.2.2状态图搜索

1.搜索方式

计算机实现状态图搜索的两种最基本方式如图4-4所示：

树式搜索：从树根出发，是以“画树”的方式进行搜索。

线式搜索：在搜索过程中只记录当前走过的节点和边，所形成的轨迹是一条线。进一步可回溯/不可回溯搜索。图4-4树式搜索和线式搜索174.2.2状态图搜索[例4.3]八数码问题的状态图搜索树,如图4-5所示。

问题建立初始状态和目标状态如上图所示，操作规则简单易行的方法是仅为空格制定左、上、右、下四种移动，空格移动的唯一约束是不能移出棋盘。从初始状态开始，下一步可以将1向右移动，也可以将8向下移动，或者将4向左移动，或者将6向上移动，那么就会得到四个新的状态。假设在搜索过程的每一步都能选择最合适的操作，一次搜索过程涉及的状态所构成的搜索树如图4-5所示，其中虚线代表一条搜索路径。184.2.2状态图搜索图4-5迷宫问题状态图搜索树

2.搜索策略搜索具有探索性，要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索和启发式（heuristic）搜索两大类。

盲目搜索：无向导

启发式搜索：有向导（全局最优/局部最优/最佳图搜索…）4.2.2状态图搜索204.3盲目搜索4.3.1广度优先搜索4.3.2深度优先搜索214.3.1广度优先搜索我们看一个例子，这里有两只地鼠,它们都要去地下挖宝藏。第一只地鼠没有任何关于宝藏位置的信息,所以只能盲目地去找,如图4-7(a)所示,此搜索方式就是盲目搜索。而第二只地鼠有一个很好的探测工具,能探测宝藏的位置,即知道相关信息,如图4-7(b)所示,此搜索方式就是启发式搜索。可见,启发式搜索可以更快更准地搜索到目标。图4-7盲目搜索与启发式搜素224.3.1广度优先搜索下面我们先学习盲目搜索。盲目搜索又叫无信息搜索或非启发式搜索。盲目搜索通常是按预定的搜索策略进行搜索,而不会考虑到问题本身的特性。这使得这样的搜索带有盲目性,效率不高。因此,通常适用于求解一些简单问题。常用的盲目搜索有广度优先搜索和深度优先搜索两种。234.3.1广度优先搜索广度优先搜索也称宽度优先搜索,以接近起始节点的程度来依次扩展节点。

1.广度优先搜索的定义

2.广度优先搜索的基本思想从初始节点S开始进行节点扩展,考察S的第1个子节点是否为目标节点,若不是目标节点,则对该节点进行扩展;再考察S的第2个子节点是否为目标节点,若不是目标节点,则对其进行扩展;对S的所有子节点全部考察并扩展以后,再分别对S的所有子节点的子节点进行考察并扩展,如此向下搜索,直到发现目标状态G为止。广度优先搜索示意图如图4-8所示。244.3.1广度优先搜索广度优先搜索的搜索顺序遵循以下原则。(1)广度优先搜索在对第n层的节点全部考察并扩展之前,不对第n+1层的节点进行考察和扩展。(2)同层节点的搜索次序可以任意。图4-8广度优先搜素示意图254.3.1广度优先搜索[例4.4]八数码问题的广度优先搜索,如图4-9所示。广度优先搜索从初始状态S0到目标状态Sg的搜索树,如图4-9所示,每个表格旁边的数字为搜索的顺序。从初始节点S0开始进行节点扩展，考察S0的第1个子节点是否为目标节点，若不是目标节点，则对该节点进行扩展；再考察S0的第2个子节点是否为目标节点,若不是目标节点,则对其进行扩展；对S0的所有子节点全部考察并扩展以后，再分别对S0的所有子节点的子节点进行考察并扩展,如此向下搜索,直到发现目标状态Sg为止。264.3.1广度优先搜索图4-9八数码问题广度优先搜索树274.3.1广度优先搜索

3.广度优先搜索的优缺点(1)优点:只要问题有解,用广度优先搜索总可以得到解。(2)不足:广度优先搜索的盲目性较大,当目标节点离初始节点较远时,将会产生许多无用节点,搜索效率低。284.3.2深度优先搜索

1.深度优先搜索的定义深度优先搜索是另外一种盲目搜索策略,在深度优先搜索过程中,首先扩展最新产生的(即最深的)节点,深度相等的节点可以任意排列。对于许多问题,其状态空间搜索树的深度可能为无限深,或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去),往往给出一个节点扩展的最大深度—深度界限。任何节点如果达到了深度界限,那么都将把它们作为没有后继节点处理。294.3.2深度优先搜索

2.深度优先搜索的基本思想深度优先搜索是一种一直向下的搜索策略。从初始节点S0开始,生成下一级各个子节点,检查是否出现目标节点Sg。若未出现,则按“最晚生成的子节点优先扩展”的原则,再生成下一级子节点,再次检查是否出现目标节点。若仍未出现,则再沿着最晚生成的子节点扩展,逐级“纵向”深入搜索,故称为“深度优先搜索”。

相较于广度优先搜索，深度优先搜索的优点是需要更少的内存空间和更短的搜索时间。因为当深度优先搜索沿着合理的路径进行遍历时，只需要用一个栈来存储从根节点到当前节点的路径所经过的那些节点。但是，深度优先搜索无法保证一定会找到一个解，且搜索过程中会不停地访问相同的状态。另外，深度优先搜索会进行深入搜索从而陷入无限循环。304.3.2深度优先搜索

[例4.5]八数码问题的深度优先搜索,如图4-10所示。

深度优先搜索从初始状态S0到目标状态Sg的搜索树。其搜索过程如图4-10所示,每个表格旁边的数字为搜索的顺序。从初始节点S0开始进行节点扩展，考察S0的第1个子节点是否为目标节点，若不是目标节点，则对该节点进行扩展；再考察S0的第1个子节点的子节点是否为目标节点,若不是目标节点,则对其继续进行扩展；值得注意的是，节点5访问结束后，没找到目标节点，则访问节点5的兄弟节点6，节点6没有其他兄弟节点且还未找到目标节点，进行回溯继续访问节点7，节点7仍不是目标节点则继续往下访问,直至找到目标。314.3.2深度优先搜索图4-10八数码问题深度优先搜索树324.4启发式搜索4.4.1启发式信息4.4.2评估函数4.4.3A*算法334.4.1启发式信息鉴于盲目搜索的不足之处,人们试图找到一种方法可以排列待扩展节点的顺序,即选择最有希望的节点进行扩展,降低复杂性,然后通过删除某些状态及其延伸来得到解,如此,搜索效率将会大为提高。进行搜索一般需要某些有关具体问题领域特性的、与具体问题求解过程相关的、可指导搜索过程朝着最有希望方向前进的控制信息,这些控制信息就叫作启发信息。把利用启发信息进行搜索的搜索方法叫作启发式搜索方法。使用问题本身的定义之外的特定知识来构造代价函数g(x)和启发函数h(x),并依据它们指引的方向进行搜索。常见启发式搜索算法有贪心算法、A算法和A*算法、遗传算法、模拟退火算法等。

1.问题的提出盲目搜索法从理论上，似乎可以解决任何状态空间的搜索问题，但实践表明，盲目搜索只能解决一些状态空间很小的简单问题，而对于那些大状态空间问题，盲目搜索就不能胜任了。因为大空间问题，往往会导致“组合爆炸”。

4.4.1启发式信息

2.启发性信息分类启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可分为以下三类：

(1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。

4.4.2评估函数

36A*算法是目前最有影响的、针对状态空间的启发式图搜索算法。除了基于状态空间的问题求解以外，下面描述的A*算法稍加修改后，还可应用于其它组合优化问题。

4.4.3

A*算法

A*算法通过对估价函数施加约束，以保证得到最优解。设g*(n)表示从初始顶点到顶点Sn的最小代价，h*(n)表示从顶点Sn到目标顶点的最小代价，则顶点Sn处实际最小代价函数为：

f*(n)=g*(n)+h*(n)

374.4.3

A*算法

如果顶点估值都按实际最小代价函数计算，则启发式搜索能够保证得到最优解。但通常实际最小代价是不知道的。为了保证得到最优解，A*算法对启发式函数施加如下约束，

其中S表示状态空间中所有顶点的集合。通俗地说，该约束是要求通过启发式函数估计出的代价值一定要小于等于实际最小代价。同时，h(n)也影响着A*算法的搜索效率。在满足

的条件下，h(n)越大越好。该值越大，表明它与实际最小代价的差距越小，其中携带的启发式信息越多，搜索时扩展的顶点数就会越少，搜索效率会越高。4.4.3

A*算法算法，采用估价函数

[例4.5]

八数码问题，在状态图搜索过程中应用A*算法排列节点。

其中，

是顶点在状态空间中的深度，即从根顶点到

所经历的层次数。（1）启发式函数1：，这里定义为顶点

中不在目标位置上的数码的个数。，而，则，通过对“不在位”数码个数的估计，可以得出至少要移动步才能到达目标。如图4-11所示，初始状态S0中总共有3个数码不在目标位置上，因此394.4.3

A*算法八数码问题采用启发函数1的搜索树如图4-11,每个表格旁边的数字表示该节点的评估函数值f=d+h值,圆圈中的数字表示节点搜索的顺序。图4-11

八数码问题的A*搜索树404.4.3

A*算法（2）启发式函数2：，这里分别是1,1,2,于是,,

同样可以断定从顶点n出发,至少要移动步才能到达目标状态。定义为每一个数码与其目标位置之间距离（不考虑夹在其间的数码）的总和。如图4-12所示，相对于目标状态Sg初始状态S0

总共有3个数码不在目标位置上，即“1”,“2”,“8”,各自距离目标位置的距离414.4.3

A*算法八数码问题采用启发函数2的搜索树如图4-12,每个表格旁边的数字表示该节点的评估函数值f=d+h值,圆圈中的数字表示节点搜索的顺序。图4-12

八数码问题的A*搜索树424.5搜索问题的典型应用4.5.1路径规划4.5.2智力游戏434.5搜索问题的典型应用人工智能可以用来解决一些现实问题,在这些问题中很多属于搜索问题。所以在讲解搜索技术之前,要明确有哪些搜索问题。搜索问题大体上包含两大类:一类是路径规划问题,如最短路径问题、旅行销售员问题等;另一类是智力游戏问题,如N皇后问题、八数码难题、迷宫问题等。444.5.1

路径规划问题

现实生活中,有很多关于路径规划的问题,都可以通过搜索技术进行求解。

1.最短路径问题最短路径是图论研究中的一个经典算法问题,已知起点和终点,寻找两点之间的最短路径。【例4.6】给定一个由若干快递网点构成的网点布局图(见图4-13),每个节点表示一个快递网点,连接两个节点的边表示快递网点间的路径,每条边上的数字表示该路径的代价(千米,km)。求解从初始节点S到目标节点G两个快递网点之间的最短距离。可见,S→A→D→K→G为最短路径。图4-13

快递网点布局图454.5.1

路径规划问题

2.旅行销售员问题旅行销售员问题是一个经典的组合优化问题,给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短路径。【例4.7】一名销售员从西安出发,途经成都、北京、哈尔滨、杭州四个城市,且每个城市访问一次,最终回到西安,求出该销售员旅行所用最短路径。旅行城市分布图如图4-14所示,通过后续启发式搜索策略的学习,可以很容易求出西安→北京→哈尔滨→杭州→成都→西安为此问题的最佳路径。除了以上两种问题外,现实生活中还有很多关于路径规划的实例,如基于道路网的路径规划问题、基于电子地图和GPS定位的最佳路径搜索问题、路由问题等。464.5.1

路径规划问题图4-14

旅行城市分布图除了以上两种问题外,现实生活中还有很多关于路径规划的实例,如基于道路网的路径规划问题、基于电子地图和GPS定位的最佳路径搜索问题、路由问题等。47

4.5.2智力游戏问题

1.N皇后问题从小到大,我们玩过很多智力小游戏,其中有很多游戏可以归结为人工智能的搜索问题,如N皇后问题、八数码难题、迷宫问题等。N皇后问题是计算机科学领域的经典问题之一,以国际象棋为背景,研究的是如何将N个皇后放置在n×n的棋盘上,并且使任意2个皇后之间不能互相攻击(当2个皇后出现在同一行、同一列、同一斜线时可以互相攻击)。其中,当N为8时,就是八皇后问题,需在8×8的棋盘上放置8个皇后。八皇后问题是由国际象棋棋手马克斯·贝瑟尔于1848年提出的,是回溯法的典型案例。484.5.2智力游戏问题

其中,图4-15(a)、(b)违背了约束条件,皇后之间互相攻击;图4-15(c)、(d)没有违背约束条件,即为问题的解。

图4-15

四皇后问题494.5.2智力游戏问题

1）四皇后问题解题思路

四皇后问题是经典的盲目搜索算法应用案例，目标是在4×4的方格棋盘上放置4个皇后，使她们彼此不能相互攻击（即不在同一行、同一列或同一斜线上），本案例采用回溯算法。（1）问题的状态表示①问题解的状态：用数组记录每行皇后位置，设4个皇后为xi，分别在第i行(i=1，2，3，4)；那么可以用(1,x1)，(2,x2)，……，(4,x4)表示4个皇后的位置；由于行号固定，可简单记为：(x1,x2,x3,x4)；例如：(4,2,1,3)②问题的解空间：(x1,x2,x3,x4)，1≤xi≤4(i=1，2，3，4)，共4！个状态；③构造状态空间树：状态空间树的根为空棋盘，每个布局的下一步可能布局是该布局结点的子结点。由于可以预知，在每行中有且只有一个皇后，因此可采用逐行布局的方式，即每个布局有n个子结点。504.5.2智力游戏问题（2）搜索算法①从空棋盘起，逐行放置棋子。②每在一个布局中放下一个棋子，即推演到一个新的布局。③如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。一个解的搜索过程如图4-16

所示。我们来看看四皇后放置棋子的过程，首先在第一行放置1个皇后，标记为（1，1）如图4-16（a)，那么第二个旗子必须从第二行开始放置，根据约束条件，可以放置在（2，3）位置如图4-16（b）。但是放第三颗棋子时，由于第三行没有合规则的位置，那么向上回溯一行，将第二个棋子列向后移动得到（2，4）位置。继续放第三个棋子，如图4-16（d）。同理在放第四个棋子时，没有合适位置，再次回溯到第一行，将棋子向后移动一列，如图4-16（f）。那么4-16（g）,4-16（h）即为放置第二、三、四个棋子的过程。514.5.2智力游戏问题图4-16

四皇后棋盘的布局状态524.5.2智力游戏问题

3）四皇后问题的Python代码实现如下：defsolve_4queens();

solutions

=

[]#

用一个列表存储皇后的位置，索引表示行，值表示列

queens=[-1]*4

#

初始化，-1表示该位置暂未放置皇后def

is_safe(row,

col):

"""检查在(row,

col)位置放置皇后是否安全"""

for

r

in

range(row):

c

=

queens[r]#

检查同一列或同一斜线

if

c

==

col

or

abs(row

-

r)

==

abs(col

-

c):

return

Falsereturn

Truedef

backtrack(row):

"""回溯算法放置皇后"""

if

row

==

4:

#

所有行都放置好了皇后，记录解决方案

#

将皇后位置转换为可视化棋盘格式

solution

=

['.'*col+'Q'+'.'*(3-col)for

col

in

queens]

solutions.append(solution)

return#尝试在当前行的每一列放置皇后for

col

in

range(4):

if

is_safe(row,

col):

queens[row]

=

col

#

放置皇后

backtrack(row

+

1)

#

继续下一行

queens[row]

=

-1

#

回溯，移除皇后

backtrack(0)

#

从第0行开始return

solutions#

打印所有解决方案solutions

=

solve_4queens()print(f"四皇后问题共有{len(solutions)}种解决方案：")fori,solinenumerate(solutions,1):

print(f"\n解决方案

{i}：")

forrowinsol:

print(row)534.5.2智力游戏问题2.八数码问题在3×3的棋盘上,摆有8个棋子,每个棋子上标有1～8的某一数字(数字不重复)。棋盘中留有一个空格,空格周围的棋子可以移到空格中。要求解的问题:给出一种初始布局(初始状态)和目标布局(目标状态),找到一种最少步骤的移动方法,实现从初始状态到目标状态的转换。八数码问题这一类型的智力游戏现实中还有很多,比如通过不断移动滑块复原原图像以及华容道等。1）问题描述八数码问题也称九宫问题。在3×3的棋盘摆有8个棋子，每个棋子上标有1～8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。544.5.2智力游戏问题要解决这个问题，必须先把问题转化为数字描述，由于八数码是一个3*3的矩阵，但在算法中不实用矩阵，而是将这个矩阵转化为一个一维数组，使用这个一维数组来表示八数码，但是移动时要遵守相关规则。八数码问题形式化描述：

（1）初始状态：规定数组中各分量对应各位置上的数字。把3×3的棋盘按从左到右，从上到下的顺序写成一个一维数组。我们可以设定初始状态数组:(2,8,3,1,0,4,7,6,5)，目标状态数组(1,2,3,8,0,4,7,6,5)。

（2）后继函数：按照某种规则移动数字得到的新数组。例如：

(2,8,3,1,0,4,7,6,5)(1,2,3,4,5,6,7,8,0)（3）目标测试：新数组是否是目标状态。即(1,2,3,4,5,6,7,8,0)是目标状态？（4）路径耗散函数：每次移动代价为1，每执行一条规则后总代价加1。554.5.2智力游戏问题图4-17八数码问题的A*搜索树八数码问题采用启发函数2的A*算法搜索树如图4-17,每个表格旁边的数字表示该节点的评估函数值f=d+h值,圆圈中的数字表示节点搜索的顺序。564.5.2智力游戏问题2）八数码问题的A*算法其算法流程图如图4-18，求解八数码问题的步骤如下：步骤一：把S0放入OPEN表（登记当前待考查的节点的数据结构），记为f=h，令CLOSED表（记录考查过的节点的数据结构）为空表；步骤二：从OPEN取出一个未设置过的具有最小f值的节点。如果该节点是目标节点，则搜索结束；否则，将扩展出来的新节点加入CLOSED中。步骤三：对于每个新节点，计算g值和h值，并更新f(n)值。如果该节点已经在OPEN表中，则更新其估价值；否则，将其加入OPEN中。步骤四：重复第2步至第3步直到搜索结束。574.5.2智力游戏问题图4-18八数码问题的A*搜索算法流程584.5.2智力游戏问题3）八数码问题的A*算法的Python语言实现

importnumpyasnpimportoperatorfromcopyimportdeepcopyA=list(map(int,input("初始状态:").split()))

#初始状态输入B=list(map(int,input("目标状态:").split()))

#目标状态输入z=0M=np.zeros((3,3),dtype=int)N=np.zeros((3,3),dtype=int)foriinrange(3):

forjinrange(3):

M[i][j]=A[z]

N[i][j]=B[z]

z=z+1openlist=[]

#open表

classState:

def__init__(self,m):

self.node=m

#节点状态

self.f=0

#总代价f(n)=g(n)+h(n)

self.g=0

#已走路径代价g(n)

self.h=0

#启发式函数估计代价h(n)

self.father=None

#父节点，用于路径回溯init=State(M)

#初始状态goal=State(N)

#目标状态#启发函数defh(s):

distance=0

foriinrange(3):

forjinrange(3):

num=s.node[i][j]

ifnum!=0:

#跳过空格

goal_i,goal_j=np.where(goal.node==num)

distance+=abs(i-goal_i[0])+abs(j-goal_j[0])

#计算到目标的距离

returndistance

#新增函数：定位空格位置deffind_zero(board):

foriinrange(3):

forjinrange(3):

ifboard[i][j]==0:

returni,j

#按照估值函数值对节点列表进行排序deflist_sort(l):

cmp=operator.attrgetter('f')

l.sort(key=cmp)

594.5.2智力游戏问题#A*搜索算法defA_star(s):

globalopenlist

#全局变量可以让OPEN表进行实时更新

openlist=[s]