分而治之与分支和归约有什么区别。
根据 Fomin 和 Kratsch 的精确指数算法，分支和归约算法使用两种类型的规则:
- A reduction rule is used to simplify a problem instance or halt the algorithm
- A branching rule is used to solve a problem instance by recursively solving smaller instances of a problem.
对我来说，这听起来很像维基百科上给出的分而治之的定义:
divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
然而，当比较分支算法和归约算法(如 k-可满足性或计算最大独立集)与分而治之算法(如快速排序和归并排序)时，我觉得它们并不相同。
那么分治法和分支归约法有区别吗？如果是这样，什么特征使它们不同。
最佳答案
分而治之算法划分输入。分支和归约算法划分解空间。
关于algorithm - 分而治之、分支和归约有什么区别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41140614/