Quelle est la différence entre diviser et conquérir, et ramifier et réduire.Quelle est la différence entre diviser et conquérir, et ramifier et réduire?
De exponentielles Exact algorithmes de Fomin et Kratsch, branche et réduire les algorithmes utilise deux types de règles:
- Une règle de réduction est utilisée pour simplifier une instance de problème ou d'arrêter l'algorithme
- A ramification La règle est utilisée pour résoudre une instance de problème en résolvant récursivement des instances plus petites d'un problème.
Pour moi, cela ressemble beaucoup à la définition de diviser pour mieux régner donnée sur Wikipedia:
diviser pour mieux régner (D & C) est un paradigme de conception algorithme basé sur récursion rameuse . Un algorithme de division et de conquête fonctionne en décomposant récursivement un problème en deux ou plusieurs sous-problèmes du même type ou d'un type apparenté, jusqu'à ce qu'ils deviennent suffisamment simples pour être résolus directement.
Cependant lorsque l'on compare la branche et de réduire les algorithmes, comme k-satisfiability ou le calcul d'un ensemble indépendant maximal, pour diviser et conquérir des algorithmes, comme quicksort et genre de fusion, ils ne se sentent pas la même chose pour moi.
Y a-t-il une différence entre diviser et conquérir, et ramifier et réduire? Si oui, quelle caractéristique les rend différents.