В чем разница между делением и завоеванием, а также ветвью и уменьшением.В чем разница между делением и завоеванием, а также ветвью и сокращением?
Из точных экспоненциальных алгоритмов Фоминой и Kratsch, ветвь и уменьшить алгоритмы использует два типа правил:
- Правило сокращения используется для упрощения экземпляра проблемы или остановить алгоритм
- ветвящегося правило используется для решения экземпляра проблемы путем рекурсивного решения меньших экземпляров проблемы.
Для меня это звучит очень похоже на определение разделяй и властвуй дается в Википедии:
разделяй и властвуй (D & C) является дизайн алгоритм парадигмы на основе многозабойных рекурсии , Алгоритм деления и покоя работает рекурсивно разбивая проблему на две или более подзадачи того же или родственного типа, пока они не станут достаточно простыми, чтобы их можно было решить напрямую.
Однако при сравнении отрасли и сократить алгоритмы, как к-выполнимости или вычисления максимального независимого множества, разделяй и властвуй алгоритмы, как и сортировки сортировка слиянием, они не чувствуют то же самое для меня.
Так есть разница между делением и завоеванием, а также ветвью и уменьшением? Если да, то какая особенность делает их разными.