第3章(搜索推理技术3-与或树搜索).pptx

人工智能
Artificial Intelligence (AI)
刘静
******@sdutcm.
理工学院
2009年春季
第3章搜索原理
图的搜索策略
盲目搜索
启发式搜索
与或树搜索(补充)
博弈树搜索(补充)
消解原理
与或树搜索(补充)
问题归约法
原始问题
中间问题
本原问题集
操作符
与或图
起始节点
中间节点
终叶节点
生成“与”、“或”后继节点的有向弧
1、终叶节点是可解的(因为它们与本原问题相关联的)
2、如果某一个非终叶节点含有“或”后继节点,那么,只要有一个后继节点是可解的,这一个非终叶节点就是可解的
3、如果某一个非终叶节点含有“与”后继节点,那么,只要所有后继节点是可解的,这一个非终叶节点才是可解的
可解节点的定义是(递归地):
1、没有后裔的非终叶节点是不可解节点
2、如果某一个非终叶节点含有“或”后继节点,那么,只要当所有的后继节点都不可解时,这一个非终叶节点才是不可解的
3、如果某一个非终叶节点含有“与”后继节点,那么,只要有一个后继节点是不可解的,这一个非终叶节点就是不可解的
不可解节点的定义(递归地)是:
根据可解与不可解节点的递归定义,用递归的方式作用于某一个与或图,以标出所有的可解节点与不可解节点
可解标志过程与不可解标志过程:
若初始节点被标志为可解节点,算法成功结束(有解)
若起始节点被标志为不可解节点,则搜索失败结束(无解)
算法结束的条件:
与或图的解图:
由最少的可解节点所构成的子图,这些节点能够使问题的起始节点是可解的
与或树:除了起始节点,每一个节点只有一个父节点
与或图:除了起始节点,每一个节点允许有多个父节点
两者的关系:与或树是与或图的特例
约定:当一个节点生成后继节点时,它们是搜索过程中没有产生过的节点,并且以后也不会再生成它们。(每一个节点只允许生成一次)