Теория алгоритмов (стр. 3 из 3)
Предположим, что можно рассмотреть все возможные алгоритмы Aiрешения задачи a и для каждого параметра n оценить задачу двумя оценками d1(a) = min (d(Ai (a))) и d2(a) = max (d(Ai (a))), где min и maxберётся по всем алгоритмам . В этом случае получим две границы решения данной задачи – нижнюю и верхнюю (рис.2). Этот рисунок определяет тот разброс сложности решений задачи и помогает ответить на вопрос: нужно ли тратить силы на поиск хорошего алгоритма или достаточно взять первый попавшийся.
Очень часто возможно оценить исходя из анализа самой задачи вид функции оценки с точностью до некоторого сомножителя – константы. В этом случае эта оценка будет не только оценка алгоритма, но и оценка задачи.
Функция f(n)есть O(g(n)), если существует константа с, такая, что f (n)< O(g(n)) для всех значений n>0.
По виду этой функции алгоритмы разделяются на следующие группы:
с линейной оценкой сложности, если функция d=C·n;
с квадратичной сложностью, если d = C · n2;
с полиномиальной сложностью, если d = C0 + C1·n +…+ Ck · nk;
с факториальной сложностью, если d=C·n!;
с экспоненциальной сложностью, если d = C · a n;
с гиперэкспоненциальной сложностью, если d = C · a t, где t = a n.
Здесь C, a и k = некоторые константы, при этом число C может быть очень большим.
Практические и NP-полные алгоритмы
По виду функций алгоритмы (и соответствующие задачи) делятся на два класса. К первому относятся алгоритмы групп 1-3, когда для полиномиальных алгоритмов k≤ 7. Эти алгоритмы называются практическими. Все другие алгоритмы составляют второй класс и называются NP – полными.
В табл. 1 приведена зависимость времени работы алгоритмов различной сложности для задач различной размерности, при условии, что время выполнения одной операции во всех алгоритмах одинаковы. Из таблицы видно, что для полинома, степени 5 задачу размерности 6о решить можно за приемлемое время, в то же время для экспоненциальных алгоритмов уже для размерности, больше 30 задача не решается.
| Таблица 1. | ||||||
| Сложность задачи | ||||||
| Сложностьалгоритма | 10 | 20 | 30 | 40 | 50 | 60 |
| N | 0.00001с | 0,00002с | 0,00003с | 0,0004с | 0,0005с | 0,00006с |
| N^2 | 0,0001с | 0,0004с | 0,0009с | 0,0016с | 0,025с | 0,0036с |
| N^3 | 0,001с | 0,008с | 0,027с | 0,064с | 0,125с | 0,216с |
| N^5 | 0,1 c | 3,2 c | 24,3 c | 1,7 мин | 5,2 мин | 13,0мин |
| 2^n | 0,001 c | 1 c | 17,9 мин | 12,7 дней | 35,7 лет | 366 столетий |
| 3^n | 0,059c | 58 мин | 6,5 лет | 3855 столетий | 2*10^8стол | 1,3*10^13 стол |
Рост скорости вычислений не уменьшит значение эффективных алгоритмов, что иллюстрирует табл. 2..
| Таблица 2 | |||
| Сложность алгоритма | Максимальный размер задачи, разрешимый за единицу времени | ||
| На современных ЭВМ | Если производ*10 | Если производ*1000 | |
| N | k | 10k | 1000k |
| Nlog n | k | Почти 10k при больших к | Почти 10k при больших к |
| N^2 | k | 3,16k | 31,6k |
| N^3 | k | 2,15k | 10k |
| 2^n | k | K+3,3 | K+9,97 |
Если доказано, что задача является NP – полной, то это означает, что её решение для параметров, имеющих практическое значение, связано с огромными затратами времени или памяти, которые не позволят получить решение. В этом случае необходимо переформулировать задачу. Например, задача поиска минимальной формулы для булевой функции является задачей NP – полной, поэтому при проектировании схем, где эта задача встречается, решают задачу, которую формулируют как поиск функций, близкой к минимальной, для чего пользуются эвристическими алгоритмами, основанными на предположениях здравого смысла. Так, если решается задача размещения объектов в некотором блоке, то разумно начинать размещение с самого большого объекта. В этих алгоритмах не всегда гарантируется получение минимального решения, но если для большинства задач оценка отличается не больше, чем на 10-15% от минимального, то это часто устраивает пользователей.
Пpимеp. Оценим сложность алгоритма Прима поиска минимального остова в графе. Пусть граф описан матрицей смежности.
Алгоритм. Выберем любую вершину и включим её в остов. Рассмотрим связанные с ней ребра. Найдём вершину, связанную с включённой в остов ребром минимального веса и включим её в остов. Для вершин, включённых в остов, рассмотрим связанные с ними рёбра к вершинам, не включённым в остов. Выберем вершину, связанную ребром минимального веса и включим её в остов. Эту процедуру продолжим до тех пор, пока все вершины не будут включены в остов.
Для матричного представления алгоритм примет, следующий вид. Выберем любую вершину и в соответствующей ей строке матрицы найдём ячейку с минимальным весом. Эта процедура потребует n сравнений, где n- порядок матрицы (число вершин в графе). Имя столбца этой ячейки определяет вершину, которую нужно включить в остов. Объединим эти вершины в одну, соответствующую вершинам, включённым в остов. Для этого рассмотрим строки и столбцы этих вершин. Если в i-й ячейке одной из строк не нулевое число, оно запишется в результирующую строку, если ненулевое значение в обеих строках, в результирующую запишем минимальное. Таким образом, для «обработки» одной вершины потребуется число операций, кратных 2 n. Число вершин в рассматриваемом графе сократится на единицу. Повторим то же самое для результирующей строки, пока число вершин не станет равной единицы. Значит, общее число операций оценивается числом, пропорциональным n2, т.е. оценка имеет квадратичную сложность d = C · n2.
Алгоритмически неразрешимые проблемы
Задачи, для которых доказано, что решающего их алгоритма не существует, называются алгоритмически неразрешимыми.
Существует большое количество задач, являющихся алгоритмически неразрешимыми. То есть речь идет об отсутствии единого алгоритма, решающего данную задачу. При этом вовсе не исключается возможность решения задачи в частных случаях, но различными способами для каждого случая.
Рассмотрим несколько примеров алгоритмически неразрешимых задач.
1 Задача эквивалентности алгоритмов
По двум произвольно заданным алгоритмам определить будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
2 Задача останова машины Тьюринга
Не существует алгоритма, позволяющего по описанию произвольного алгоритма и его исходных данных определить, останавливается ли алгоритм на этих данных или работает бесконечно.
3 Задача эквивалентности двух слов в ассоциативном исчислении
Ассоциативным исчислением называют совокупность всех слов в некотором алфавите вместе с какой-либо конечной системой допустимых подстановок.
Подстановка P ® Q называется ориентированной. Она заключается в замене фрагмента P в слове R фрагментом Q.
Подстановка P — Q называется неориентированной. Она заключается как в замене фрагмента P в слове R фрагментом Q, так и в замене в слове R фрагмента Q фрагментом P.
Пример. R = ‘aabcb’ P = ‘ab’ Q = ‘bcb’
При P ® Q получим: R' = ‘abcbcb’.
При P — Q получим как R' = ‘abcbcb’, так и R'' = ‘aaab’.
Два слова R1 и R2 называются эквивалентными для заданной системы ориентированных подстановок, если от слова R1 можно, применяя конечное число раз подстановки, перейти к слову R2.
Если же подстановки неориентированы, то возможность перехода требуется как от R1 к R2, так и от R2 к R1.
Задача эквивалентности слов в ассоциативном исчислении состоит в следующем: для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет.
Задача слов не является надуманной, так как к ней может быть сведена любая известная задача.
Например, рассмотрим задачу поиска пути в лабиринте. Изобразим лабиринт в виде графа, в котором вершинам соответствуют площадки, а ребрам — соединяющие их коридоры. Каждой площадке или вершине графа сопоставим некоторое слово. Каждому коридору или ребру xixj сопоставим неориентированную подстановку, переводящую слово, соответствующее xi, в слово, соответствующее xj.
Например, если вершине x1 соответствует слово ‘xypt’, а смежной вершине x2 — слово ‘xyqt’, то неориентированная подстановка будет иметь вид:
‘p’ — ‘q’.
Задача слов решена для некоторых частных случаев. Например, пусть даны алфавит {x, y, z, p, q} и система неориентированных подстановок:
xz — zx, xp — px, yz — zy, yp — py, xyxz — xyxzq, qzx — xq, qpy — yq.
Спрашивается, эквивалентны ли в данном ассоциативном исчислении слова: xyxxzp и xzypxp?
Ответ: нет, не эквивалентны, так как в первом слове нечетное число букв x, а во втором — четное; система же подстановок сохраняет четность или нечетность букв x в словах.
В общем же случае задача слов алгоритмически неразрешима.
4 Задача распознавания выводимости
С задачей эквивалентности двух слов в ассоциативном исчислении тесно связана задача распознавания выводимости, которая является одной из важнейших задач математической логики.
Задача распознавания выводимости состоит в следующем:
для любых двух слов (формул) S и T в логическом исчислении определить выводима ли формула T из формулы S.
Эта задача также алгоритмически неразрешима.
Теория алгоритмов Методическое пособие по дисциплине «Математическая логика и теория алгоритмов» / В.П. Битюцкий, Н.В. Папуловская. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006, с.