Вычислительные и комбинаторные алгоритмы

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

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

Для изображения комбинаторных алгоритмов удобным математическим аппаратом является теория графов.

5.4. Поиск решения комбинаторной задачи.

Процесс поиска решения комбинаторной задачи может быть представлен графом типа дерево.

x₁ 0_й уровень

x₂ x₃ x₄ 1_й уровень

x₅ x₆ x₇ x₈ x₉ x₁₀ 2_й уровень

n-1_й уровень

n_й уровень

Корень дерева (вершина 0_го уровня) – это ситуация, в которой мы находимся перед работой алгоритма. Из нее мы можем перейти в одну из ситуаций 1_го уровня и так далее. Вершины n_го нижнего уровня - это решения. Такие вершины называются целевыми. Вообще говоря, целевые вершины не обязательно должны располагаться на одном уровне, но это всегда можно сделать путем введения фиктивных вершин.

Требуется среди целевых вершин выбрать вершину, соответствующую оптимальному решению.

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

Поэтому поступают следующим образом. Находясь в ситуации, соответствующей некоторой вершине x i_го уровня, приписывают смежным с x вершинам i+1_го уровня количественную оценку. После этого выбирают на i+1_м уровне вершину y с максимальной оценкой. Так находясь в корне дерева – вершине x₁, мы оцениваем вершины x_2, x₃, x₄. Если, например, вершина x₄ получила максимальную оценку, то на следующем шаге алгоритма выбирается вершина y=x₄ и оцениваются вершины x₈, x₉, x₁₀.

Ситуации, связанные с вершинами x₂ и x₃, не рассматриваются, то есть ребра х₁-х₂ и х₁-х₃ обрываются. Таким образом, каждый раз переходя из вершины х в вершину у, мы обрываем оставшиеся ребра, исходящие из х, тем самым существенно сокращая дерево перебора.

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

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

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