Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Практические и NP-полные алгоритмы





По виду функций алгоритмы (и соответствующие задачи) делятся на два класса. К первому относятся алгоритмы групп 1-3, когда для полиномиальных алгоритмов k≤ 7. Эти алгоритмы называются практическими. Все другие алгоритмы составляют второй класс и называются NP – полными.

В табл. 1 приведена зависимость времени работы алгоритмов различной сложности для задач различной размерности, при условии, что время выполнения одной операции во всех алгоритмах одинаковы. Из таблицы видно, что для полинома, степени 5 задачу размерности 6о решить можно за приемлемое время, в то же время для экспоненциальных алгоритмов уже для размерности, больше 30 задача не решается.

 

Таблица 1.
  Сложность задачи
Сложность алгоритма            
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.

 

Date: 2015-07-01; view: 583; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию