搜索概念

1. 状态空间大小

如果在一个给定的世界中有$n$个变量对象，它们可以分别取$x_1, x_2, \ldots, x_n$个不同的值，那么状态的总数就是$x_1 \cdot x_2 \cdot \ldots \cdot x_n$。

2. 状态空间图与搜索树

$a.$状态搜索图

状态空间图的构建方式是：状态代表节点，从一个状态到其子状态存在有向边。这些边代表动作，任何相关的权重代表执行相应动作的成本。注意，在状态空间图中，每个状态只被表示一次。

这是因为搜索图中，每一个状态代表的是问题中的唯一、确定的某个系统配置（例如位置、物品、状态等），而我们只需要表示它一次。这个状态不是某个动作后的临时中间产物，而是问题中的一个“里程碑”。

$b.$搜索树

搜索树中对一个状态可以出现的次数没有这样的限制。这是因为虽然搜索树也是一类以状态为节点、动作为状态之间边的图，但每个状态/节点不仅编码状态本身，还编码了从开始状态到状态空间图中给定状态的整个路径。由于从一个状态到另一个状态通常存在多种方式，状态在搜索树中往往会多次出现。因此，搜索树的大小大于或等于其对应的状态空间图。