人工智能第2版学习——知情搜索3

书：人工智能第2版
有需要电子版的可以私信我。

这次学习高级搜索算法那，包括：约束满足搜索、与或树、双向搜索。

约束满足搜索

在AI中，问题简化技术是一个重要方法。直接看下面这个问题：
问题：将Blob移动到vertical bar的另一边。
约束：

1. Blob占用4格，可以上下左右移动。
2. vertical条占用2格，可以上下左右移动。
3. 水平条占用横向的两格，可以上下左右移动。
4. 圆占用一格，可以上下左右移动。
5. 每个格子不能被重复占用。
   
   如果是用一个相对盲目的状态空间搜索，问题求解可能要超过800次移动。
   而如果采用问题简化对待求解的子目标进行识别，如：必须让Blob在垂直条之上或之下的两行内。（此时Blob才能从垂直条的右边移动到左边。）则求解问题只需要82次。

与或树

书中的概念如下：

我的理解就是：如果一个节点，它的子节点如果是与节点，则这个路径可行的条件是必须满足与节点的所有子节点；如果一个节点，它的子节点是或节点，则这个路径可行的条件是只需满足或节点的一个子节点。

我们看一下书给的例子：

图中，B、C、D是或节点。E和F、G和H是与节点。
所以从图可以看出，要骑自行车野餐需要检测自行车和准备食物；要吃晚餐看电影需要餐厅和电影院；要去不错的餐厅不需要有什么条件。
这三种选择是可替代的，但每一种选择(当然第三种没有)都有条件。

双向搜索

前向搜索别认为是一种代价昂贵的过程，它会带来指数级的增长。所以双向搜索的想法是通过前向搜索目标状态，并从已知的目标状态后向搜素到起始状态，看下图：

书中这里还说了一页文字介绍，不知道是翻译有问题还是啥，读起来很难看懂它想表达的意思，就不多说了，感兴趣的去看书吧。
或者可以看看这篇，讲的双向A*算法，挺好理解的。

这次就到这里了，可以点个赞吗？