智能决策支持系统和智能技术的决策支持.ppt

《智能决策支持系统和智能技术的决策支持.ppt》由会员分享，可在线阅读，更多相关《智能决策支持系统和智能技术的决策支持.ppt（216页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、智能决策支持系统和智能决策支持系统和智能技术的决策支持智能技术的决策支持第4章 目录n4.14.1人工智能基本原理人工智能基本原理n4.24.2专家系统与智能决策支持系统专家系统与智能决策支持系统n4.34.3神经网络的决策支持神经网络的决策支持n4.4 4.4 遗传算法的决策支持遗传算法的决策支持n4.5 4.5 机器学习的决策支持机器学习的决策支持4.1 4.1 人工智能基本原理人工智能基本原理n1 1、人工智能的决策支持技术、人工智能的决策支持技术 n n从智能决策支持系统的概念可知智能决策支持系统从智能决策支持系统的概念可知智能决策支持系统从智能决策支持系统的概念可知智能决策支持系统从

2、智能决策支持系统的概念可知智能决策支持系统中包含了人工智能技术，与决策支持有关的人工智中包含了人工智能技术，与决策支持有关的人工智中包含了人工智能技术，与决策支持有关的人工智中包含了人工智能技术，与决策支持有关的人工智能技术主要有：能技术主要有：能技术主要有：能技术主要有：n n专家系统、神经网络、遗传算法、机器学习、自专家系统、神经网络、遗传算法、机器学习、自专家系统、神经网络、遗传算法、机器学习、自专家系统、神经网络、遗传算法、机器学习、自然语言理解等。然语言理解等。然语言理解等。然语言理解等。n n专家系统专家系统专家系统专家系统n n是利用大量的专门知识解决特定领域中的实际问题的计算机

3、程序是利用大量的专门知识解决特定领域中的实际问题的计算机程序是利用大量的专门知识解决特定领域中的实际问题的计算机程序是利用大量的专门知识解决特定领域中的实际问题的计算机程序系统；系统；系统；系统；n n神经网络神经网络神经网络神经网络n n是利用神经元的信息传播模型（是利用神经元的信息传播模型（是利用神经元的信息传播模型（是利用神经元的信息传播模型（MPMPMPMP模型）进行学习和应用；模型）进行学习和应用；模型）进行学习和应用；模型）进行学习和应用；n n遗传算法遗传算法遗传算法遗传算法n n是模拟生物遗传过程的群体优化搜索方法；是模拟生物遗传过程的群体优化搜索方法；是模拟生物遗传过程的群体

4、优化搜索方法；是模拟生物遗传过程的群体优化搜索方法；n n机器学习机器学习机器学习机器学习n n是让计算机模拟和实现人类的学习，获取解决问题的知识；是让计算机模拟和实现人类的学习，获取解决问题的知识；是让计算机模拟和实现人类的学习，获取解决问题的知识；是让计算机模拟和实现人类的学习，获取解决问题的知识；n n自然语言理解自然语言理解自然语言理解自然语言理解n n是让计算机理解和处理人类进行交流的自然语言。是让计算机理解和处理人类进行交流的自然语言。是让计算机理解和处理人类进行交流的自然语言。是让计算机理解和处理人类进行交流的自然语言。4.1人工智能基本原理人工智能基本原理n n2 2 2 2智

5、能决策支持系统结构形式智能决策支持系统结构形式智能决策支持系统结构形式智能决策支持系统结构形式 n n1 1 1 1）基本结构）基本结构）基本结构）基本结构n n智能决策支持系统（智能决策支持系统（智能决策支持系统（智能决策支持系统（IDSSIDSSIDSSIDSS）决策支持系）决策支持系）决策支持系）决策支持系统（统（统（统（DSSDSSDSSDSS）人工智能（）人工智能（）人工智能（）人工智能（AIAIAIAI）技术）技术）技术）技术 4.1人工智能基本原理人工智能基本原理问题综合与交互系统数据库管理系统模型库管理系统模型库数据库人工智能技术专家系统神经网络遗传算法机器学习自然语言理解图4

6、.1 智能决策支持系统的基本结构图4.2 智能决策支持系统结构问题综合与交互系统模型库管理系统数据库管理系统知识库管理系统推理机用户模型库知识库数据库人工智能技术可以概括为：推理机知识库人工智能技术可以概括为：推理机知识库人工智能技术可以概括为：推理机知识库人工智能技术可以概括为：推理机知识库 智能决策支持系统的结构可以简化为图智能决策支持系统的结构可以简化为图智能决策支持系统的结构可以简化为图智能决策支持系统的结构可以简化为图4.24.24.2人工智能基本原理人工智能基本原理n4.2.1逻辑推理逻辑推理n4.2.2知识表示与知识推理知识表示与知识推理n4.2.3搜索技术搜索技术4.2.1 4

7、.2.1 逻辑推理逻辑推理1.1.形式逻辑形式逻辑(人的思维形式、规律人的思维形式、规律)（1）概念：反映事物的特有属性和属性的取值。（2）判断：对概念的肯定或否定；判断本身有对有错；判断有全称的肯定（或否定）判断和存在的肯定（或否定）判断。（3）推理：从一个或多个判断推出一个新判断的过程。4.2.1逻辑推理逻辑推理2.2.推理的种类推理的种类演绎推理归纳推理类比推理假言推理三段论推理数学归纳法假言易位推理枚举归纳推理1 1）演绎推理演绎推理演绎推理演绎推理：从一般现象到个别（特殊）现象的推理。：从一般现象到个别（特殊）现象的推理。：从一般现象到个别（特殊）现象的推理。：从一般现象到个别（特殊

8、）现象的推理。2 2）归纳推理归纳推理归纳推理归纳推理：从个别（特殊）现象到一般现象的推理。：从个别（特殊）现象到一般现象的推理。：从个别（特殊）现象到一般现象的推理。：从个别（特殊）现象到一般现象的推理。3 3）类比推理类比推理类比推理类比推理：从个别（特殊）现象到个别（特殊）现象的推理。：从个别（特殊）现象到个别（特殊）现象的推理。：从个别（特殊）现象到个别（特殊）现象的推理。：从个别（特殊）现象到个别（特殊）现象的推理。1）演绎推理 专家系统的研究基本上属于演绎推理范畴。演绎推理的核心是假言推理。假言推理：以假言判断为前提，对该假言判断的前件或后件的推理。1）假言推理：pq，p q 2）

9、三段论推理：pq，qr pr 3）假言易位推理（拒取式）：pq，q p 符号符号“”表示推出表示推出4.2.1逻辑推理逻辑推理 2）归纳推理(个别一般)（1）数学归纳法 这种推导是严格的，结论是确实可靠的。（2）枚举归纳推理 S1是P，S2是P，Sn是P S1Sn是S类事物中的部分分子，没有相反事例。所以，S类事物都是P。枚举归纳推理的结论是或然的(并非必然地)，它的可靠性和事例数量相关。4.2.1逻辑推理逻辑推理枚举归纳推理实例 如观察到铁受热膨胀、铜受热膨胀等事实而不知其所以然，由此推出“所有金属受热膨胀”的结论就是简单枚举归纳推理。3）类比推理它是由两个（或两类）事物在某某些些属属性性上

10、上相相同同，进而推断它们在另一个属性另一个属性上也可能相同相同的推理。A事物有abcd属性,B事物有abc属性（或a,b,c相似属性）所以，B事物也可能有d属性（或d相似属性）类类比比推推理理的的结结论论带带有有或或然然性性，它它的的可可靠靠性性和和相相类类比事物属性之间的联系程度有关比事物属性之间的联系程度有关。4.2.1逻辑推理逻辑推理类比推理实例一 1816年的一天，法国医生雷奈克出诊为一位年轻的女性看病，一见病人，雷奈克犯起愁来：她身体非常肥胖，要诊断她的心脏和肺部是否正常，按当时医生惯用的方法，把耳朵贴近病人的胸部来听，肯定听不清楚，更何况她是一位年轻的女性。雷奈克抬头看了看院子里正

11、在玩耍的小孩，脑子里突然浮现出几年前看到一个孩子们玩的游戏：一个孩子用钉子敲打木板的一头，另外的孩子争先恐后地抱着把耳朵贴近木板的另一头，兴致勃勃地倾听着。为什么木头能够把声音清晰地传过来呢？雷奈克稍微想了想，只见他很很地拍了一下手说：“就是这样！就是这样！”雷奈克要来一叠纸，紧紧地卷成一个卷，然后把纸卷的一端放在姑娘的胸部，另一端放在自己的耳朵上，侧着脸听了起来。“真是一个妙法！”雷奈克高兴地喊了一句。回到家里，雷奈克找到一根木棒，造成了历史上第一个“听诊器”。类比推理实例一类比推理实例二 19世纪30年代，英国商人威尔斯以与冯灿的茂隆皮箱商行订购的皮箱中有不是皮的木料为由，向香港法院起诉，

12、蓄意敲诈冯灿。针对这种情况，冯灿的律师罗文锦取出口袋的金怀表，高声问法官：“请问这是什么表？”法官答道：“这是金表，可是这与本案有什么关系？”罗文锦高举金表，面对法庭上 所 有 的 人 说：“有 关 系。这 是 金 表，没 有 人 怀 疑 是吧？但是，请问，这块金表除表面镀金之外，内部的机制都是金制吗？”旁听者同声议论：“当然不是。”罗文锦继续说：“那么人们为什么又叫它金表呢？”稍作停顿又高声说：“由此可见，茂隆行的皮箱案不过是原告无理取闹、存心敲诈而已”原告理屈词穷，法庭最后以威尔斯诬告，罚款5000元结案 皮箱诉讼案的法庭辩论中，卖方律师在反驳中所使用的就是类比推理：表的外表有金，内部含有

13、不是金的材料，但却是金表；箱的外表有皮，但也含有不是皮的材料；所以，箱仍是皮箱。类比推理实例二 3.总结 1 1）演演绎绎推推理理的的结结论论没没有有超超出出已已知知的的知知识识范范围围。而而归纳推理和类比推理的结论归纳推理和类比推理的结论超出超出已知的知识范围。已知的知识范围。演绎推理只能解释一般规律中的个别现象演绎推理只能解释一般规律中的个别现象演绎推理只能解释一般规律中的个别现象演绎推理只能解释一般规律中的个别现象 而而而而归归归归纳纳纳纳推推推推理理理理和和和和类类类类比比比比推推推推理理理理创创创创造造造造了了了了新新新新的的的的知知知知识识识识，使使使使科科科科学学学学得得得得到到

14、到到新新新新发展，是一种创造思维方式。发展，是一种创造思维方式。发展，是一种创造思维方式。发展，是一种创造思维方式。2 2）演演绎绎推推理理中中由由于于前前提提和和结结论论有有必必然然联联系系，只只要要前提为真，结论一定为真。前提为真，结论一定为真。归归归归纳纳纳纳推推推推理理理理和和和和类类类类比比比比推推推推理理理理中中中中前前前前提提提提和和和和结结结结论论论论，不不不不能能能能保保保保证证证证有有有有必必必必然然然然联联联联系系系系，具具具具有有有有或或或或然然然然性性性性。这这这这样样样样推推推推理理理理的的的的结结结结论论论论未未未未必必必必是是是是可可可可靠靠靠靠的的的的。需需需

15、需要要要要经经经经过过过过严严严严格格格格的的的的验验验验证证证证和和和和证证证证明明明明，使之形成新的理论。使之形成新的理论。使之形成新的理论。使之形成新的理论。4.2.1逻辑推理逻辑推理4.2.2知识表示与知识推理知识表示与知识推理n4.2.2.1数理逻辑表示法数理逻辑表示法(自学自学)n4.2.2.1产生式规则产生式规则n4.2.2.3语义网络语义网络n4.2.2.4框架框架n4.2.2.5剧本剧本(自学自学)4.2.2.24.2.2.2 产生式规则（产生式规则（ifAthenB）n1.正向推理正向推理n n逐条搜索规则库，对每一条规则的前提条件，检查逐条搜索规则库，对每一条规则的前提条

16、件，检查逐条搜索规则库，对每一条规则的前提条件，检查逐条搜索规则库，对每一条规则的前提条件，检查事实库事实库事实库事实库中是否存在。中是否存在。中是否存在。中是否存在。n n前提条件中各子项，若在事实库中前提条件中各子项，若在事实库中前提条件中各子项，若在事实库中前提条件中各子项，若在事实库中不是全部存在不是全部存在不是全部存在不是全部存在，放弃该条规则。若在事实库中放弃该条规则。若在事实库中放弃该条规则。若在事实库中放弃该条规则。若在事实库中全部存在全部存在全部存在全部存在，则执行该，则执行该，则执行该，则执行该条规则，把条规则，把条规则，把条规则，把结论结论结论结论放入放入放入放入事实库事

17、实库事实库事实库中。中。中。中。n n反复循环执行上面过程，直至推出目标，并存入反复循环执行上面过程，直至推出目标，并存入反复循环执行上面过程，直至推出目标，并存入反复循环执行上面过程，直至推出目标，并存入事事事事实库实库实库实库中为止。中为止。中为止。中为止。1.ABG2.CDA3.EDB,C,E4.2.2.2产生式规则产生式规则事实库的最后状态为：事实库的最后状态为：B，C，E，D，A，G产生式规则库产生式规则库事实库事实库产生式规则库和事实库的初始状态为：产生式规则库和事实库的初始状态为：4.2.2.24.2.2.2 产生式规则产生式规则n逆逆(反反)向推理向推理n n逆向推理是从目标开

18、始，寻找以逆向推理是从目标开始，寻找以逆向推理是从目标开始，寻找以逆向推理是从目标开始，寻找以此目标为结论此目标为结论此目标为结论此目标为结论的规则的规则的规则的规则n n对该规则的前提进行判断对该规则的前提进行判断对该规则的前提进行判断对该规则的前提进行判断，若该规则的前提中某个子，若该规则的前提中某个子，若该规则的前提中某个子，若该规则的前提中某个子项是另一规则的结论时，再找以此结论的规则。项是另一规则的结论时，再找以此结论的规则。项是另一规则的结论时，再找以此结论的规则。项是另一规则的结论时，再找以此结论的规则。n n重复以上过程，直到对某个规则的前提能够进行判断。重复以上过程，直到对某

19、个规则的前提能够进行判断。重复以上过程，直到对某个规则的前提能够进行判断。重复以上过程，直到对某个规则的前提能够进行判断。按此规则前提判断（按此规则前提判断（按此规则前提判断（按此规则前提判断（“是是是是”或或或或“否否否否”）得出结论的判断，）得出结论的判断，）得出结论的判断，）得出结论的判断，由此回溯到上一个由此回溯到上一个由此回溯到上一个由此回溯到上一个 规则的推理，一直回溯到目标的规则的推理，一直回溯到目标的规则的推理，一直回溯到目标的规则的推理，一直回溯到目标的判断。判断。判断。判断。GADEBC4.2.2.2产生式规则产生式规则逆向推理中，目标改变过程：逆向推理中，目标改变过程：1

20、.ABG2.CDA3.EDB,C,E产生式规则库产生式规则库事实库事实库4.2.3 4.2.3 搜索技术搜索技术n搜索技术是人工智能的一个重要研究内容。智能技搜索技术是人工智能的一个重要研究内容。智能技术体现在术体现在减少搜索树中的盲目搜索减少搜索树中的盲目搜索。n n1.1.1.1.执执执执行行行行时时时时间间间间与与与与，等等等等成成成成正正正正比比比比的的的的算算算算法法法法，称称称称为为为为按按按按多多多多项项项项式时间执行式时间执行式时间执行式时间执行。n n2.2.2.2.执执执执行行行行时时时时间间间间与与与与，！和和和和等等等等成成成成正正正正比比比比的的的的算算算算法法法法，

21、称称称称为为为为按按按按指指指指数时间执行数时间执行数时间执行数时间执行。按多项式时间执行的算法，计算机是可以实现的。按多项式时间执行的算法，计算机是可以实现的。按指数时间执行的算法，计算机是不可能实现的。按指数时间执行的算法，计算机是不可能实现的。4.2.3 4.2.3 搜索技术搜索技术n人人工工智智能能中中发发展展了了一一种种称称为为启启发发式式搜搜索索方方法法，基基本本思思想想可可用用一个实例来说明：一个实例来说明：n n一一一一个个个个外外外外地地地地人人人人到到到到某某某某城城城城市市市市出出出出差差差差，他他他他想想想想到到到到书书书书店店店店看看看看看看看看，又又又又不不不不知知

22、知知书书书书店店店店在在在在何何何何处处处处，如如如如果果果果采采采采取取取取盲盲盲盲目目目目搜搜搜搜索索索索，从从从从住住住住地地地地出出出出发发发发沿沿沿沿任任任任一一一一方方方方向向向向走走走走，在分叉路口又任选一分支走，他可能走几天几夜也找不到在分叉路口又任选一分支走，他可能走几天几夜也找不到在分叉路口又任选一分支走，他可能走几天几夜也找不到在分叉路口又任选一分支走，他可能走几天几夜也找不到n n如如如如果果果果采采采采用用用用启启启启发发发发式式式式方方方方法法法法，他他他他会会会会问问问问路路路路上上上上的的的的人人人人，到到到到书书书书店店店店怎怎怎怎样样样样走走走走。城市中的大

23、部分人对书店不知道，问不出来。城市中的大部分人对书店不知道，问不出来。城市中的大部分人对书店不知道，问不出来。城市中的大部分人对书店不知道，问不出来。4.2.3 4.2.3 搜索技术搜索技术n n改改改改一一一一种种种种问问问问法法法法：问问问问该该该该城城城城市市市市最最最最热热热热闹闹闹闹的的的的地地地地方方方方在在在在哪哪哪哪儿儿儿儿？按按按按照照照照这这这这个个个个启发式信息沿着指路人的路线，乘车到达最热闹的地方启发式信息沿着指路人的路线，乘车到达最热闹的地方启发式信息沿着指路人的路线，乘车到达最热闹的地方启发式信息沿着指路人的路线，乘车到达最热闹的地方n n但但但但书书书书店店店店在

24、在在在哪哪哪哪儿儿儿儿，仍仍仍仍然然然然不不不不知知知知道道道道。如如如如果果果果盲盲盲盲目目目目搜搜搜搜索索索索，可可可可能能能能仍仍仍仍然然然然找找找找不不不不到到到到。如如如如果果果果采采采采用用用用启启启启发发发发式式式式方方方方法法法法，他他他他会会会会问问问问路路路路上上上上的的的的人人人人，卖卖卖卖画画画画的地方在哪儿，他可以通过画店再问书店在哪儿？的地方在哪儿，他可以通过画店再问书店在哪儿？的地方在哪儿，他可以通过画店再问书店在哪儿？的地方在哪儿，他可以通过画店再问书店在哪儿？n n启启启启发发发发式式式式方方方方法法法法能能能能减减减减少少少少大大大大量量量量盲盲盲盲目目目目

25、无无无无效效效效的的的的搜搜搜搜索索索索，能能能能有有有有效效效效克克克克服服服服按按按按指数时间执行的组合爆炸现象指数时间执行的组合爆炸现象指数时间执行的组合爆炸现象指数时间执行的组合爆炸现象4.2.3 4.2.3 搜索技术搜索技术n搜索方法分类：搜索方法分类：n n1 1 1 1、基本搜索法、基本搜索法、基本搜索法、基本搜索法n n（1 1 1 1）广度优先搜索法。）广度优先搜索法。）广度优先搜索法。）广度优先搜索法。n n（2 2 2 2）深度优先搜索法。）深度优先搜索法。）深度优先搜索法。）深度优先搜索法。n n2 2 2 2、生成测试法。、生成测试法。、生成测试法。、生成测试法。n

26、n3 3 3 3、爬山法。、爬山法。、爬山法。、爬山法。n n4 4 4 4、启发式搜索。、启发式搜索。、启发式搜索。、启发式搜索。n n5 5 5 5、博弈算法。、博弈算法。、博弈算法。、博弈算法。（1 1）极小极大搜索法。）极小极大搜索法。（2 2）剪枝算法。剪枝算法。4.2.3.14.2.3.1 广度优先搜索（宽度优先搜索）广度优先搜索（宽度优先搜索）1 1、广度优先搜索思想、广度优先搜索思想 n n从初始状态从初始状态从初始状态从初始状态S S S S开始，开始，开始，开始，利用规则利用规则利用规则利用规则，生成所有可能的状态生成所有可能的状态生成所有可能的状态生成所有可能的状态。构成

27、树的下一层节点，检查是否出现目标状态构成树的下一层节点，检查是否出现目标状态构成树的下一层节点，检查是否出现目标状态构成树的下一层节点，检查是否出现目标状态G G G G，若，若，若，若未出现，就对该层所有状态节点，分别顺序利用规未出现，就对该层所有状态节点，分别顺序利用规未出现，就对该层所有状态节点，分别顺序利用规未出现，就对该层所有状态节点，分别顺序利用规则。则。则。则。n n生成再下一层的所有状态节点，对这一层的所有状生成再下一层的所有状态节点，对这一层的所有状生成再下一层的所有状态节点，对这一层的所有状生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现态节点检查是否出现态节

28、点检查是否出现态节点检查是否出现G G G G，若未出现，继续按上面思想，若未出现，继续按上面思想，若未出现，继续按上面思想，若未出现，继续按上面思想生成再下一层的所有状态节点生成再下一层的所有状态节点生成再下一层的所有状态节点生成再下一层的所有状态节点.n n这样一层一层往下展开。直到这样一层一层往下展开。直到这样一层一层往下展开。直到这样一层一层往下展开。直到出现目标状态出现目标状态出现目标状态出现目标状态G G G G为止。为止。为止。为止。图图4.7广度优先搜索示意图广度优先搜索示意图（2 2）算法）算法1)1)把初始节点把初始节点S S0 0故入故入OPENOPEN表。表。2)2)如

29、果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出 。3)3)把把OPENOPEN表的第一个节点表的第一个节点(记为节点记为节点n)n)取出放入取出放入CLOSEDCLOSED表。表。4)4)考察节点考察节点n n是否为目标节点。若是，则求得了问是否为目标节点。若是，则求得了问题的解，退出。题的解，退出。5)5)若节点若节点n n不可扩展，则转第不可扩展，则转第2)2)步。步。6)6)扩展节点扩展节点n n，将其子节点放入，将其子节点放入OPENOPEN表的尾部，并表的尾部，并为每一个子节点都配置指向父节点的指针，然后为每一个子节点都配置指向父节点的指针，然后转第转第2)2

30、)步。步。广度优先搜索过程开始把n的后继节点放入OPEN表的末端，提供返回节点n的指针把S放入OPEN表OPEN表为空表？是失败否把第一个节点（n）从OPEN移至CLOSED表n为目标节点？是成功否n能否扩展是否有任何后继节点为目标节点否是是否例子1(八数码难题)重排九宫问题，在重排九宫问题，在3x33x3的方格棋盘上放置分别标有数的方格棋盘上放置分别标有数字字1 1、2 2、3 3、4 4、5 5、6 6、7 7、8 8共共8 8个棋子，初始状态个棋子，初始状态为为S S0 0，目标状态为，目标状态为S Sg g，如图，如图1 1所示。所示。可使用的算符有：可使用的算符有：空格左移，空格上移

31、，空格右移，空格下移。即空格左移，空格上移，空格右移，空格下移。即只允许把位于空格左、上、右、下的邻近棋子移入只允许把位于空格左、上、右、下的邻近棋子移入空格。要求寻找从初始状态到目标状态的路径。空格。要求寻找从初始状态到目标状态的路径。该该路路径径使使用用的的算算符符序序列列：空空格格上上移移，空空格格左左移移，空空格格下下移移，空格右移。空格右移。广广度度优优先先搜搜索索的的盲盲目目性性较较大大，当当目目标标节节点点距距离离初初始始节节点点较较远远时时将将会会产产生生许许多多无无用用节节点点，因因此此搜搜索索效效率率低低，但但是是，只只要要问问题题有有解解，用用广广度度优优先先搜搜索索总总

32、可以得到解，而且得到的是路径最短的路径。可以得到解，而且得到的是路径最短的路径。由图由图2可以看出，解的路径是：可以看出，解的路径是：S0381626广度优先法适合于搜索树的宽度较小的问题。广度优先法适合于搜索树的宽度较小的问题。1 1、深度优先搜索法思想、深度优先搜索法思想 n n从从从从初初初初始始始始状状状状态态态态S S S S开开开开始始始始，利利利利用用用用规规规规则则则则生生生生成成成成搜搜搜搜索索索索树树树树下下下下一一一一层层层层任任任任一一一一个个个个结结结结点点点点，检检检检查查查查是是是是否否否否出出出出现现现现目目目目标标标标状状状状态态态态G G G G，若若若若未

33、未未未出出出出现现现现，以以以以此此此此状状状状态态态态利利利利用用用用规规规规则则则则生生生生成成成成再再再再下下下下一一一一层层层层任任一一个个结结结结点点点点，再再再再检检检检查查查查是是是是否否否否为为为为目目目目标标标标节节节节点点点点G G G G。若若若若未未未未出出出出现现现现，继继继继续续续续以以以以上上上上操操操操作作作作过过过过程程程程，一一一一直直直直进进进进行行行行到到到到叶叶叶叶节节节节点点点点（即即即即不不不不能能能能再再再再生生生生成成成成新新新新状状状状态态态态节节节节点点点点）。n n当当当当它它它它仍仍仍仍不不不不是是是是目目目目标标标标状状状状态态态态G

34、 G G G时时时时，回回回回溯溯溯溯到到到到上上上上一一一一层层层层结结结结果果果果，取取取取另一可能扩展搜索的分支。生成新状态节点。另一可能扩展搜索的分支。生成新状态节点。另一可能扩展搜索的分支。生成新状态节点。另一可能扩展搜索的分支。生成新状态节点。n n一直进行下去，直到找到目标状态一直进行下去，直到找到目标状态一直进行下去，直到找到目标状态一直进行下去，直到找到目标状态G G G G为止。为止。为止。为止。4.2.3.2深度优先搜索法深度优先搜索法图图4.8深度优先搜索示意图深度优先搜索示意图（2 2）算法）算法1)1)把初始节点把初始节点S S0 0故入故入OPENOPEN表。表。

35、2)2)如果如果OPENOPEN表为空，则问题无解，退出表为空，则问题无解，退出 。3)3)把把OPENOPEN表的第一个节点表的第一个节点(记为节点记为节点n)n)取出放入取出放入 CLOSEDCLOSED表。表。4)4)考察节点考察节点n n是否为目标节点。若是，则求得了问是否为目标节点。若是，则求得了问题的解，退出。题的解，退出。5)5)若节点若节点n n不可扩展，则转第不可扩展，则转第2)2)步。步。6)6)扩展节点扩展节点n n，将其全部子节点放入到，将其全部子节点放入到OPENOPEN表的首部，表的首部，并为其配置指向父节点的指针，然后转第并为其配置指向父节点的指针，然后转第2)2

36、)步。步。开始把S放入OPEN表OPEN表为空表？是失败否把第一个节点（n）从OPEN移至CLOSED表是否有任何后继节点为目标节点是成功否扩展n,把n的后继节点放入OPEN表的前头，提供返回节点n的指针s为目标节点？否是深深度度优优先先搜搜索索例子2：对图对图1 1所示的重排九宫问题进行深度优先搜索，可得到图所示的重排九宫问题进行深度优先搜索，可得到图3 3所示的搜索树这只是搜索树的一部分，尚未到达目标节点，仍所示的搜索树这只是搜索树的一部分，尚未到达目标节点，仍需继续往下搜索。需继续往下搜索。在深度优先搜索中，搜索一旦进入某个分支，就在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一

37、直向下搜索。如果目标节点恰好在此将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，分支上，则可较快地得到解。但是，如果目标节点不如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不能在此分支上，而该分支又是一个无穷分支，则就不能得到解。得到解。所以深度优先搜索是不完备的，即使问题有所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。显然，解，它也不一定能求得解。显然，用深度优先求得的用深度优先求得的解，也不一定是路径最短的解。解，也不一定是路径最短的解。深度优先法适合于搜索树的深度较小的问题4.2.3.34.2.3.3 生成测试法生成测试法n生成测试

38、法算法是：生成测试法算法是：n n1 1 1 1、生成一个可能状态节点。、生成一个可能状态节点。、生成一个可能状态节点。、生成一个可能状态节点。n n2 2 2 2、测试该状态是否为目标状态。、测试该状态是否为目标状态。、测试该状态是否为目标状态。、测试该状态是否为目标状态。n n3 3 3 3、若是目标状态则结束。否则回到第、若是目标状态则结束。否则回到第、若是目标状态则结束。否则回到第、若是目标状态则结束。否则回到第1 1 1 1步步步步n n其中：生成可能的状态，可以是有规律的，也可以其中：生成可能的状态，可以是有规律的，也可以其中：生成可能的状态，可以是有规律的，也可以其中：生成可能的

39、状态，可以是有规律的，也可以是无规律的是无规律的是无规律的是无规律的4.2.3.34.2.3.3 生成测试法生成测试法n n（1 1）如果搜索过程中，）如果搜索过程中，）如果搜索过程中，）如果搜索过程中，总是利用刚生成出的状态来生总是利用刚生成出的状态来生总是利用刚生成出的状态来生总是利用刚生成出的状态来生成新状态成新状态成新状态成新状态，这种生成测试法就是，这种生成测试法就是，这种生成测试法就是，这种生成测试法就是深度优先深度优先深度优先深度优先搜索法。搜索法。搜索法。搜索法。n n（2 2）如如如如果果果果搜搜搜搜索索索索过过过过程程程程中中中中，总总总总是是是是利利利利用用用用旧旧旧旧状

40、状状状态态态态生生生生成成成成所所所所有有有有可可可可能能能能出出出出新新新新状状状状态态态态，而而而而且且且且状状状状态态态态节节节节点点点点以以以以从从从从旧旧旧旧到到到到新新新新的的的的顺顺顺顺序序序序逐逐逐逐个个个个生生生生成成成成的原则。这种生成测试法就是的原则。这种生成测试法就是的原则。这种生成测试法就是的原则。这种生成测试法就是广度优先广度优先广度优先广度优先搜索法。搜索法。搜索法。搜索法。n n（3 3）如如如如果果果果搜搜搜搜索索索索过过过过程程程程中中中中，有有有有时时时时利利利利用用用用旧旧旧旧状状状状态态态态生生生生成成成成新新新新状状状状态态态态，有有有有时时时时利利

41、利利用用用用新新新新状状状状态态态态生生生生成成成成新新新新状状状状态态态态，这这这这就就就就是是是是无无无无规规规规律律律律的的的的生生生生成成成成测测测测试法。试法。试法。试法。4.2.3.44.2.3.4 爬山法爬山法(生成测试法的变种生成测试法的变种)n爬山算法：爬山算法：(测试函数测试函数)n n1.1.1.1.开始状态作为一个可能状态。开始状态作为一个可能状态。开始状态作为一个可能状态。开始状态作为一个可能状态。n n2.2.2.2.从一个可能状态，应用从一个可能状态，应用从一个可能状态，应用从一个可能状态，应用规则规则规则规则生成所有新的可能状态集。生成所有新的可能状态集。生成所

42、有新的可能状态集。生成所有新的可能状态集。n n3.3.3.3.对该状态集中每一状态，进行如下操作：对该状态集中每一状态，进行如下操作：对该状态集中每一状态，进行如下操作：对该状态集中每一状态，进行如下操作：n n 对该状态测试，检查是否为目标，是则停止。对该状态测试，检查是否为目标，是则停止。对该状态测试，检查是否为目标，是则停止。对该状态测试，检查是否为目标，是则停止。n n 计算该状态的好坏，或者比较各状态的好坏。计算该状态的好坏，或者比较各状态的好坏。计算该状态的好坏，或者比较各状态的好坏。计算该状态的好坏，或者比较各状态的好坏。n n4.4.4.4.取状态集中最好状态，作为下一个可能

43、状态。取状态集中最好状态，作为下一个可能状态。取状态集中最好状态，作为下一个可能状态。取状态集中最好状态，作为下一个可能状态。n n5.5.5.5.循环到第循环到第循环到第循环到第2 2 2 2步。步。步。步。在爬山法中可能出现以下几种情况：在爬山法中可能出现以下几种情况：局部极大点：它比局部极大点：它比周围邻居周围邻居状态都好，但不是目标。状态都好，但不是目标。图图4.9局部极大点示意图局部极大点示意图在爬山法中可能出现以下几种情况：在爬山法中可能出现以下几种情况：平顶：它与平顶：它与全部邻居全部邻居状态都有状态都有同同一个值，构成一个一个值，构成一个 平面。平面。图图4.10平顶示意图平顶

44、示意图在爬山法中可能出现以下几种情况：在爬山法中可能出现以下几种情况：山脊：它与山脊：它与线状邻居线状邻居状态有相同值，比其它邻居状状态有相同值，比其它邻居状态要好。态要好。图图4.11山脊示意图山脊示意图4.2.3.44.2.3.4 爬山法爬山法n为了解决以上问题，需要采用如下策略：为了解决以上问题，需要采用如下策略：n n（1 1）退退退退回回回回到到到到某某某某一一一一更更更更早早早早状状状状态态态态结结结结点点点点，沿沿沿沿着着着着另另另另一一一一方方方方向向向向（对对对对该结点就不一定是当时最好值的方向）进行爬山。该结点就不一定是当时最好值的方向）进行爬山。该结点就不一定是当时最好值

45、的方向）进行爬山。该结点就不一定是当时最好值的方向）进行爬山。n n（2 2）朝朝朝朝一一一一个个个个方方方方向向向向前前前前进进进进一一一一大大大大步步步步（按按按按某某某某方方方方向向向向深深深深度度度度优优优优先先先先搜搜搜搜索多次），走出平顶区，按别方向进行爬山。索多次），走出平顶区，按别方向进行爬山。索多次），走出平顶区，按别方向进行爬山。索多次），走出平顶区，按别方向进行爬山。n n（3 3）同时朝）同时朝）同时朝）同时朝两个或多个方向两个或多个方向两个或多个方向两个或多个方向前进，即按两个或多个前进，即按两个或多个前进，即按两个或多个前进，即按两个或多个方向爬山。方向爬山。方向爬

46、山。方向爬山。4.2.3.54.2.3.5 启发式搜索启发式搜索n启发式搜索是对每个在搜索过程中遇到的启发式搜索是对每个在搜索过程中遇到的新状态新状态，用一个用一个估计函数估计函数（启发式函数）并计算其值的大（启发式函数）并计算其值的大小，确定下一步将从哪一个状态开始继续前进。小，确定下一步将从哪一个状态开始继续前进。n n一般以一般以一般以一般以估计值小者为较优估计值小者为较优估计值小者为较优估计值小者为较优的状态，以此实行最的状态，以此实行最的状态，以此实行最的状态，以此实行最优搜索。优搜索。优搜索。优搜索。n n估计函数值的大小与从估计函数值的大小与从估计函数值的大小与从估计函数值的大小

47、与从初始状态到达目标状态初始状态到达目标状态初始状态到达目标状态初始状态到达目标状态的路径有关。的路径有关。的路径有关。的路径有关。4.2.3.54.2.3.5 启发式搜索启发式搜索n具体需要考虑以下具体需要考虑以下问题问题：n n（1 1）下一步选择哪个状态结点？）下一步选择哪个状态结点？）下一步选择哪个状态结点？）下一步选择哪个状态结点？n n（2 2）是是是是部部部部分分分分展展展展开开开开几几几几个个个个状状状状态态态态结结结结点点点点还还还还是是是是全全全全部部部部展展展展开开开开所所所所有有有有可可可可能能能能产产产产生生生生的状态结点？的状态结点？的状态结点？的状态结点？n n（

48、3 3）使用哪个规则（或算子）来展开新状态结点？）使用哪个规则（或算子）来展开新状态结点？）使用哪个规则（或算子）来展开新状态结点？）使用哪个规则（或算子）来展开新状态结点？n n（4 4）怎样决定舍弃还是保留新生成的状态结点？）怎样决定舍弃还是保留新生成的状态结点？）怎样决定舍弃还是保留新生成的状态结点？）怎样决定舍弃还是保留新生成的状态结点？n n（5 5）如何定义启发式函数（估计值函数）？）如何定义启发式函数（估计值函数）？）如何定义启发式函数（估计值函数）？）如何定义启发式函数（估计值函数）？n n（6 6）如何决定搜索方向？）如何决定搜索方向？）如何决定搜索方向？）如何决定搜索方向？

49、n n（7 7 7 7）怎样决定停止或继续搜索？）怎样决定停止或继续搜索？）怎样决定停止或继续搜索？）怎样决定停止或继续搜索？一般启发式函数法用如下公式表示：一般启发式函数法用如下公式表示：f（x）=g（x）+h（x）ff（x x）表示由开始状态到目标状态的总耗费表示由开始状态到目标状态的总耗费表示由开始状态到目标状态的总耗费表示由开始状态到目标状态的总耗费g g（x x）表示开始状态到当前状态的耗费。表示开始状态到当前状态的耗费。表示开始状态到当前状态的耗费。表示开始状态到当前状态的耗费。hh（x x）表示当前状态到目标状态的耗费。表示当前状态到目标状态的耗费。表示当前状态到目标状态的耗费。

50、表示当前状态到目标状态的耗费。4.2.3.5启发式搜索启发式搜索启发式函数分析：启发式函数分析：n n1.1.当当当当h h（x x）=0=0，即，即，即，即f f（x x）=g=g（x x）取取取取f f（x x）为为为为最最最最小小小小，即即即即取取取取g g（x x）为为为为最最最最小小小小。这这这这要要要要求求求求在在在在已已已已扩扩扩扩展展展展的的的的结结结结点点点点中中中中取取取取最最最最佳佳佳佳路路路路径径径径。g g（x x）能能能能保保保保证证证证找找找找到到到到最最最最好好好好解解解解。但对搜索速度没有太多的帮助。但对搜索速度没有太多的帮助。但对搜索速度没有太多的帮助。但对