tmp.md

TMP

Методы разработки алгоритмов

1) Метод грубой силы (Brute-force) (Полный перебор, исчерпывающий поиск)

Прямой подход к решению задачи.

2) Разделяй и властвуй (Divide and Conquer) (Метод декомпозиции)

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

Где применяется:

• в различных сортировках (Quick sort, external merge sort, ...)
• алгоритм быстрых преобразований Фурье (в аудио кодеках)

3) Динамическое программирование (Dynamic Programming)

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

Существует два подхода к разработке таких алгоритмов:

1) Сверху-вниз (Top-down) (Memoization)

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

2) Снизу-вверх (Bottom-up) (Tabulation)

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

Где применяется:

• Сравнение данных (Longest Common Subsequence)
• Graph Algorithms (Поиск кратчайшего расстояния)
• Machine Learning (Искусственные нейронные сети (алгоритм обратного распространения ошибки)).

4) Жадный алгоритм (Greedy algorithm)

Такой алгоритм это популярный метод для задач оптимизации заключающийся в неком "близоруком" рассмотре данных. Суть в следующем - сначала мы сортируем данные по какому-то принципу, если это как-то поможет, а дальше мы циклически выбираем лучший вариант из тех что есть под рукой предполагая что в конечном счете получим оптимальное решение. (Например задача о непрерывном рюкзаке (Knapsack problem)).

Где применяется:

• в сжатии (jpeg, mp3, gzip)
• Data Analisys
• Graph Algorithms

5) Поиск с возвратом (Backtrecking)

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

Расширенный вариант этого метода - метод ветвей и границ (Branch and Bound).

Где применяется:

• в куче абстрактных оптимизационных задач (маршрутизация, компьютерное зрение и тд)

6) Локальный поиск (Local Search)

Еще один метод для задач оптимизации. Для примера можно рассмотреть задачу "Hill Climbing".

Где применяется:

• Machine Learning

7) Преобразуй и властвуй (Transform and Conquer)

Суть метода в том что бы преобразовать имеющуюся задачу в другую задачу, например, более простую, а потом решить её. Преобразуют либо саму задачу либо её данные.

Где применяется:

• в системах управления базами данных (DBMS)

Итоги

• Brute-force - перебирайте все варианты.
• Divide and Conquer - разбивайте задачи на подзадачи.
• Dynamic Programing - кэшируйте что-то.
• Greedy Algorythn - пытайтесь взять что-то выгодное в первую очередь.
• Backtrecking - пытайтесь оптимизировать Brute-force отменяя отдельные операции.
• Local Search - пытайтесь выбрать решение которое, по крайней мере, не хуже предыдущего.
• Transform and Conquer - преобразуйте данные что бы подружить их со "странной библиотекой".