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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.4,对问题进行分割后进行搜索,子问题1,子问题,n,原始问题,子问题集,本,原,问,题,问题分割的实质：,从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问,题分割为一个平凡的本原问题集合。,1.与/或(AND/OR)图表示,与图,A,B,C,D,与图,例如,“,句子,”,与树,句子,主语,谓语,“句子”与树,例如,“,谓语,”,与树,谓语,动词,名词句,“谓语”与树,例如,“,名词句,”,与树,名词句,冠词,名词,“名词句”与树,或图,A,B,C,或图,例如，“主语”或树,主语,名词句,代名词,“主语”或树,例如，“名词”或树,名词,man,mouse,“名词”或树,例如，“代名词”或树,代名词,she,he,“代名词”或树,例如，“动词”或树,动词,caught,take,“动词”或树,B,C,D,E,F,G,A,H,M,B,C,D,E,F,G,A,N,与或图,一些关于与或图的术语,H,M,B,C,D,E,F,G,A,N,父节点,与节点,弧线,或,节点,子节点,终叶节点,举例：句子的语法结构与或图,设定义下列成分的符号为：,R1，名词句，,R2，谓语，,R3，主语，,R4，主语，,R5，句子，,R6，代表名词man,R7，代表名词mouse,R8，代表代名词she,R9，代表动词caught,R10，代表冠词the,其中包含在括号内的节点是,非终叶节点,，不包含在括号内的节点是,终叶节点,。,一个句子由主语和谓语两种成分按,AND,关系组成，表示只有当两种成分都存在时，一个句子才能成立。,主语成分可由名词句或代名词按,OR,关系构成，表示这两种成分中随便一种的存在，主语都能成立了。,表示句子结构的与/或图,句子,主语,谓语,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,另一个解图,句子,主语,谓语,名词句,冠词,名词,the,man,动词,名词句,caught,冠词,名词,the,mouse,梵塔难题,1,2,3,C,B,A,解题过程（3个圆盘问题）,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,梵塔问题,归约图,（,113,）（,123,）,（,111,）（,113,）,（,123,）（,122,）,（,111,）（,333,）,（,122,）（,322,）,（,111,）（,122,）,（,322,）（,333,）,（,321,）（,331,）,（,322,）（,321,）,（,331,）（,333,）,2.与或图的搜索,与/或图搜索就是从初始节点开始，逐步展开与/或树，获得目标解图的过程。,S标记和N标记,对于与/或图中，那些是目标的子节点，加上标记S；,而那些既不是目标，又无法再继续扩展的子节点，则加上标记N。,搜索步骤：,把初始节点放入OPEN表。,如果OPEN表是空，则求解失败。,从OPEN表中取出第一个节点，如果它是目标，则求解成功；如果它不是目标，则继续。,扩展该节点，并对子节点进行评估，将除标记为无解N外的所有节点都放入OPEN表。,转回第2 步。,子节点的扩展方法,对于AND节点，它的所有子节点都要展开；,对于OR节点，它的所有子节点中只要展开其中一个就可以了。,节点的评估标准,对于AND节点，当它的所有子节点都标记为S时，它可标记为S，只要有一个是N，则它标记为N；,对于OR节点，只要它有一个子节点标记为S，它就可以标记为S。,有解图及无解图的表示,通过上述节点的评估，当初始节点最后标记为S时，得到的图称为有解图；,当初始节点经过评估，最后标记为N时，得到的图称为无解图。,如果无任何标记时，得到的图为原来的未解图。,举例：,句子,主语,谓语,代名词,she,动词,名词句,caught,冠词,名词,the,mouse,S,S,S,S,S,S,S,S,S,S,S,S,