Выбор правильной методики проектирования для параллельного алгоритма является наиболее сложной и важной задачей. Большинство проблем параллельного программирования может иметь более одного решения. В этой главе мы обсудим следующие методы проектирования параллельных алгоритмов:
- Разделяй и властвуй
- Жадный метод
- Динамическое программирование
- Откат
- Филиал & Связанный
- Линейное программирование
Метод разделяй и властвуй
В подходе «разделяй и властвуй» проблема делится на несколько небольших подзадач. Затем подзадачи решаются рекурсивно и объединяются, чтобы получить решение исходной задачи.
Подход «разделяй и властвуй» включает в себя следующие шаги на каждом уровне —
-
Разделить — исходная проблема делится на подзадачи.
-
Завоевать — Подзадачи решаются рекурсивно.
-
Объединить — Решения подзадач объединяются, чтобы получить решение исходной проблемы.
Разделить — исходная проблема делится на подзадачи.
Завоевать — Подзадачи решаются рекурсивно.
Объединить — Решения подзадач объединяются, чтобы получить решение исходной проблемы.
Подход «разделяй и властвуй» применяется в следующих алгоритмах:
- Бинарный поиск
- Быстрая сортировка
- Сортировка слиянием
- Целочисленное умножение
- Матричная инверсия
- Матричное умножение
Жадный метод
В жадном алгоритме оптимизации решения наилучшее решение выбирается в любой момент. Жадный алгоритм очень легко применить к сложным задачам. Он решает, какой шаг обеспечит наиболее точное решение на следующем шаге.
Этот алгоритм называется жадным, потому что когда предоставляется оптимальное решение для меньшего экземпляра, алгоритм не учитывает всю программу в целом. Как только решение рассматривается, жадный алгоритм никогда не рассматривает то же самое решение снова.
Жадный алгоритм работает рекурсивно, создавая группу объектов из наименьших возможных составных частей. Рекурсия — это процедура для решения проблемы, в которой решение конкретной проблемы зависит от решения меньшего экземпляра этой проблемы.
Динамическое программирование
Динамическое программирование — это метод оптимизации, который делит проблему на более мелкие подзадачи, и после решения каждой подзадачи динамическое программирование объединяет все решения, чтобы получить окончательное решение. В отличие от метода «разделяй и властвуй», динамическое программирование многократно использует решение подзадач.
Рекурсивный алгоритм для рядов Фибоначчи является примером динамического программирования.
Алгоритм возврата
Backtracking — это метод оптимизации для решения комбинационных задач. Он применяется как для программных, так и для реальных задач. Проблема восьмерки, головоломка судоку и прохождение лабиринта — популярные примеры использования алгоритма возврата.
В обратном порядке мы начнем с возможного решения, которое удовлетворяет всем необходимым условиям. Затем мы переходим на следующий уровень и, если этот уровень не дает удовлетворительного решения, мы возвращаемся на один уровень назад и начинаем с новой опции.
Ветвь и Связка
Алгоритм ветвления и ограничения — это метод оптимизации, позволяющий получить оптимальное решение проблемы. Он ищет лучшее решение для данной проблемы во всем пространстве решения. Границы оптимизируемой функции объединяются со значением самого последнего лучшего решения. Это позволяет алгоритму полностью находить части пространства решений.
Цель поиска по ветвям и привязкам — поддерживать путь к цели с наименьшими затратами. Как только решение найдено, оно может продолжать улучшать решение. Поиск ветвей и границ реализован в поиске с ограничением по глубине и поиском по глубине.
Линейное программирование
Линейное программирование описывает широкий класс задач оптимизации, где и критерий оптимизации, и ограничения являются линейными функциями. Это метод получения наилучшего результата, например, максимальной прибыли, кратчайшего пути или минимальной стоимости.
В этом программировании у нас есть набор переменных, и мы должны присваивать им абсолютные значения, чтобы удовлетворить набор линейных уравнений и максимизировать или минимизировать заданную линейную целевую функцию.