●●。计算机算法基础 分枝一限界法
计算机算法基础 分枝－限界法
●·0预备知识 o问题状态 o状态空间树 o解状态 o活结点 o状态空间 oE结点 o答案状态 o死结点 o等等 o本节主要目的 通过对n-皇后问题的分析,学习以上概念, 并且了解回溯法
0 预备知识 问题状态 解状态 状态空间 答案状态 状态空间树 活结点 E-结点 死结点 等等…… 本节主要目的 通过对n-皇后问题的分析，学习以上概念， 并且了解回溯法
●·。解空间树结构的术语 o树中每个结点确定求解问题的一个问题状态 (problem state) o由根结点到其它结点的所有路径确定了这个 间题的状态空间( state space) 解状态( solution states) 是这样一些问题状 态S,对于这些问题状态,由根到S的那条路 續定了这解空间中的一个元组(满足显式 o答案状态(so! ution states )是这样,些解状 态S,由根到S的路径确定了问题的一个解 (满足隐式约束) o解空间的树结构为状态空间树( state space tree)
解空间树结构的术语 树中每个结点确定求解问题的一个问题状态 (problem state) 由根结点到其它结点的所有路径确定了这个 问题的状态空间(state space) 解状态(solution states)是这样一些问题状 态S，对于这些问题状态，由根到S的那条路 径确定了这解空间中的一个元组（满足显式 约束） 答案状态(solution states)是这样一些解状 态S，由根到S的路径确定了问题的一个解 （满足隐式约束） 解空间的树结构为状态空间树(state space tree)
●·。利用状态空间树解题 o1设想状态空间树 o2生成问题状态 o3确定问题状态中哪些是解状态 o4哪些解状态是答案状态 生成问题状态→构造状态空间树
利用状态空间树解题 1 设想状态空间树 2 生成问题状态 3 确定问题状态中哪些是解状态 4 哪些解状态是答案状态 生成问题状态 → 构造状态空间树
状态空间树术语 ●活结点:自己已经生成而其所有的儿子 结点还没有全部生成的结点。 E结点(正在扩展的结点):当前正在 生成其儿子结点的活结点 死结点:不再进一步扩展或者其儿子结 点已全部生成的生成结点。 静态树( static trees):树结构与所要解 决的问题的实例无关。 动态树( dynamic trees):根据不同的 实例而使用不同的树结构
状态空间树术语 ⚫ 活结点：自己已经生成而其所有的儿子 结点还没有全部生成的结点。 ⚫ E-结点（正在扩展的结点）：当前正在 生成其儿子结点的活结点。 ⚫ 死结点：不再进一步扩展或者其儿子结 点已全部生成的生成结点。 静态树(static trees)：树结构与所要解 决的问题的实例无关。 动态树(dynamic trees)：根据不同的 实例而使用不同的树结构