Video在线视频

那么我们这种树搜索方法的具体实现是这样的

当然这也是一个伪代码，但是更具体一点

它把一些数据结构考虑进来了

那么看一下我们的树搜索它的输入同样是问题的形式化

以及 刚才是搜索策略，

那么这里 在实现搜索策略的时候它引进了一个fringe表

这个fringe字面意义是边缘，也就是说我们这颗搜索树的边缘

这颗搜索树的边缘也就是这颗搜索树的叶子结点

那么这棵树的叶子结点也就是它的待拓展结点

也就是他还没有探索过的还没有拓展过的结点

就放在这个fringe表里面

然后呢它的输出就是返回一个问题的解，或者是它觉得这个问题没解，失
败，这个和前面一样

然后我们来看一下它具体是怎么实现这个树搜索方法的

首先根据问题的形式化找到问题的初始状态

然后根据初始状态产生一个初始结点

然后把初始结点插入到fringe表里面去

也就是说因为这个初始结点就是第一个待拓展结点

它既是根结点也是叶子结点

然后呢把它放到fringe表中，准备进行拓展

然后接下来就开始搜索循环的主体

首先它看一下fringe表（边缘表）也就是待拓展叶子结点表

先判断它是不是空的，如果是空的就意味着已经没有待拓展节点了

所有的节点，状态空间里面的所有状态我都探索过都没有找到解

那么就意味着没解，所以就失败

否则它就从fringe表中，也就是待拓展结点表中

最前面的一个结点取出来，准备进行拓展

所以这个fringe表就是一个队列

我们把排在前面的结点拿出来优先进行拓展，探索

那么把这个结点拿出来之后

首先判断一下这个结点对应的状态是不是目标状态

也就是说进行目标测试

如果是的话就意味着找到了解

所以就把这个结点对应的这个解呢给它返回去

如果不是那我们就对这个结点进行拓展

那么进行拓展呢，就是通过当前这个结点对应的状态能够执行哪些动作

然后产生一些后续状态就叫做对这个结点进行拓展

然后把拓展产生的后续状态对应的新的结点呢

把它插入到fringe表里面去

也就是说新产生出来的结点成为了新的待拓展结点

成为新的叶子结点放到fringe表里面去

然后放进去之后这一次迭代就结束

然后第二次呢又去做同样的事情

先看一下fringe表里有没有待拓展结点

有的话把排在队首的这个结点取出来

判断一下它是不是目标，不是，对它进行拓展插入到fringe表里面去

所以这个是我们的树搜索方法的一个具体的实现

所以这里，他首先有一个fringe表，fringe表是一个队列表

也就是说这里我们的搜索策略就体现在这个队列表

你是怎么排队的，是选择什么样的一种排序方案

因为它最终要把排在队列表最前面的几点优先取出来进行试探，进行拓展

所以呢这个搜索策略就体现在这个fringe表的排队策略上面

那么这里还有一个就是根据当前结点和问题的形式化

对当前结点进行一个拓展

或者说对当前状态通过后续函数产生后续状态

那么看一下，这个结点的拓展是如何实现的

所以结点拓展函数的输入就是当前结点和问题的形式化

它返回的是一个结点的集合

这个集合就是当前这个结点的后续结点的集合

也就是在我们的搜索树中当前这个是父结点

它产生出来的结点的集合是它的儿子结点

那么看到首先它设了一个变量叫后续结点集

一开始初始化是一个空集合

然后就开始了，对于每一个可执行的动作

也就是说当前结点对应一个状态

对于这个状态能执行的每个动作都产生一个新的结点

产生一个新的后续

就像罗马尼亚问题一样

那么它可以执行走到这个城市产生一个状态

也可以执行走到另一城市产生一个状态

对于它可以执行的每一个动作产生一个新的状态，产生一个新的结点

然后我们来看一下，对它每个能执行的动作

他通过当前结点的状态，以及它能执行的后续函数

你就知道这个这个状态通过执行这个动作会产生一个新的什么样的状态

然后来产生一个新的结点加到这个后续结点里面去

然后这个新的结点怎么产生呢？

首先初始化一个新的结点s空结点

然后这个结点他有这么一些域

也就是说这个结点是一个数据结构，那么这个结点它有这些东西要储存

第一个就是他的父亲结点是谁，它是谁产生的

所以他就记录下来它是当前结点产生的，赋值给它，这个箭头表示赋值

然后这个结点它的ACTION这个域是什么意思呢

就是说我是父亲结点通过执行什么动作产生的

所以给它记录下来放到这个域里面

然后呢再把我对应的这个结点的状态是什么记录下来

那么这个状态就是后续函数你问题的形式化定义知道的

也就是说当前这个结点对应的这个状态

通过执行这个动作会产生什么样的新的状态

这个后续函数定义的，所以把它储存起来

也就是说，这个新的结点对应的状态是什么

然后还要记录下来这个新的结点的路径代价

路径代价就是从初始结点到当前结点路径上代价的总和

那么这个代价的话应该是它父亲结点的代价

也就是从初始结点到它的父亲结点的代价

加上父亲结点到达它所执行这个动作所产生的单步代价

加上父亲结点到达它所执行这个动作所产生的单步代价

那就是我们这个新产生出来的结点的路径代价

还要记录下来这个结点它的深度，它在这棵树的第几层

那么它的深度就是它的父亲结点的深度加一，这个比较容易计算

所以呢把这些都记录下来之后这个新的结点就构造好了

就把它加到这个后续结点里面去

所以每一个可执行的动作产生一个新的状态

由这个新的状态构造一个新的后续结点放到后续结点集里去

然后呢把所有的后续状态、后续结点都产生出来之后就返回去了

那么这个当前结点就拓展完毕

返回到这里之后就把所有新产生出来的后续结点添加到fringe表里去

以便下一次进行拓展，进行搜索

这就是我们的通用树搜索算法或者是一般树搜索方法实现的伪代码

那么这里面我们看到有两个概念我们要区分开来

一个概念就是我们的状态State，另一个概念就是Node就是结点

那么这个状态表示的是一个实际问题物理配置的一个表示

比如说像这里一个八数码问题，状态指的就是这么一个摆放情况

而结点是一个数据结构，是我们在程序实现的时候建立的一个数据结构

它是我们整个搜索算法形成的搜索树的一个组成部分

那么这个结点包含哪些信息呢？也就是说他要储存那些域呢？

第一个就是他要储存它的父亲结点是谁

也就是它是由哪个结点执行哪个动作产生的，这些都要储存下来

它还要储存这个结点所在的深度，所在的层是第几层

那么我们前面讲过它的父亲结点的层数加一就是他所在的层

然后它还要储存从初始结点到当前结点的路径代价是多少

那么也就是说从初始结点到当前结点经过了那些动作

每一个动作的单步代价是多少，累加起来

那么它也可以计算出来

就是从初始状态到达它的父亲结点的这个代价

加上从父亲结点到达自己执行动作的单步代价

就是从初始结点到达它的一个代价

它还要储存对应的状态是那个状态

比如说我这个结点从初始状态执行了这么多动作

到达这个结点，到达这个结点对应的状态是谁

所以呢这个状态只是我们结点的一部分信息

结点还要储存其他的信息