文档介绍：该【《与或图搜索问题》 】是由【相惜】上传分享，文档一共【65】页，该文档可以免费在线阅读，需要了解更多关于【《与或图搜索问题》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第二章与或图搜索问题目标目标初始节点sabc编辑课件1第二章与或图搜索问题与或树是用于表示问题及其求解过程的又一种形式化方法。对于一个复杂问题,直接求解往往比较困难,因此通过下述方法进行简化:分解:把一个复杂问题简化为假设干简单的子问题,重复此过程,直到不需要再分解或者不能再分解为止。假设每个子问题都可求解,那么原问题可求解。因此以下图称为“与〞树。PP3P2P1编辑课件2第二章与或图搜索问题等价变换:对于一个复杂问题,除了可用“分解〞方法进行求解外,还可利用同构或同态的等价变换,把它变换为假设干个较为容易求解的新问题。假设新问题中有一个可求解,那么就得到了原问题的解。因此以下图称为“或〞:不能再分解或变换,而且可以直接求解的子问题。端节点与终止节点:没有子节点的节点称为端节点;本原问题所对应的节点称为终止节点。显然,终止节点一定是端节点,但端节点不一定是终止节点。可解节点:满足以下条件之一者,称为可解节点:;“或〞节点,且其子节点中至少有一个是可解节点;“与〞节点,且其子节点中全部都是可解节点。:关于可解节点的三个条件全部不满足的节点称为不可解节点。解树:由可解节点构成,并且由这些节点可推出初始节点〔它对应于原始问题〕为可解节点的子树称为解树。。〔记为节点n)取出放入CLOSED表。,那么作以下工作:,将其子节点放入OPEN表的尾部,并为每个子节点配置指向父节点的指针,以备标识过程使用。。假设有,那么标识这些终止节点为可解节点,并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。如果初始节点S0也被标识为可解节点,就得到了解树,搜索成果,退出搜索过程;如果不能确定S0为可解节点,那么从OPEN表中删去具有可解先辈的节点。。编辑课件8与或树的广度优先搜索〔续〕,那么作以下工作。。,如果初始节点S0也被标识为不可解节点,那么搜索失败,说明原问题无解,退出搜索过程;如果不能确定S0为不可解节点,那么从OPEN表中删去具有不可解先辈的节点。。编辑课件9与或树的广度优先搜索:例如2134t1ABt2t4t35编辑课件10