简答

1.LC检索是否每次都能选出具有最小结点成本函数得结点作为下一个E结点？简述理由。

答：不能，要满足以下两点，LC检索才可以保证找到最小成本得答案结点（如果存在）

1.对于每一个结点X都有成本估计函数<=C(X)且对于答案结点有，C^(X)=C(X)

2.采用改进后的算法LC1,从活结点表中删除元素时判断是否为答案结点。

2.回溯法和分支-限界法的状态空间生成方式有何不同？简述两种方法的基本思想。

答：（1）回溯法的状态生成方法: 当前的E-结点R 一旦生成一个新的儿子结点C, 这个C结点就变成一个新的E-结点, 当检测完了子树C后, R结点就再次成为E-结点, 生成下一个儿子结点。分支-限界方法的状态生成方法: 一个E-结点一直保持到变成死结点为止。
（2）回溯法：加限界的深度优先生成方法称为回溯法。回溯法在包含问题所有解的解空间树中, 按深度优先的策略, 从根结点出发搜索解空间树。搜索至解空间树的任一结点时, 先判断该结点是否肯定不包含问题的解。如果肯定不包含, 则跳过以该结点为根的子树, 逐层向其祖先结点回溯。否则就进入该子树, 继续按深度优先的策略进行搜索。
分支-限界法：生成当前E-结点全部儿子之后，再生成其他活结点的儿子；使用限界函数帮助避免生成不包含答案结点子树的状态空间。

3.解释下列术语的含义，回溯法运行过程中，状态空间树所有结点没有完全遍历到，但为什么没有丢解？

答：

状态空间树：所求问题的解空间的树结构

显式约束：限定每个x只从一个给定的集合上取值，可以与所求解问题的实例有关也可以无关

隐式约束：规定问题的实例的解空间中的那些实际上满足规范函数的元组，描述了xi必须彼此相关的情况

问题状态：解空间树中的每一个节点确定所求解问题的一个问题状态

解状态：这样一些问题状态S，对于这些问题状态，由根到S的哪条路径确定了这解空间的一个元组。

答案状态：这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（它满足隐式约束条件）

活结点：如果已经生成一结点，而它的所有儿子结点还没有全部生成，则这个结点就叫活结点。

E结点：当前正在生成其儿子节点的活结点

死结点：不再进一步扩展或者其儿子结点已全部生成的结点

限界函数：所求解的问题需要求一个是某一限界函数P（x1，x2……）取极大值（或取极小值或满足该限界函数）的向量，表示问题的约束条件或目标。

加限界的深度优先生成方法称为回溯法。回溯法在包含问题所有解的解空间树中, 按深度优先的策略, 从根结点出发搜索解空间树。搜索至解空间树的任一结点时, 先判断该结点是否肯定不包含问题的解。如果肯定不包含, 则跳过以该结点为根的子树, 逐层向其祖先结点回溯。所以没有遍历的结点都是没有解的，因此不会丢解。

4.给出COOK定理。并简述什么是NP-难度问题，什么是NP-完全问题，什么是NP，什么是P，什么是可满足性问题

答：

COOK定理：可满足性在P内，当且仅当P=NP

NP-难度：如果可满足性约化为一个问题L，则称此问题L是NP-难度的。

NP-完全：如果L是NP难度的而且L属于NP，则称问题L是NP完全的。

P是所有可在多项式时间内用确定算法求解的判定问题的集合，NP是所有可在多项式时间内用不确定算法求解的判定问题的集合

可满足性问题：对于变量的任一一组真值指派确定公式是否为真。

5.给出以比较为基础的检索算法和分类算法的时间下界分别是什么？简要说明理由。

O ( l o g n ) 和 Ω ( n l o g n ) O(logn)和\Omega(nlogn) O(logn)和Ω(nlogn)简要理由不会说
之前有n个内结点对应与x中的n种情况，
最坏的查找也不大于由根到叶子结点的最长路径
而假设最外层内结点在k层，则共有2的k次方剪一的内结点树，而高度2的k次方剪一就大于等于n，k大于等于logn加1取天蓬

6.给出LC分支-限界检索中活结点表使用的数据结构，并阐述LC分支-限界检索的检索策略。

可以使用队列也可以使用堆栈
LC检索是选取成本估计函数值最小的那个作为E-结点
根据所给问题确定解空间，该解空间中至少有一个。解决问题的最优解。
遍历的过程中运用限界函数。避免产生不可能的解的节点。

7.列出用动态规划法求解最短周游路线问题的递推关系式。

答：其实就是货郎担

8.算法有哪些重要特性，算法分析主要包括哪两方面内容？

答：算法：一组有穷的规则，规定了解决某一特定问题的一系列运算。

必须满足的五个特性是

1.有穷性

2.确定性

3.可行性

4.输入

5.输出

算法分析主要包括两方面

1.事前分析：求出该算法的一个时间界限函数

2.事后测试搜集此算法的执行时间和实际占用空间的统计资料

证明题

1.设I是在两台设备上作流水线调度的任一实例，证明对于同一个I，每种POFI调度的长度和每种OFI调度的长度相同，因此6.8的算法也可以生成一种POFI调度。

答：

http://www.doc88.com/p-9734963937737.html

前往此处寻找同样题目

2.证明即使作业有不同的处理时间定理5.3亦真。这里假设作业i的效益P大于0，处理时间大于等于0，期限大于处理时间。

答：定理5.3:设J是K个作业的集合, σ \sigma σ =i1i2…ik是J中作业的一种排序,它使得di1≤di2≤…≤dik .J是一个可行解,当且仅当J中的作业可以按照 σ \sigma σ的次序又不违反任何一个期限的情况下来处理.

di1≤di2≤…≤dik .J是一个可行解,当且仅当J中的作业可以按照 σ \sigma σ的次序又不违反任何一个期限的情况下来处理.

参考作业第五章的PPT