“分而治之”和“分支-约减”算法有什么区别？
从Fomin和Kratsch的“Exact Exponential Algorithms”中可以看出，“分支-约减”算法使用两种类型的规则：
- 减少规则：用于简化问题实例或停止算法； - 分支规则：通过递归地解决较小的问题实例来解决问题。
对我来说，这听起来很像维基百科上给出的“分而治之”的定义：
"分而治之"（D&C）是一种基于多分支递归的算法设计模式。分治算法通过递归地将一个问题分成两个或更多的与原问题相同或相似的子问题，直到这些子问题变得足够简单，可以直接求解。
然而，当将“分支-约减”算法（如k-satisfiability或计算最大独立集）与“分而治之”算法（如快速排序和归并排序）进行比较时，它们在感觉上并不相同。
那么，“分而治之”和“分支-约减”算法有什么区别？如果有的话，是什么特点使它们不同呢？
从Fomin和Kratsch的“Exact Exponential Algorithms”中可以看出，“分支-约减”算法使用两种类型的规则：
- 减少规则：用于简化问题实例或停止算法； - 分支规则：通过递归地解决较小的问题实例来解决问题。
对我来说，这听起来很像维基百科上给出的“分而治之”的定义：
"分而治之"（D&C）是一种基于多分支递归的算法设计模式。分治算法通过递归地将一个问题分成两个或更多的与原问题相同或相似的子问题，直到这些子问题变得足够简单，可以直接求解。
然而，当将“分支-约减”算法（如k-satisfiability或计算最大独立集）与“分而治之”算法（如快速排序和归并排序）进行比较时，它们在感觉上并不相同。
那么，“分而治之”和“分支-约减”算法有什么区别？如果有的话，是什么特点使它们不同呢？