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

《第二章 基于搜索的问题求解之对问题进行分割后搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、caughttake“动词”或树BCDEFGAHMBCDEFGAN与或图一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点举例：句子的语法结构与或图设定义下列成分的符号为：R1，名词句，<冠词和名词>R2，谓语，<动词和名词句>R3，主语，<名词句>R4，主语，<代名词>R5，句子，<主语和谓语>R6，代表名词manR7，代表名词mouseR8，代表代名词sheR9，代表动词caughtR10，代表冠词the其中包含在<>括号内的节点是非终叶节点，不包含在<>括号内的节点是终叶节点。一个句子由主语和谓语两种成分按AND关系组成，表示只

3、有当两种成分都存在时，一个句子才能成立。主语成分可由名词句或代名词按OR关系构成，表示这两种成分中随便一种的存在，主语都能成立了。表示句子结构的与/或图句子主语谓语R5代名词R4名词句R3R1冠词名词R10themanmouseR6R7sheR8动词名词句R2caughtR9R1冠词名词themanmouseR6R7R10与/或树的解图与/或树的解图是原来的与/或图的一部分初始节点；对于AND节点，包含其所有子节点；对于OR节点，只包含其中一部分或全部节点；终端节点就是目标节点。上述句子结构与或图的一个解图句子主语谓语代名词she动词名词句caught冠词名词

4、themouse另一个解图句子主语谓语名词句冠词名词theman动词名词句caught冠词名词themouse梵塔难题123CBA解题过程（3个圆盘问题）123123123123123123123123梵塔问题归约图（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（333）2.与或图的搜索与/或图搜索就是从初始节点开始，逐步展开与/或树，获得目标解图的过程。S标记和N标记对于与/或图中，那些是目标的子节点，加上标记S；而

5、那些既不是目标，又无法再继续扩展的子节点，则加上标记N。搜索步骤：把初始节点放入OPEN表。如果OPEN表是空，则求解失败。从OPEN表中取出第一个节点，如果它是目标，则求解成功；如果它不是目标，则继续。扩展该节点，并对子节点进行评估，将除标记为无解N外的所有节点都放入OPEN表。转回第2步。子节点的扩展方法对于AND节点，它的所有子节点都要展开；对于OR节点，它的所有子节点中只要展开其中一个就可以了。节点的评估标准对于AND节点，当它的所有子节点都标记为S时，它可标记为S，只要有一个是N，则它标记为N；对于OR节点，只要它有一个子节点标记为S，它就可以标记为

6、S。有解图及无解图的表示通过上述节点的评估，当初始节点最后标记为S时，得到的图称为有解图；当初始节点经过评估，最后标记为N时，得到的图称为无解图。如果无任何标记时，得到的图为原来的未解图。举例：句子主语谓语代名词she动词名词句caught冠词名词themouseSSSSSSSSSSSS