RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology人工智能原理(符号计算科学)PrinciplesofArtificialIntelligenceRuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology第五章：问题规约策略Chapter05Problem-ReductionApproachRuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01PRA的基本思想Section01theEssentialsofPRARuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01PRA的基本思想1.1PRA与状态空间法Three-S的局限性与状态空间法一样，问题规约方法也是人工智能的一种基于图搜索策略的问题求解方法。问题的表现形式是多样的，甚至是无限的，因此，问题状态的数量可能是巨大的，并非所有的问题都象八数码问题一样，只有9!种可能的状态。从某种意义上说，状态空间法求解问题的过程是状态树生长的过程，是问题状态近乎几何级数地生长的过程，是被搜索的状态空间恶性膨胀的过程RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01PRA的基本思想1.1PRA与状态空间法Three-S的局限性随着状态空间的膨胀，数量巨大的问题状态需要占用计算机大量的资源，包括存储空间和运行时间。特别的，对大的问题或复杂的问题，其状态空间中问题状态的数量之大，甚至可能令当代最大的计算机也难以承受。因此，状态空间法作为一种人工智能问题求解方法，仍然存在一定的局限性，特别是在求解大问题或复杂问题的能力上。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01PRA的基本思想1.2模拟人的复杂问题求解行为PRA面向复杂问题问题规约是人类处理或求解大问题或复杂问题的一种常用的方式。人们常常将大的问题或复杂的问题分解为一系列小的或简单的问题，然后，分别加以处理或求解。一个大的问题常常是由一些小的问题构成的，一个复杂的问题常常是由一些简单问题构成的。这些小的问题或简单的问题就是大问题或复杂问题的子问题。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01PRA的基本思想1.2模拟人的复杂问题求解行为PRA的AI特征问题规约方法模拟人类处理大问题或复杂问题的智能行为，将大问题或复杂问题分解为较小或较简单的问题，将较小或较简单的问题再分解为更小或更简单的问题，直至所有的问题都易于处理或求解为止。最小的问题或具有明显解答的问题被称为本原问题。一般地，本原问题是原始问题的子孙问题。因此，问题规约的过程就是在问题空间中不断搜索问题的子问题和子问题的子问题的过程，直至将原始问题分解为本原问题集合。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01PRA的基本思想1.3规约：化解复杂问题问题规约的基本思想是：将大问题或复杂问题分解为小的或简单的本原问题集合。问题规约方法和状态空间法具有共同的特征，这就是图搜索。问题规约的图搜索过程：在问题空间中，以待求解的原始问题为出发点，以本原问题为目标，不断地搜寻子问题的过程。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02PRA自学要点Section02TheFocusesonSelf-LearningPRARuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02PRA自学要点(一)PRA问题的形式化定义：问题规约方法中的问题被定义为一个四元组：其中：P,O,p(o),p(p)(5.1)(1)P={p}：问题空间(问题的集合)(2)O={O}：算子空间(操作的集合)(3)p(o)P：原始问题(OriginalProblem)(4)p(p)P：本原问题(PrimitiveProblem)应用O中的算子对p(o)进行操作，将原始问题p(o)转化为本原问题集合p(g)的过程称为问题(5.1)的求解。本原问题集合RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02PRA自学要点(一)PRA问题的形式化关于本原问题：所谓本原问题，是指具有明显解答的问题，或有现成...
