一、问题状态描述

1．状态（State）的基本概念

状态（state）是为描述某类不同事物间的差别而引入的一组最少变量q₀，q₁，…，q_n的有序集合，其矢量形式如下：

Q=［q₀，q₁，…，q_n］^T （2.1）

式中每个元素q_i（i=0，1，…，n）为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如

Q_k=［q_0k，q_1k，…，q_nk］^T （2.2）

问题：状态是为描述某类不同事物间的差别而引入的一组最少变量的集合。
A.正确 B.错误

算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。

问题的状态空间（state space）是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态（S，F，G）。

问题：问题的状态空间（state space）是一个表示该问题全部可能状态及其关系的图。
A.正确 B.错误

问题：我们生活中玩棋类游戏时，每一个棋局可以看作一个状态，每一个走步可以看作一个算符。

2．状态空间的表示法

对一个问题的状态描述，必须确定3件事：

① 该状态描述方式，特别是初始状态描述；

② 操作符集合及其对状态描述的作用；

③ 目标状态描述的特性。

二、状态图示法

1．图的基本概念

图由节点（不一定是有限的节点）的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图（directed graph）。某个节点序列（n_i1，n_i2，…，n_ik）当j=2，3，…，k时，如果对于每一个n_i，j-1都有一个后继节点n_ij存在，那么就把这个节点序列叫做从节点n_i1至节点n_ik的长度为k的路径。

代价（cost）是给各弧线指定数值以表示加在相应算符上的代价。

图的显式说明 是指各节点及其具有代价的弧线由一张表明确给出。

图的隐式说明 是指各节点及其具有代价的弧线不能由一张表明确给出。

1 2