几道算法选择题 几道算法选择题

算法选择题知识点总结 一、分支限界法与回溯法 * 分支限界法和回溯法都是在问题的解空间树 T 上搜索问题的解，二者的区别在于：分支限界法的目标是寻找满足约束条件的解，而回溯法的目标是寻找问题的所有可能解。 * 回溯法在解空间树 T 上的搜索方式是深度优先搜索。 二、回溯算法和分支限界法 * 回溯算法和分支限界法的问题的解空间树不会是有序树，因为解空间树的结构取决于问题的具体定义和约束条件。 * 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是回溯法。 三、分支限界法的搜索方式 * 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，例如队列式分支限界法、优先队列式分支限界法、栈式分支限界法等。 四、概率算法 * 概率算法是一种非确定性地选择下一计算步骤的方法，力图消除问题复杂性与具体实例间的关联。 * 数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍得算法都是概率算法的具体类型。 * 蒙特卡罗算法能够求得问题的近似解，但却无法有效地判定解的正确性。 五、素数测试 * 素数测试的数学原理是费尔马小定理和Wilson 定理。 六、判定问题难易处理 * 判定问题难易处理的标准是：可以由多项式时间算法求解的问题是易处理的，而需要超过多项式时间算法求解的问题是难处理的。 七、函数的阶 * 设 f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数 C 和自然数 N0，使得当N≥N0 时有 f（N）≤Cg（N），则称函数 f（N）当 N 充分大时有上界 g（N），记作f（N）=O（g（N）），即 f（N）的阶不高于g（N）的阶。 八、子集树问题和排列树问题 * 对于含有 n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为2n+1-1。 * 对于含有 n 个元素的排列树问题，最坏情况下计算时间复杂性为n!。 这些算法选择题涵盖了分支限界法、回溯法、概率算法、素数测试、判定问题难易处理和函数的阶等多个方面的知识点，旨在考察读者的算法基础和逻辑思维能力。