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

7.1. Общая информация

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

• Метод грубой силы (brute force, полный перебор);
• Метод декомпозиции (decomposition, "разделяй и властвуй");
• Метод уменьшения размера задачи ("уменьшай и властвуй");
• Метод преобразования задачи ("преобразуй и властвуй");
• Жадные алгоритмы (greedy algorithms);
• Методы поиска в пространстве состояний, в том числе:
  • Поиск с возвратом (backtracking);
  • Локальный поиск (local search);
• Динамическое программирование (dynamic programming).

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

7.2. Метод грубой силы

Метод грубой силы (brute force) предполагает поиск решения "в лоб", т.е. без введения каких-то дополнительных построений и лишних концепций. Он оперирует только тем, что дано в условии задачи и известно из определений задействованных понятий.

Некоторые примеры такого подхода:

• нужно найти произведение матриц - умножаем поэлементно, исходя из определения;
• нужно найти элемент в структуре данных - обойдём и проверим каждый (линейный поиск);
• нужно упорядочить элементы от самого меньшего до самого большего - будем отбирать их по одному (сортировка выбором).

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

Пусть дано облако точек на плоскости (географические координаты или набор объектов, характеризуемых двумя параметрами). Необходимо найти пару точек, расстояние между которыми минимально. Алгоритм решения методом грубой силы со сложностью $O(n^2)$:

def closest_pair(points):
    n = len(points)
    min_dist = ∞
    min_pair = None
    for i = 0; i < n; i++:
        for j = i + 1; j < n; j++:
            dist = ((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2) ** 0.5
            if dist < min_dist:
                min_dist = dist
                min_pair = (points[i], points[j])
    return min_pair

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

7.3. Метод декомпозиции

Метод декомпозиции ("разделяй и властвуй") предполагает разбиение исходной задачи на подзадачи, которые решаются отдельно, а затем объединяются в ответ на исходную задачу.