Порядковая оценка.

Пример 1.

Пузырьковая сортировка.

N(N-1)/2

O(N²)

Пример 2.

Задача коммивояжёра.

Для нахождения кратчайшего цикла Гамильтона необходимо построить все перестановки на множестве вершин V. Для всех перестановок на V:

Вычислить длину цикла.

Если длина цикла меньше минимальной запомнить цикл.

O(N!)

Пример 3.

Задача о двоичном векторе.

AX=B где X – двоичный вектор

Найти X

Задача решается полным перебором всех чисел двоичного числа n.

1. Если двоичное число является решением выйти из цикла. O(2ⁿ)

2. Задать верхнюю и нижнюю границы адресного пространства

Пока адресное пространство существует:

1. Вычислить середину, поделив пополам.

2. Если ключ поиска совпадает с ключом по середине, то вернуть адрес, иначе если ключ в середине > ключа поиска, то изменить верхнюю границу, иначе изменить нижнюю границу.

Пример 4.

Бинарный поиск.

1. Задать верхнюю и нижнюю границу поиска

2. Пока адресное пространство существует выполнять

   1. Вычислить середину адресного пространства

   2. Если ключ поиска совпадает с ключом в середине, то вернуть адрес иначе

   3. Если ключ в середине больше ключа поиска, то изменить верхнюю границу иначе изменить нижнюю.

Экспоненциальный алгоритм при кратном повышении мощности вычислителя позволяет увеличивать размерность задачи на фиксированную величину.

Оптимизационные и опознавательные задачи.

Оптимизационная задача это задача поиска варианта решения из множества вариантов наилучшего в смысле заданного критерия.

Распознавательная задача это задача дающая ответ на вопрос является ли предложенный вариант оптимальным.

Каждая оптимизационная постановка имеет распознавательный эквивалент.

1. Для всех вершин I от 1 до n выполнять

   1. Для всех вершин j != I выполнять

      1. Удалить ребро I j из графа

      2. Если в изменённом графе отсутствует кратчайший цикл, то вернуть его на место. (Распознавательная задача)

Решение задач оптимизационной.

Задача оптимизации полиноминально сводиться к задаче оптимизации.

Если задача А полиноминально сводится к задаче B то оценка эффективности решения задачи А отличается от оценки эффективности задачи B полиноминальным множителем.

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

P и np классы эффективности.

НП – алгоритмы это алгоритмы, которые решаются за премиуминальное время при условии неограниченного распаралеливаования.

Задачи оптимизации на графах.

Подходы к решению:

1. Перебор – алгоритм исчерпывающего и ограниченного перебора.

2. Приближенный методы оптимизации.

3. Эффективные алгоритмы.

Алгоритмы исчерпывающего перебора.

Поиск в глубину и поиск в ширину.

В стратегии перебора отличается последовательностью порождения допустимых вариантов.

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

Стратегия поиска в ширину для каждого текущего состояния рассматривает все возможные состояния–продолжения в порядке очереди.

Пример.

Поиск пути между парой заданных вершин графа.

Найти все возможные варианты пути из вершины 3 в вершину 6.

Мы находимся в вершине 3.

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