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