启发式图搜索过程

第三章知识的状态空间表示法1 课前思考：人类的思维过程，可以看作是一个搜索的过程。

某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。

2 学习目标：掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法，对典型问题，掌握启发式函数的定义方法。

3 学习指南：了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题。

4 难重点：回溯搜索算法、算法及其性质、改进的Ａ＊算法。

5 知识点：本章所要的讨论的问题如下：有哪些常用的搜索算法。

问题有解时能否找到解。

找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。

3.1 状态空间表示知识一、状态空间表示知识要点1．状态状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。

通常表示成：Q={q1，q2，……，qn}当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。

实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。

2．操作（规则或算符）操作（Operator）是把问题从一种状态变成为另一种状态的手段。

当对一个问题状态使用某个可用操作时，它将引起该状态中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态。

操作可以是一个机械步骤、一个运算、一条规则或一个过程。

操作可理解为状态集合上的一个函数，它描述了状态之间的关系。

通常可表示为：F={ f1 , f2,……… fm}3．状态空间状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。

用三元组表示为：（{Qs}，{F}，{Qg}）Qs：初始状态，Qg：目标状态，F：操作（或规则）。

B 规则B-ruleF 规则F-ruleNP 完全问题 NP-complete problem本原问题primitive problem博弈game不可解标示过程unsolvable-labeling procedure不可解节点unsolvable node不可满足集unsatisfiable set不确定性uncertainty差别difference产生式production产生式规则production rule冲突解决conflict resolution存在量词existential quantifier代换substitution代换例substitution instance倒退值backed-up value等价equivalence定理证明theorem-proving动作action反演refutation反演树refutation tree费用cost估计费用estimated cost 估值函数evaluation function归结resolution归结反演resolution refutation归结式resolvent归结原理resolution principle归约reduction合取conjunction合取范式conjunctive normal form合取式conjunct合适公式、合式公式well-formed formula (wff)合一unifier回答语句answer statement回溯backtracking机器学习machine learning节点的扩展expansion of node解释器interpreter解树solution tree解图solution graph句子sentence可解标示过程solvable labeling procedure可解节点solvable node 可满足性satisfiability 空子句empty clause控制策略control strategy宽度优先搜索breadth-first search扩展节点expendingnode连词，连接词connective量词quantifier量词辖域scope ofquantifier论域，文字域domainof discourse逻辑logic逻辑连词logicconnective逻辑推理logicreasoning盲目搜索，无信息搜blind search模式匹配match pattern模式识别Patternrecognition母式matrix逆向推理backwardreasoning匹配match启发函数heuristicfunction启发式搜索Heuristicsearch启发搜索heuristicsearch启发信息heuristicinformation前缀prefix全称量词universalquantifier全局数据库Globaldatabase人工神经网络artificialneural network人工智能artificialintelligence,AI人工智能语言AIlanguage深度优先搜索depth-first search事实fact搜索search, searching搜索策略searchingstrategy搜索树searching tree搜索算法searchingalgorithm搜索算法的效率efficiency of searchalgorithm搜索图searching graph算符、算子、操作符operator图graph图表示法graph notation图搜索graph search图搜索控制策略graph-search controlstrategy推导表，引导图derivation graph推理inference推理reasoning推理机reasoning machine谓词predicate谓词逻辑predicatelogic谓词演算predicatecalculus谓词演算公式wffs ofpredicate calculus谓词演算辖域domainin predicate calculus文字literal问题归约problem-reduction问题求解problemsolving析取disjunction析取式disjunct线形输入形策略linear-input formstrategy项term学习learning演绎deduction一阶谓词演算firstorder predicate calculus一致解图consistantsolution graph遗传算法geneticalgorithm永真式validity有向图directed graph有序搜索orderedsearch与或树AND/OR tree与或图AND/OR graph与节点AND node原子公式atomicformula蕴涵，蕴涵式implication正向推理forwardreasoning知识knowledge知识工程knowledgeengineering知识获取knowledgeacquisition知识库knowledge base智能intelligence重言式tautology专家系统Expert system状态state状态空间state space子句clause自动定理证明automatic theoremproving组合爆炸combinatorialexplosion祖先过滤形策略ancestry-filtered formstrategy最一般合一most generalunifier最一般合一者mostgeneral unifier最优解树optimalsolution treeaction 动作AI language 人工智能语言ancestry-filtered form strategy 祖先过滤形策略AND node 与节点AND/OR graph 与或图AND/OR tree 与或树answer statement 回答语句artificial intelligence,AI 人工智能artificial neural network 人工神经网络atomic formula 原子公式automatic theorem proving 自动定理证明backed-up value 倒退值backtracking 回溯backward reasoning 逆向推理blind search 盲目搜索，无信息搜breadth-first search 宽度优先搜索B-rule B 规则clause 子句combinatorial explosion 组合爆炸conflict resolution 冲突解决conjunct 合取式conjunction 合取conjunctive normal form 合取范式connective 连词，连接词consistant solution graph一致解图control strategy 控制策略cost 费用deduction 演绎depth-first search 深度优先搜索derivation graph 推导表，引导图difference 差别directed graph 有向图disjunct 析取式disjunction 析取domain in predicate calculus 谓词演算辖域domain of discourse 论域，文字域efficiency of search algorithm 搜索算法的效率empty clause 空子句equivalence 等价estimated cost 估计费用evaluation function 估值函数existential quantifier 存在量词expansion of node 节点的扩展expending node 扩展节点Expert system 专家系统fact 事实first order predicate calculus一阶谓词演算forward reasoning 正向推理F-rule F 规则game 博弈genetic algorithm 遗传算法Global database 全局数据库graph 图graph notation 图表示法graph search 图搜索graph-search control strategy图搜索控制策略heuristic function 启发函数heuristic information 启发信息Heuristic search 启发式搜索heuristic search 启发搜索implication 蕴涵，蕴涵式inference 推理intelligence 智能interpreter 解释器knowledge 知识knowledge acquisition 知识获取knowledge base 知识库knowledge engineering 知识工程learning 学习linear-input form strategy线形输入形策略literal 文字logic逻辑logic connective 逻辑连词logic reasoning 逻辑推理machine learning 机器学习match 匹配match pattern 模式匹配matrix 母式most general unifier 最一般合一most general unifier 最一般合一者NP-complete problem NP完全问题operator 算符、算子、操作符optimal solution tree 最优解树ordered search 有序搜索Pattern recognition 模式识别predicate 谓词predicate calculus 谓词演算predicate logic 谓词逻辑prefix 前缀primitive problem 本原问题problem solving 问题求解problem-reduction 问题归约production 产生式production rule 产生式规则quantifier 量词reasoning 推理reasoning machine 推理机reduction 归约refutation 反演refutation tree 反演树resolution归结resolution principle 归结原理resolution refutation 归结反演resolvent 归结式satisfiability 可满足性scope of quantifier 量词辖域search, searching 搜索searching algorithm 搜索算法searching graph 搜索图searching strategy 搜索策略searching tree 搜索树sentence 句子solution graph 解图solution tree 解树solvable labeling procedure可解标示过程solvable node 可解节点state 状态state space 状态空间substitution 代换substitution instance 代换例tautology 重言式term 项theorem-proving 定理证明uncertainty 不确定性unifier 合一universal quantifier 全称量词unsatisfiable set 不可满足集unsolvable node 不可解节点unsolvable-labelingprocedure不可解标示过程validity 永真式well-formed formula (wff)合适公式、合式公式wffs of predicate calculus谓词演算公式。

八数码问题（一）问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。

这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。

现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。

该问题称八数码难题或者重排九宫问题。

（二）问题分析八数码问题是个典型的状态图搜索问题。

搜索方式有两种基本的方式，即树式搜索和线式搜索。

搜索策略大体有盲目搜索和启发式搜索两大类。

盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。

1、启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。

所以引入启发式搜索策略。

启发式搜索就是利用启发性信息进行制导的搜索。

它有利于快速找到问题的解。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。

所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。

即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

启发函数设定。

对于八数码问题，可以利用棋局差距作为一个度量。

搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。

（三）数据结构与算法设计该搜索为一个搜索树。

为了简化问题，搜索树节点设计如下：struct Chess//棋盘{int cell[N][N];//数码数组int Value;//评估值Direction BelockDirec;//所屏蔽方向struct Chess * Parent;//父节点};int cell[N][N]; 数码数组：记录棋局数码摆放状态。

int Value; 评估值：记录与目标棋局差距的度量值。

Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。

人工智能：Artificial Intelligence，简称AI，主要研究如何使用人工的方法和技术，使用各种自动化机器或智能化机器模仿、延伸和扩展人的智能，实现某些机器思维或脑力劳动自动化。

人工智能的研究目标及其意义：1目标：远期目标是要制造智能机器；近期目标是实现机器智能。

2意义：普遍的计算机智能低下，无法满足社会需求；研究AI是当前信息化社会的迫切需求；智能化是自动化发展的必然趋势；研究AI，对人类自身的智能的奥秘也提供有益的帮助。

人工智能的科学范畴：当前的人工智能既属于计算机技术的一个前沿领域，也属于信息处理和自动化技术的一个前沿领域。

还涉及到智能科学、认知科学、心理科学等，是一门综合性的交叉学科和边缘学科。

人工智能的研究途径与方法：1心里模拟，符号推演2生理模拟，神经计算3行为模拟，控制进化4群体模拟，仿生计算5博采广鉴，自然计算6原理分析，数学建模人工智能的基本技术：1表示2运算3搜索人工智能基于应用的领域：1难题求解2自动规划、调度与配置3机器定理证明4自动程序设计5机器翻译6智能控制7智能管理8智能决策9智能通信10智能仿真11智能CAD12智能制造等人工智能的分支领域：1搜索与图解2学习与发现3知识与推理4发明与创造5感知与交流6记忆与联想7系统与建造8应用与工程人工智能正式诞生于1956年夏，在达特莫斯大学的研究会上，麦卡锡提议正式采用了“AI”这一术语。

麦卡锡---AI之父ＡＩ的现状与发证趋势：１多种途径齐头并进，多种方法协作互补２新思想、新技术不断涌现，新领域新方向不断开拓3理论研究更加深入，应用研究愈加广泛4研究队伍日益壮大，社会影响越来越大。

以上展现了AI繁荣景象和光明前景，虽有困难，问题和挑战，但前进和发展毕竟是大势所趋。

产生式系统的组成：产生式规则库、推理机和动态数据库状态转换规则（操作operator）：1引起状态中某些分量发生改变，从而使一个具体状态变化到另一个具体状态的作用；2它可以是一个机械性的步骤、过程、规则或算子。

图搜索与问题求解实验报告一实验题目图搜索与问题求解二实验目的1熟悉和掌握启发式搜索/A*搜索的定义、估价函数和算法过程；2 理解和掌握搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3 比较并分析图搜索策略的实质，通过实验理解启发式搜索/A*搜索的意义。

三实验要求1以九宫问题/八数码问题为例，以某种启发式搜索/A*搜索策略编程演示其搜索过程；2 定义启发式函数,能正确求解出从初始状态到目标状态的移动路线；3 对不可达状态能进行正确识别；4对所采用的启发式函数做出性能分析。

四数据结构typedef struct Qnode{ //队列的节点类型定义long a; //将8数码转化为长整型后入队列int dnum; //与目标状态数码不同的位置的个数Qnode *next;}*QueuePtr;typedef struct{QueuePtr front; //队头指针QueuePtr rear; //队尾指针}LinkQueue; //链式队列五实验算法1 说明有解和无解如何判定；int NiXu(int a[][3]) //求出所给状态的逆序数{i nt i,j,k=0,sum=0;i nt b[8];f or(i=0;i<3;i++)for(j=0;j<3;j++)if(a[i][j]) //空格用0代替，逆序不计空格b[k++]=a[i][j];for(i=1;i<8;i++)for(j=0;j<i;j++)if(b[i]<b[j])sum++;return sum;}if(NiXu(start)%2 != NiXu(end)%2)printf("无法到达！\n");e lse{printf("广度优先搜索如下：\n\n");search();}2 说明启发式函数如何设定；int h(long x){i nt sum=0;i nt b[3][3];u_trans(x,b);f or (int i=0;i<3;i++)for (int j=0;j<3;j++)if (end[i][j]!=b[i][j])sum++;r eturn sum;}3说明实验中采用的搜索算法。

一、填空题1、人工智能三大学派是（符号主义）、（联结主义）和（行为主义）。

2、设P是谓词公式，对于P的任何论域，存在P为真的情况，则称P为（永真式）。

3、谓词公式G是不可满足的，当且仅当对所有的解释（G都为假）。

4、广度优先搜索算法中，OPEN表的数据结构实际是一个（二叉树），深度优先搜索算法中，OPEN表的数据结构实际是一个（单链表）。

5、产生式系统由三部分组成（综合数据库）、（知识库）和推理机，其中推理可分为（正向推理）和（反向推理）。

6、专家系统的结构包含人机界面、（知识库）、（推理机）、（动态数据库）、（知识库答理系统）和解释模块。

7、开发专家系统所要解决的基本问题有三个，那就是知识的获取、知识的表示和知识的运用，知识表示的方法主要有（逻辑表示法或称谓词表示法）、（框架）、（产生式）和语义网络等，在语义网络表示知识时，所使用的推理方法有（AKO）和（ISA）。

8、从已知事实出发，通过规则库求得结论的产生式系统的推理方式是（正向推理）。

9、AI是（Artifical Inteligence）的缩写。

10、在谓词公式中，紧接于量词之后被量词作用的谓词公式称为该量词的（辖域），而在一个量词的辖域中与该量词的指导变元相同的变元称为（约束变元），其他变元称为（自由变元）。

11、假言推理（A B） A （ B ），假言三段论（A B）（B C）（ A C ）。

12、在诸如走迷宫、下棋、八数码游戏等游戏中，常用到的一种人工智能的核心技术称为（图搜索）技术，解这类问题时，常把在迷宫的位置、棋的布局、八数码所排成的形势用图来表，这种图称为（状态空间图或状态图）。

13、在启发式搜索当中，通常用（启发函数）来表示启发性信息。

14、某产生式系统中的一条规则：A（x） B（x），则前件是（ A（x）），后件是（ B （x））。

15、在框架和语义网络两种知识表示方法中，（框架）适合于表示结构性强的知识，而（语义网络）则适合表示一些复杂的关系和联系的知识。

NCEPU AI pplication⏹人工智能，Artificial Intelligence，简称AI。

⏹人工智能被誉为二十世纪继空间技术、原子能技术后的第三大科学技术成就。

⏹AI是用机器(计算机或智能机)来模仿人类的智能行为。

⏹AI也叫机器智能，是研究如何使机器具有认识问题与解决问题的能力，研究如何使机器具有感知功能、思维功能、行为功能及学习、记忆等功能。

======================================0.0===================================== 知识表示：常用的知识表示方法1．状态空间表示法2．“与/或”图表示法3．产生式规则表示法4．框架表示法5．逻辑表示法6．语义网络表示法知识表示方法的评估原则：有效性、可扩展性、可理解性、清晰性。

1状态空间表示法：概念：所谓状态就是描述某一类事物中各个不同事物之间的差异而引入的最少的一组变量的有序集合。

操作时引起状态中的某些分量发生改变，从而使问题由一个具体状态变化到另一个状态的租用。

描述了状态之间的关系。

问题的状态空间是一个表示该问题的全部可能的状态及其相互关系的图。

所以状态空间常记为三元状态〈S，F，G〉。

初始状态集合、操作集合、目标状态集合。

2与或图表示方法上与下或3产生式规则的格式为：如果，则；前提，结论或者条件推出行动。

结论一般一个条件可以多个。

用产生式规则表示知识所构成的系统称为产生式系统，或称为基于规则的系统。

4框架表示法：5、谓词逻辑例子：用谓词公式表示变电所中负荷的供电状态。

用谓词公式表示拉开刀闸1 的操作。

6语义网络：语义网络是通过概念及其语义关系表示知识的一种网络图。

是由结点、弧和指示器而组成的有向图。

结点：表示所研究领域中的物体、概念、特性值；弧：表示结点之间的关系；指示器：说明结点之间关系（如隶属、性能）的语句。

过程表示法：简言之，依据问题的求解目标，按照事物的发展过程规律，用相关知识加以设计和描述其求解过程的方法，称之为过程表示法。