1、问题求解的基本方法问题规约 2一 问题规约概念： 把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解 问题的解答就由子问题的解答联合构成 问题归约可以递归地进行，直到把问题变换为本原问题的集合 本原问题就是不可或不需再通过变换化简的 “原子 “问题 3问题归约的描述SP = ( S , O )S-在问题求解（即搜索）过程中所有可达的合法状态 构成的集合O-操作算子的集合，操作算子的执行导致状态的变迁 问题状态可以通过子问题状态的联合加以表示 操作算子的执行则导致问题的 变换 4变换可区分为以下三种情况：（ 1） 状态变迁导致问题从上一状态变迁到下一状态，这就是一般图搜索技术中
2、操作算子的作用（ 2） 问题分解分解问题为需同时处理的子问题，但不改变问题状态（ 3） 基于状态变迁的问题分解先导致状态变迁，再实现问题分解，实际上 就是前二个操作的联合执行 5问题归约的例子：字母重写问题初始状态为字母列表（ A B C），目标状态为只包含字母 x、 y、 z的字母列表操作算子分为两类：（ 1） 面向问题分解，由单一操作算子 Split(n)实现， n是当前问题（子问题）状态节点（ 2） 面向状态变迁，设计为字母列表的 重写规则 ： 6(A) (D F), (A) (G)，(B C) (E)， (B) (H)，(C) (I J K)， (D) (x)，(E) (y z)， (F) (x y z)，(G) (z)， (H) (x x)，(I) (y y)， (J) (z z)，(K) (x z)。 7求解重写问题的与或图 8(A B C) (A)(B C),(A B C) (A)(B)(C),(A)(D) (F),(A)(G)，(B C)(E) ，(B)(H)，(C)(I)(J)(K) 。 9紧凑的与或图 10结论在字母重写问题的规约过程中，各子问题相互独立，所以子问题的进一步归约和本原问题的求解无交互作用，可按任意次序进行 然而，对于其他复杂的问题，还需要考虑各子问题求解的 次序
