第二章 基于搜索的问题求解之对问题进行分割后搜索.ppt

1、2.4 对问题进行分割后进行搜索,问题分割的实质： 从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题分割为一个平凡的本原问题集合。,1. 与/或(AND/OR)图表示,与图,A,B,C,D,与图,例如,“句子”与树,句子,主语,谓语,“句子”与树,例如,“谓语”与树,谓语,动词,名词句,“谓语”与树,例如,“名词句”与树,名词句,冠词,名词,“名词句”与树,或图,A,B,C,或图,例如，“主语”或树,主语,名词句,代名词,“主语”或树,例如，“名词”或树,名词,man,mouse,“名词”或树,例如，“代名词”或树,代名词,she,he,“代名词”或树,例如

2、，“动词”或树,动词,caught,take,“动词”或树,与或图,一些关于与或图的术语,举例：句子的语法结构与或图,设定义下列成分的符号为： R1， 名词句， R2，谓语， R3，主语， R4，主语， R5，句子， R6，代表名词man R7，代表名词mouse R8，代表代名词she R9，代表动词caught R10，代表冠词the,其中包含在括号内的节点是非终叶节点，不包含在括号内的节点是终叶节点。 一个句子由主语和谓语两种成分按AND关系组成，表示只有当两种成分都存在时，一个句子才能成立。 主语成分可由名词句或代名词按OR关系构成，表示这两种成分中随便一种的存在，主语都能成立了。,表

3、示句子结构的与/或图,句子,主语,谓语,R5,代名词,R4,名词句,R3,R1,冠词,名词,R10,the,man,mouse,R6,R7,she,R8,动词,名词句,R2,caught,R9,R1,冠词,名词,the,man,mouse,R6,R7,R10,与/或树的解图,与/或树的解图是原来的与/或图的一部分 初始节点； 对于AND节点，包含其所有子节点； 对于OR节点，只包含其中一部分或全部节点； 终端节点就是目标节点。,上述句子结构与或图的一个解图,句子,主语,谓语,代名词,she,动词,名词句,caught,冠词,名词,the,mouse,另一个解图,句子,主语,谓语,名词句,冠词,

4、名词,the,man,动词,名词句,caught,冠词,名词,the,mouse,梵塔难题,解题过程（3个圆盘问题）,梵塔问题归约图,（322） （333）,2. 与或图的搜索,与/或图搜索就是从初始节点开始，逐步展开与/或树，获得目标解图的过程。,S标记和N标记,对于与/或图中，那些是目标的子节点，加上标记S； 而那些既不是目标，又无法再继续扩展的子节点，则加上标记N。,搜索步骤：,把初始节点放入OPEN表。 如果OPEN表是空，则求解失败。 从OPEN表中取出第一个节点，如果它是目标，则求解成功；如果它不是目标，则继续。 扩展该节点，并对子节点进行评估，将除标记为无解N外的所有节点都放入OPEN表。 转回第2 步。,子节点的扩展方法,对于AND节点，它的所有子节点都要展开； 对于OR节点，它的所有子节点中只要展开其中一个就可以了。,节点的评估标准,对于AND节点，当它的所有子节点都标记为S时，它可标记为S，只要有一个是N，则它标记为N； 对于OR节点，只要它有一个子节点标记为S，它就可以标记为S。,有解图及无解图的表示,通过上述节点的评估，当初始节点最后标记为S时，得到的图称为有解图； 当初始节点经过评估，最后标记为N时，得到的图称为无解图。 如果无任何标记时，得到的图为原来的未解图。