Вычислительная сложность алгоритмов

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

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

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

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

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

Оценка сложности алгоритмов и создание эффективных алго­ритмов - одна из важнейших задач современной дискретной математики.

Существует много критериев оценки алгоритмов. Но можно сказать, что одним из самых важных критериев является его временная сложно­сть. Время ра­боты алгоритма можно выразить в виде функции от «размеров» входных данных, требуемых для описания задачи. Входные и вы­ходные данные можно кодировать некоторым «разумным» спо­собом в виде двоичных последовательностей из нулей и единиц. Тогда алгоритм можно рассматривать как последовательность двоичных операций, работающих с памятью из двоичных же символов.

Временная сложность алгоритма отражает затраты времени (число шагов), требуемые для его работы. Это функция, которая каждой входной длине n ставит в соответствие мини­мальное время, затрачиваемое алгоритмом на решение всех од­нотипных индивидуальных задач этой длины.

Из курса математического анализа известно, чтофункция f(n) есть O(g(n)), если существует константа c, такая что |f(n)| <= c(g(n)) для всех n >= 0.

Полиномиальным алгоритмом (или алгоритмом полиномиаль­ной временной сложности) называется алгоритм, у которого вре­менная сложность равна О(Р(n)), где Р(n) — некоторая поли­номиальная функция от входной длины n. Алгоритмы, для вре­менной сложности которых не существует такой оценки, называ­ются экспоненциальными.

Задача считается труднорешаемой,если для нее не сущест­вует разрешающего полиномиального алгоритма.

Кажется, что по мере совершенствования вычислительной техники и роста ее быстродействия проблема оптимизации алгоритмов не должна стоять так остро. Но следующие табл. 2, 3 демонстрируют обратное. Из последней таблицы видно, что повышение быстродей­ствия машины не дает существенного роста размерности разре­шимых задач, если алгоритм имеет экспоненциальную слож­ность.

Таблица 2

Оценка зависи­мости времени работы алгоритмов сложности, равной n, n³, 2ⁿ, от размеров входной информации

Таблица 3

Оценка максимальной размерности задачи, решаемой за один час

Многие прикладные задачи могут быть сформулированы в терминах теории графов. Однако при решении реальных задач характеристики соответствующих графов (например, число вер­шин n и число ребер m) весьма велики, и их анализ возможен лишь с привлечением ЭВМ.

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

Задачи теории графов можно классифицировать следующим образом:

1) задачи, для которых имеются алгоритмы сложности O(n + m);

2) задачи, для которых известны алгоритмы сложности О (Р(n + m)), где Р — нелинейный полином;

3) задачи, для которых известны только алгоритмы экспонен­циальной сложности, но про которые нельзя сказать, что для них нет алгоритмов полиномиальной сложности;

4) задачи, которые могут быть решены лишь с использовани­ем алгоритма экспоненциальной сложности.

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

К четвертому классу относятся задачи перечисления всех остовных деревьев графа и перечисления всех циклов графа. Это объясняется тем, что у полного n-вершинного графа число остовных деревьев равно n^n-2 , число циклов дли­ны i равно Cⁱ_n(i - 1)!, т. е. общее число циклов составляет

К первому классу относятся, например, следующие задачи: поиск остовного дерева графа; выделение компонен­ты связности графа и сильной связности орграфа; нахождение минимального пути в орграфе (или минимального маршрута в графе). Для решения этих задач построены алгоритмы, имеющие сложность О(n + m).

Второй класс в настоящее время включает в себя такие за­дачи: нахождение матрицы связности; нахождение мини­мального пути в нагруженном графе (сложность алгоритма О(n³)); нахождение минимального ос­товного дерева в нагруженном графе (сложность алгоритма О (n²)).

Третий класс содержит следующие задачи: о существовании в графе гамильтонова цикла (задача коммивояжера); об определении изоморфизма данного графа G₁ какому-нибудь подгра­фу графа G₂, и многие другие задачи. Для решения этих задач не существует полиномиальных алго­ритмов, хотя не кажется безусловным, что их решение возможно лишь с помощью экспоненциальных алгоритмов. Для многих за­дач этого класса справедливо следующее свойство сводимости: существование полиномиального алгоритма для решения одной из них дало бы полиномиальный алгоритм для решения другой. В современной дискретной математике третий класс задач явля­ется предметом пристального изучения.

Библиографический список

1. В. Н. Нефедов, В. А. Осипова Курс дискретной математики: учебное пособие. - М. Изд-во МАИ, 1992.-264 с.: ил.

2. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. Москва: Издательство «Мир», 1976. 735 с.

3. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Издательство «Мир», 1978. 844 с.

4. Кук Д., Бейз Г. Компьютерная математика. М.: Наука, 1990. 384 с.

5. Кузнецов О.П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с.

6. Яблонский С. В. Введение в дискретную математику. М.: Наука, 384 с., 1986

7. Костин А. Е., Шаньгин В. Ф. Организация и обработка структур данных в вычислительных системах. М.: Высшая школа, 1987. 248 с.

8. Королев М. А., Клешко Г. Н., Мишенин А. И. Информационные системы и структуры данных. М.: Статистика, 1977. 183 с.

9. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 535 с.

10. Евстигнеев В.А. Применение теории графов в программировании. /Под ред. А.П. Ершова.- М.: Наука, Главная редакция физико-математической литературы, 1985 – 352 с.

11. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985. – 406 с.

12. Харари Ф. Теория графов /пер. с англ. В.П. Козырева. Под ред. Г. П. Гаврилова – М.: Издательство «Мир», 1973. 300 с.

Оглавление

Введение…………………………………………………………………….3

1. Неориентированные графы... 4

1.1. Основные определения. 4

1.2. Маршруты, циклы и связность. 6

2. Ориентированные графы... 7

2.1. Основные определения. 7

2.2. Маршруты и связность в ориентированных графах. 8

3. Структуры данных для представления графа.. 11

3.1. Матричное представление графов. 11

3.1.1. Матрица инциденций. 12

3.1.2. Матрица циклов. 14

3.1.3. Матрица разрезов. 15

3.1.4. Матрица смежности вершин. 16

3.1.5. Матрица путей. 18

3.2. Представление графов в виде списков. 18

3.3. Упорядоченные графы.. 19

4. Задачи нахождения путей в графах.. 20

4.1. Алгоритм вычисления стоимости прохождения между узлами. 21

4.2. Алгоритм нахождения кратчайшего пути. 22

4.3. Задачи с одним источником.. 23

4.4. Метод поиска в глубину. 25

4.4.1. Алгоритм поиска в глубину на неориентированном графе. 26

4.4.2. Поиск в глубину в ориентированном графе. 27

5. Вычислительная сложность алгоритмов.. 28

6. Библиографический список.. 33

Не нашли, что искали? Воспользуйтесь поиском по сайту: