人工智能--代价树的盲目搜索

左手的ㄟ右手 2022-01-21 11:13 375阅读 0赞

### 文章目录 ###

*  代价树及其代价运算
 *   *  概念
 *  代价树的广度优先搜索
 *   *  算法描述
     *  总结
 *  代价树的深度优先搜索

在一般树的搜索策略中，我们都进行了一种假设，认为状态孔家那种各边的代价都相同，且为一个单位量。 从而使用路径长度代替路径的代价。

但是对许多实际问题，这样的假设是不实际的。例如，城市交通问题，各城市之间的距离不可能是相同的。

# 代价树及其代价运算 #

## 概念 ##

通常，我们把每条边上都标有其代价的树称为代价树。

在代价树中，可以用 g ( n ) g(n) g(n)表示从初始节点 S 0 S\_0 S0到节点`n`的代价，用 c ( n 1 , n 2 ) c(n\_1,n\_2) c(n1,n2)表示从父节点 n 1 n\_1 n1到其子节点 n 2 n\_2 n2的代价。这样，对节点 n 2 n\_2 n2的代价有：  
 g ( n 2 ) = g ( n 1 ) + c ( n 1 , n 2 ) g(n\_2) \\ = \\ g(n\_1) \\ + \\ c(n\_1,n\_2) g(n2)=g(n1)\+c(n1,n2)

通常，在代价树中最小代价的路径和最短路径有可能是不同的。

代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。

# 代价树的广度优先搜索 #

也称分支限界法。每次从`Open`表中选择节点或往`Closed`表中存放节点时总是选择代价最小的节点。

## 算法描述 ##

1.  把初始节点 S 0 S\_0 S0放入`Open`表中
2.  如果`Open`表为空，则问题无解，失败退出
3.  把`Open`表的第一个节点取出，放入`Closed`表，并记该节点为`n`
4.  考察节点`n`是否为目标节点，若是，则得到问题的解，成功退出
5.  若节点`n`不可扩展，则转第二步
6.  扩展节点`n`，将其子节点放入`Open`表的**尾部**，并未每一个子节点设置指向父节点的指针。按如下公式：  
     g ( n 2 ) = g ( n 1 ) + c ( n 1 , n 2 ) g(n\_2) \\ = \\ g(n\_1) \\ + \\ c(n\_1,n\_2) g(n2)=g(n1)\+c(n1,n2)  
    计算各子节点的代价，并根据各节点的代价对`Open`表中的全部节点按照从小到大的顺序重新进行排序。。然后转到第二步。

## 总结 ##

代价树的广度优先策略是完备的，如果问题有解则算法一定能找到它，并且找到的一定是最优解。

![image][]

# 代价树的深度优先搜索 #

算法步骤与广度优先基本相同，区别在于代价树的深度优先搜索每次都是从刚扩展的子节点中选择一个代价最小的节点。

[image]: http://note.youdao.com/yws/res/13915/E04D7F5DB0914275B8A22D20C4FF8D99