Учебники

DAA – разделяй и властвуй

Многие алгоритмы по своей природе являются рекурсивными для решения данной проблемы, рекурсивно решая подзадачи.

При подходе «разделяй и властвуй» проблема делится на более мелкие проблемы, затем меньшие проблемы решаются независимо, и, наконец, решения небольших проблем объединяются в решение большой проблемы.

Как правило, алгоритмы «разделяй и властвуй» состоят из трех частей:

  • Разделите проблему на несколько подзадач, которые являются небольшими экземплярами одной и той же проблемы.

  • Покорите подзадачи , решая их рекурсивно. Если они достаточно малы, решите подзадачи как базовые.

  • Объедините решения подзадач в решение исходной задачи.

Разделите проблему на несколько подзадач, которые являются небольшими экземплярами одной и той же проблемы.

Покорите подзадачи , решая их рекурсивно. Если они достаточно малы, решите подзадачи как базовые.

Объедините решения подзадач в решение исходной задачи.

Плюсы и минусы подхода «разделяй и властвуй»

Подход «разделяй и властвуй» поддерживает параллелизм, поскольку подзадачи независимы. Следовательно, алгоритм, который разработан с использованием этого метода, может работать в многопроцессорной системе или на разных машинах одновременно.

При таком подходе большинство алгоритмов разрабатываются с использованием рекурсии, поэтому управление памятью очень высоко. Для рекурсивной функции используется стек, где необходимо сохранить состояние функции.

Применение подхода «разделяй и властвуй»

Ниже приведены некоторые проблемы, которые решаются с использованием подхода «разделяй и властвуй».