Время работы алгоритма Краскала с древовидной и списочной структурой данных

Путем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
Hauptverfasser:	Трофимчук, А.Н., Васянин, В.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2015
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/123488
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Время работы алгоритма Краскала с древовидной и списочной структурой данных / А.Н. Трофимчук, В.А. Васянин // Системні дослідження та інформаційні технології. — 2015. — № 3. — С. 48-61. — Бібліогр.: 28 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-123488
record_format	dspace
spelling	irk-123456789-1234882017-09-07T03:02:55Z Время работы алгоритма Краскала с древовидной и списочной структурой данных Трофимчук, А.Н. Васянин, В.А. Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень Путем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима. За допомогою чисельних експериментів виконано порівняння двох реалізацій алгоритму Краскала, які основано на списковій (запропонований алгоритм) і деревовидній (алгоритм Тарьяна) структурах даних та алгоритму Прима. Using numerical experiments, two implementations of Kruskal's algorithm based on the linked lists (the proposed algorithm) and tree (Tarjan's algorithm) data structures were compared with Prim's algorithm. 2015 Article Время работы алгоритма Краскала с древовидной и списочной структурой данных / А.Н. Трофимчук, В.А. Васянин // Системні дослідження та інформаційні технології. — 2015. — № 3. — С. 48-61. — Бібліогр.: 28 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/123488 519.168 ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень
spellingShingle	Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень Трофимчук, А.Н. Васянин, В.А. Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології
description	Путем численных экспериментов выполнено сравнение двух реализаций алгоритма Краскала, основанных на списочной (предложенный алгоритм) и древовидной (алгоритм Тарьяна) структуре данных и алгоритма Прима.
format	Article
author	Трофимчук, А.Н. Васянин, В.А.
author_facet	Трофимчук, А.Н. Васянин, В.А.
author_sort	Трофимчук, А.Н.
title	Время работы алгоритма Краскала с древовидной и списочной структурой данных
title_short	Время работы алгоритма Краскала с древовидной и списочной структурой данных
title_full	Время работы алгоритма Краскала с древовидной и списочной структурой данных
title_fullStr	Время работы алгоритма Краскала с древовидной и списочной структурой данных
title_full_unstemmed	Время работы алгоритма Краскала с древовидной и списочной структурой данных
title_sort	время работы алгоритма краскала с древовидной и списочной структурой данных
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2015
topic_facet	Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень
url	http://dspace.nbuv.gov.ua/handle/123456789/123488
citation_txt	Время работы алгоритма Краскала с древовидной и списочной структурой данных / А.Н. Трофимчук, В.А. Васянин // Системні дослідження та інформаційні технології. — 2015. — № 3. — С. 48-61. — Бібліогр.: 28 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT trofimčukan vremârabotyalgoritmakraskalasdrevovidnojispisočnojstrukturojdannyh AT vasâninva vremârabotyalgoritmakraskalasdrevovidnojispisočnojstrukturojdannyh
first_indexed	2025-07-08T23:45:13Z
last_indexed	2025-07-08T23:45:13Z
_version_	1837124364566265856
fulltext	 А.Н. Трофимчук, В.А. Васянин, 2015 48 ISSN 1681–6048 System Research & Information Technologies, 2015, № 3 TIДC ТЕОРЕТИЧНІ ТА ПРИКЛАДНІ ПРОБЛЕМИ ІНТЕЛЕКТУАЛЬНИХ СИСТЕМ ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ УДК 519.168 ВРЕМЯ РАБОТЫ АЛГОРИТМА КРАСКАЛА С ДРЕВОВИДНОЙ И СПИСОЧНОЙ СТРУКТУРОЙ ДАННЫХ А.Н. ТРОФИМЧУК, В.А. ВАСЯНИН Путем численных экспериментов выполнено сравнение двух реализаций алго- ритма Краскала, основанных на списочной (предложенный алгоритм) и древо- видной (алгоритм Тарьяна) структуре данных и алгоритма Прима. Результаты сравнения позволяют утверждать, что для решения практических задач нахож- дение минимального или максимального остовного дерева (леса) алгоритмы со списочной структурой данных работают не хуже, а в большинстве случаев бы- стрее, чем алгоритмы с древовидной структурой. Показана практическая оцен- ка сложности предложенного алгоритма, которая для связных графов состав- ляет )(eO , где e — число ребер графа. Экспериментально доказано, что время работы алгоритма на связных разреженных графах сравнимо со временем «карманной» сортировки ребер (bucket sort). Выявлено, что предложенный ал- горитм работает быстрее алгоритма Прима для графов с числом ребер не больше, чем ,27,0 2v где v — число вершин графа. Экспериментальное иссле- дование алгоритма на графах, содержащих от 499500 до 71994000 ребер, пока- зало его высокую вычислительную эффективность, и он может быть рекомен- дован для решения практических задач на разреженных графах или сетях большой размерности. ВВЕДЕНИЕ В настоящее время известно достаточно много алгоритмов определения ми- нимального остовного дерева на взвешенном графе (MST-дерева). Наиболее известными из них являются алгоритмы Борувки [1,2], Ярника-Прима- Дейкстры [3–5] и Краскала-Лобермана-Вайнберга [6,7]. Алгоритм Борувки был много раз переоткрыт другими авторами (Шоке, Флорек, Лукасевич, Перкал, Штейнгауз, Зубжицкий) и известен также как алгоритм Соллина [8]. Обширный библиографический обзор по истории развития MST-алгоритмов можно найти в работах Тарьяна [9], Грэхэма и Хелла [10]. Для построения современных алгоритмов используются ATД (абст- рактные типы данных — abstract data type), которые включают различные комбинации традиционных данных, таких как переменные и массивы и спе- циальных (указателей, списков, стеков, очередей, деревьев и т.д.). Для задан- ных классов АТД определяются функциональные операторы (процедуры) обработки внутренних структур данных, которые реализуются средствами используемого языка программирования. В книгах [11–16] можно найти Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології, 2015, № 3 49 подробнейшее описание АТД, применяемых в алгоритмах построения ос- товных деревьев, оценки временной сложности алгоритмов для их различ- ных реализаций, а также исчерпывающий обзор и исторические справки по алгоритмам нахождения остовных деревьев. Следует также отметить, что в современных объектно-ориентированных языках программирования, таких как C++, Java и др. имеются библиотеки со стандартными АТД и программа- ми для решения задач нахождения оптимальных остовных деревьев [17–19]. Цель работы — экспериментально показать, что алгоритм Краскала, реализованный на списочных АТД [20] во многих практических случаях работает быстрее, чем алгоритм Тарьяна [21], основанный на древовидных АТД и сравнить время работы этих алгоритмов и алгоритма Прима на связ- ных и несвязных, плотных и разреженных графах большой размерности. ПОСТАНОВКА ЗАДАЧИ Пусть задан простой (не содержащий петель и параллельных ребер) неори- ентированный граф ),( EVG с множеством вершин ,V Vv  и множе- ством ребер E , Ee  , где v и e соответственно число вершин и ребер графа, а  — знак мощности множества. Граф может быть неполным и несвязным. Для графа задан вектор весов ребер icC  , ei ,1 , где Zci , Z — множество неотрицательных целых чисел. Требуется найти ациклический подграф (лес) графа G с минимальным или максимальным общим весом. В литературе принято называть такой ациклический подграф в случае связного графа MST-деревом, а в случае несвязного графа — MTS-лесом. В дальнейшем для упрощения изложения будем использовать для связных и несвязных графов общий термин MST (minimum/maximum spanning trees — минимум/максимум остовных де- ревьев). АЛГОРИТМЫ ПОСТРОЕНИЯ MST-ДЕРЕВЬЕВ В настоящее время наилучшими по быстродействию для разреженных гра- фов являются алгоритмы Тарьяна [21] (без учета сортировки ребер), Габова, Галила, Спенсера и Тарьяна [22] и Чазелла [23, 24]. Дальнейшее развитие алгоритмов возможно за счет усложнения АТД и уменьшения времени вы- полнения отдельных операций, используемых при работе с их внутренними структурами данных [14, 15]. Уменьшение времени работы алгоритмов мо- жет быть достигнуто также за счет распараллеливания процесса построения MST, особенно в алгоритмах Борувки-Соллина. Несмотря на существование достаточно эффективных MST-алгоритмов, интерес к разработке еще более быстрых алгоритмов не ослабевает [25, 26], (рассматривается современное положение дел в поиске линейного алгорит- ма построения MST). Это объясняется тем, что одновременно с постоянным ростом быстродействия и оперативной памяти современных ПК, появляется возможность решать более сложные оптимизационные задачи для графов А.Н. Трофимчук, В.А. Васянин ISSN 1681–6048 System Research & Information Technologies, 2015, № 3 50 или сетей большой размерности (десятки тысяч вершин, сотни тысяч и мил- лионы ребер), в которых в качестве подзадач нужно многократно находить MST-деревья. Тогда алгоритм определения MST-деревьев с минимальной сложностью может значительно сократить время решения общей задачи. Приведем реализацию «жадного» алгоритма Краскала, который нахо- дит остовное дерево с минимальным или максимальным весом за время )(eO [20]. Введем обозначения:  ,  — знаки логического «и», логическо- го «или»; «» — знак операции присваивания, «!» — знак комментария, а },1\| { eii  — означает «для всех i от единицы до e с шагом 1». Для сортировки ребер будем применять алгоритм со сложностью по- рядка )(eO , основанный на идеях «карманной» сортировки или сортировки «вычерпыванием» и сортировки подсчетом. Такой тривиальный подход к сортировке ребер оправдан низкой временной сложностью и тем, что для большинства графов (сетей), характеризующих реальные объекты, разброс значений весов ребер, как правило, незначителен. Для описания алгоритма сортировки определим следующие перемен- ные и структуры данных. Обозначим: v , e — число вершин и неориенти- рованных ребер в графе; MINVAL , MAXVAL — минимальный и макси- мальный вес ребра; )(eIS , )(eST , )(eC — массивы, содержащие соответственно номера левых и правых вершин ребер и веса ребер. Для удобства эти массивы могут быть упорядочены так, чтобы номер левой вершины был меньше номера правой вершины, а номера левых и правых вершин увеличивались от начала к концу массивов; )2,(MMAXU — массив, содержащий ссылки на списки номеров ребер, упорядоченных по неубыва- нию весов в массиве )(eE ; )(eE — массив, содержащий списки номеров ребер, упорядоченных по неубыванию весов. Алгоритм сортировки не перемещает исходные значения в массивах ,IS ,ST .C Сортируются только ссылки на номера ребер в исходных масси- вах в порядке неубывания весов ребер. Для этого строится массив )(eE списков номеров ребер. Поскольку может быть несколько ребер с одинако- вым весом, массив содержит списки для ребер с одинаковым весом. В мас- сиве )2,(MMAXU элемент )1,(iU содержит голову списка — номер первого ребра k в массиве )(eE с весом i , а элемент )2,(iU указывает на номер по- следнего ребра j в массиве )(eE с весом i . При этом элемент )(kE указы- вает на следующее ребро в )(eE с таким же весом и т.д. Для последнего ребра j значение 0)( jE и означает конец списка ребер с одинаковым ве- сом. Для того чтобы в начале массива U не было пустых элементов, выпол- няется масштабирование весов ребер. Поэтому значение MMAX 1 MINVALMAXVAL равно максимальному весу ребра после масштаби- рования плюс 1, а минимальный вес ребра будет всегда равен единице. Если веса ребер являются дробными неотрицательными числами, то с учетом не- обходимой точности вычислений, можно ввести соответствующие мас- штабные коэффициенты (например, умножить веса всех ребер на 1000, 10000 и т.д.) для перевода весов ребер в целые числа, а затем определить значение .MMAX Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології, 2015, № 3 51 Алгоритм SORT. Сортировка ребер по неубыванию весов с временной сложностью )(eO . 1. 0U ; .0E 2. Для } ,1 { eii  выполнить шаги 3–6. 3. 1)(  MINVALiCl . 4. Если 0)1,( lU , то ilU )1,( ; иначе ilUE ))2,(( . 5. ilU )2,( . 6. Перейти к шагу 2. ! Конец цикла по .i 7. Конец. Очевидно, что асимптотическая оценка временной сложности алгорит- ма SORT составляет )(eO операций, а реальное время выполнения сорти- ровки ребер будет зависеть от конкретного языка программирования алго- ритма, компилятора, операционной системы и мощности компьютера на котором работает конкретная программа, реализующая алгоритм. Рассмотрим алгоритм построения MST. Пусть MK — максимальное число независимых компонент графа, 2/vMK  ; NK — номер очередной порожденной компоненты; KK — количество связных компонент; NY — счетчик количества вершин в строимом минимальном остовном лесе; SV — признак наличия изолированных вершин в графе; )(MKW — массив весов порожденных компонент. Определим следующие массивы: )(vA — массив, содержащий номера связных компонент, в которые входят вершины ,i vi ,1 ; )3,(MKH — массив, содержащий ссылки на списки номеров вер- шин компоненты MK в массиве );(vG )(vG — массив, содержащий списки номеров вершин связных компонент графа; )2,(MKEK — массив, содер- жащий ссылки на списки номеров ребер компоненты MK в массиве )(eB ; )(eB — массив, содержащий списки номеров ребер связных компонент графа. Массивы ),3,(MKH )(vG и ),2,(MKEK )(eB устроены аналогично массивам ),2,(MMAXU )(eE . Элемент )3,(iH содержит число вершин в i -й компоненте графа ( i -ом поддереве). Введенные структуры данных позволяют за две операции сравнения определять, к какой компоненте при- надлежат вершины ребра, включаемого в остовный лес на очередном шаге алгоритма, а также за одну операцию присваивания сливать две независи- мые компоненты в одну. При этом всегда компонента с меньшим числом вершин или ребер сливается в большую компоненту. Алгоритм LINK. Построение остовного леса (дерева) с минимальным весом с использованием списочных структур данных. 1. ;0A ;1NK ;0KK ;0NY ;0G ;0B ;0W .0SV 2. ;0KNOV ;0KPRI ;0KSLI ;0KOST ;0KPUS .0KSUZ 3. Для } ,1 { MMAXii  выполнить шаги 4–31. 4. )1,(iUND  . ! Выбрать номер первого ребра из списка ребер с оди- наковым весом. А.Н. Трофимчук, В.А. Васянин ISSN 1681–6048 System Research & Information Technologies, 2015, № 3 52 5. Пока 0ND выполнить шаги 6–30. 6. )(NDISl  ; )(NDSTk  ; )(1 lAl  ; )(1 kAk  . ! Выбрать левую и правую вершины ребра и номера компонент, в которые эти вершины входят. 7. Если 110101 klkl  , то 1 KPUSKPUS ; перейти к шагу 28. ! Обнаружено циклическое ребро, перейти на выбор нового ребра. 8. Если ,0101  kl то перейти к шагу 15. ! Присоединить к суще- ствующей компоненте новую вершину и новое ребро, перейти к присоеди- нению к компоненте. 9. Если ,0101  kl то lll  ; 111 ll  ; kl  ; 11 kl  ; llk  ; 111 lk  ; перейти к шагу 15. ! Присоединить к существующей компоненте новую вершину и новое ребро, перейти к присоединению к компоненте. 10. Если 0101  kl , то перейти к шагу 12. ! Образовать новую ком- поненту, добавить две новые вершины и одно новое ребро, перейти на обра- зование компоненты. 11. Перейти к шагу 18. ! Слить две независимые компоненты и добавить новое ребро, перейти на слияние компонент. 12. NKlA )( ; NKkA )( ; lNKH )1,( ; klG )( ; kNKH )2,( . ! Образование новой компоненты. 13. 2)3,( NKH ; NDNKEK )1,( ; NDNKEK )2,( ; )(NKW )(NDC . ! 14. 1 KKKK ; 1 NKNK ; 2 NYNY ; 1 KNOVKNOV ; 1 KOSTKOST ; перейти к шагу 28. 15. 1)( klA  ; lkHG ))2,1(( ; lkH )2,1( ; 1)3,1()3,1(  kHkH . ! Присоединение к компоненте 16. NDkEKB ))2,1(( ; NDkEK )2,1( ; )()1()1( NDCkWkW  . 17. 1 NYNY ; 1 KPRIKPRI ; 1 KOSTKOST ; перейти к ша- гу 28. 18. Если )3,1()3,1( kHlH  , то 1llp  ; 11 kl  ; lpk 1 . ! Слияние ком- понент. 19. )1()1()1( lWkWkW  ; .0)1( lW 20. 1 KSLIKSLI ; 1 KOSTKOST ; )3,1(lHKSUZKSUZ  . 21. );1,1())2,1(( lHkHG  );2,1()2,1( lHkH  ).3,1()3,1()3,1( lHkHkH  22. )1,1())2,1(( lEKkEKB  ; )2,1()2,1( lEKkEK  ; .))2,1(( NDkEKB  23. NDkEK )2,1( ; ).()1()1( NDCkWkW  24. ).1,1(lHj  25. Пока 0j выполнить шаг 26. ! Обновить массив вхождения вер- шин в компоненты после слияния двух компонент. 26. 1)( kjA  ; )( jGj  . 27. 1 KKKK . ! Уменьшить число компонент на единицу. 28. Если vNYKK 1 , то перейти к шагу 33. ! Граф связный и все узлы включены в остовный лес. 29. )(NDEND  . ! Выбрать номер очередного ребра. Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології, 2015, № 3 53 30. Перейти к шагу 5. ! Конец цикла по .ND 31. Перейти к шагу 3. ! Конец цикла по .i 32. Если vNY  , то 1 SVSV . 33. Конец. Приведенный алгоритм может быть использован для построения ос- товного леса (дерева) с максимальным весом, если в цикле по i ребра просматривать в обратном порядке, т.е. в шаге 3 записать: для } 1,1, \| {  MMAXii выполнить шаги 4–31. В записи алгоритма в шаге 2 введены переменные ,KNOV ,KPRI ,KSLI в которых соответственно накапливается: число образований новых компонент; число присоединений к существующей компоненте вершин (ре- бер); число слияний двух независимых компонент. В переменных ,KOST ,KPUS KSUZ соответственно подсчитывается число ребер в остовном ле- се, число пустых проходов (пропуск ребер, образующих циклы), суммарное число слитых вершин. Все эти переменные необходимы для проведения дальнейшего экспериментального анализа сложности алгоритма. Значения ,KPUS ,KPRI ,KNOV KSLI и KSUZ зависят от структуры и размерно- сти графа, их трудно выразить через основные параметры графа, поэтому в дальнейшем изложении для их определения будем использовать эмпириче- ские методы. Значение KOST = KPRI + KNOV + ,KSLI а KOST + KPUS = e или KOST + KPUS = e — числу просмотренных ребер графа для построе- ния остовного дерева или леса соответственно для связного и несвязного графа. Рассмотрим алгоритм Тарьяна [21] построения MST-деревьев с приме- нением древовидной структуры для представления наращиваемого остовно- го леса с операциями слияния по рангу и сжатия путей. Будем считать, что ребра графа предварительно отсортированы алгоритмом SORT. Определим следующие массивы: )(iA , vi ,1 — массив указателей на вхождение вершин i в независимые компоненты, первоначально каждая вершина указывает сама на себя; )(iH , vi ,1 — массив, содержащий ранги вершин i ; )(iB , 1,1  vi — массив, содержащий номера ребер MST графа. Алгоритм TREE. Построение остовного леса (дерева) с минимальным весом с использованием древовидных структур данных. 1. ;0H ;0B ;0SUM ;0LP ;0KSLI ;0KOST ;0KPUS .0KSUZ 2. Для } ,1 { vii  выполнить iiA )( . 3. Для } ,1 { MMAXii  выполнить шаги 4–14. 4. )1,(iUND  . ! Выбрать номер первого ребра из списка ребер с оди- наковым весом. 5. Пока 0ND выполнить шаги 6–13. 6. )(NDISl  ; )(NDSTk  . А.Н. Трофимчук, В.А. Васянин ISSN 1681–6048 System Research & Information Technologies, 2015, № 3 54 7. 1 KSLIKSLI . 8. Вызвать )(lFND ; Вызвать ).(kFND 9. Если ,kl  то перейти к шагу 10, иначе 1 KPUSKPUS , перейти к шагу 11. 10. Вызвать ),( lkUN ; 1 KOSTKOST ; 1 LPLP ; NDLPB )( ; ).(NDCSUMSUM  11. Если ,1 vKOST то перейти к шагу 15. 12. ).(NDEND  13. Перейти к шагу 5. ! конец цикла по .ND 14. Перейти к шагу 3. ! конец цикла по .i 15. Конец. 1. Процедура )(xFND . ! zyx ,, — целые. 2. xz  . ! Ищем корень для .x 3. Пока xxA )( выполнить )(xAx  . ! x — корень, первый проход. 4. Пока xzA )( выполнить шаг 5. 5. zy  ; )(zAz  ; xyA )( ; 2 KSUZKSUZ . ! Обновляем ука- затели на корень, второй проход. 6. Возвратить x в точку вызова. ! Конец процедуры ).(xFND 1. Процедура ),( yxUN . ! yx, — целые. 2. Если )()( yHxH  , то yxA )( , перейти к шагу 5, иначе перейти к шагу 3. 3. Если )()( yHxH  , то xyA )( , перейти к шагу 5, иначе перейти к шагу 4. 4. yxA )( ; 1)()(  yHyH . 5. Возврат в точку вызова. ! Конец процедуры .),( yxUN В алгоритме TREE переменные KOST и KPUS имеют то же назначе- ние, что и в алгоритме LINK, а в переменных ,KSLI KSUZ и SUM накап- ливается соответственно число просмотренных ребер, число циклических проходов для нахождения корней деревьев и обновления указателей и суммарный вес остовного дерева или леса. Значение  KOSTKSLI KPUS равно 'e или e для связного и несвязного графа. Чтобы не услож- нять алгоритм Тарьяна в нем не формируются массивы подобные ),3,(MKH ),(vG ),2,(MKEK )(eB и )(MKW для хранения вершин, ребер и весов для компонент несвязного графа. Поэтому при дальнейшем экспериментальном сравнении быстродействия алгоритмов LINK и TREE из алгоритма LINK бы- ли убраны операторы формирования этих массивов и введены операторы 1 LPLP , NDLPB )( , )(NDCSUMSUM  как в строке 10 алго- ритма TREE. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ Для проведения эксперимента были составлены главный модуль программы и четыре модуля (подпрограммы), реализующие алгоритм сортировки Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології, 2015, № 3 55 SORT, алгоритм LINK, алгоритм TREE и алгоритм Прима PRIM с представ- лением графа в виде матрицы смежности. Все тестовые программы написа- ны на языке Digital Visual Fortran. Вычислительный эксперимент проводил- ся на ПЭВМ с процессором Intel Core 2 Duo c тактовой частотой 2,66 ГГц и оперативной памятью 2 Гб под управлением операционной системы Windows Vista. В главном модуле программы в режиме диалога вводились: число вер- шин графа — ;v число исходящих из каждой вершины ребер (степень или валентность вершины) — ;VAL границы изменения значений весов ребер от MINVAL до ;MAXVAL параметр, управляющий выводом входных и выход- ных данных. Далее с помощью датчика псевдослучайных чисел (встроенной функции языка ()RAND ) генерировались веса ребер от MINVAL = 80 до MAXVAL = 800, формировались массивы ,IS ,ST .C Вся оперативная па- мять, необходимая для работы алгоритмов выделялась и освобождалась ди- намически в главном модуле программы. Время работы алгоритмов фикси- ровалось встроенным модулем )(_ Ttimecpu непосредственно до входа и после выхода из модулей сортировки и построения минимального остов- ного дерева. Работа алгоритмов проверялась на неориентированных полных графах с числом вершин v от 1000 (499500 ребер) до 12000 (71994000 ре- бер). Результаты эксперимента приведены в таблице и на рис. 1. Где e — число ребер, просмотренных для полного построения остовного дерева. Для ,KOST ,KPUS ,KPRI ,KNOV KSLI проценты указаны по отношению к e , а для e проценты указаны по отношению к e . Для KSUZ в алгоритме LINK KSUZL( в таблице) указано суммарное число слитых вершин (число выполнений оператора 1)( KJA  в цикле в шаге 25) и среднее число сли- тых вершин за одну итерацию. Для алгоритма TREE параметрKSUZ обоз- начен как .KSUZT Кроме того в таблице приняты следующие обозначения: SORT — время сортировки ребер алгоритмом SORT; ,LINK TREE и ,LSUM TSUM — соответственно время работы предложенного алго- ритма LINK, алгоритма Тарьяна TREE и общее время построения MST- дерева, которое определяется суммой времени сортировки ребер и времени работы алгоритма LINK или алгоритма TREE; PRIM — время работы алго- ритма Прима; MST — вес .MST Из таблицы видно, что процесс построения минимального остовного дерева для связных графов заканчивается при просмотре в среднем не более 0,25% ребер графа, а средние значения в процентах для ,KPUS ,KPRI ,KNOV KSLI приблизительно равны 81%, 15%, 2%, 2%. При этом среднее число слитых вершин за одну операцию слияния равно 6. Время работы ал- горитмов LINK и TREE практически совпадает, растет очень медленно и для полного графа с 12 тыс. вершин не превысило 0,03 с (рис. 1). Общее время построения MST-дерева главным образом определяется временем сортиров- ки ребер в алгоритме SORT. Поэтому для связных графов можно практиче- ски принять, что общая сложность алгоритмов построения MST-дерева со- измерима со сложностью алгоритма SORT для сортировки ребер )(eO . Из таблицы и графиков также видно, что на полных графах лучшим остается алгоритм Прима. А.Н. Трофимчук, В.А. Васянин ISSN 1681–6048 System Research & Information Technologies, 2015, № 3 56 Т а б л и ц а . Время построения MST-дерева полного графа в зависимости от числа вершин в секундах № 1 2 3 4 5 6 7 8 9 10 11 12 С р ед н ее зн ач ен и е v 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 e (млн.) 0,4995 1,999 4,4985 7,998 12,4975 17,997 24,4965 31,996 40,4955 49,995 60,4945 71,994 e 3993 8276 15637 24805 23820 38117 39228 38898 48523 53627 65813 77612 % 0,80 0,41 0,35 0,31 0,19 0,21 0,16 0,12 0,12 0,11 0,11 0,11 0,25 KOST 999 1999 2999 3999 4999 5999 6999 7999 8999 9999 10999 11999 % 25,02 24,15 19,18 16,12 20,99 15,74 17,84 20,56 18,55 18,65 16,71 15,46 19,08 KPUS 2994 6277 12638 20806 18821 32118 32229 30899 39524 43628 54814 65613 % 74,98 75,85 80,82 83,88 79,01 84,27 82,16 79,44 81,45 81,35 83,29 84,54 80,92 KPRI 576 1322 2228 3246 4198 5174 6222 7228 8224 9174 10164 11192 % 14,43 15,97 14,25 13,09 17,63 13,57 15,86 18,58 16,95 17,11 15,44 14,42 15,61 KNOV 212 339 386 377 401 413 389 386 388 413 418 404 % 5,31 4,10 2,47 1,52 1,68 1,08 0,99 0,99 0,80 0,77 0,64 0,52 1,74 KSLI 211 338 385 376 400 412 388 385 387 412 417 403 % 5,28 4,08 2,46 1,51 1,68 1,08 0,99 0,99 0,80 0,77 0,63 0,52 1,73 KSUZL 1040 1656 1880 2332 2364 2597 2800 3068 3050 3004 2873 2754 Число сли- тых вершин за одну итерацию 5 5 5 6 6 6 7 8 8 7 7 7 6 KSUZT 1288 2240 2642 3180 3346 3636 3818 4158 4164 4396 4324 4236 SORT 0,02 0,02 0,03 0,06 0,09 0,09 0,16 0,19 0,22 0,28 0,34 0,37 LINK 0,00 0,00 0,00 0,00 0,00 0,02 0,00 0,02 0,02 0,00 0,00 0,02 TREE 0,00 0,00 0,02 0,00 0,02 0,02 0,02 0,02 0,02 0,02 0,02 0,03 LSUM 0,02 0,02 0,03 0,06 0,09 0,11 0,16 0,21 0,24 0,28 0, 34 0,39 TSUM 0,02 0,02 0,05 0,06 0,11 0,11 0,18 0,21 0,24 0,30 0,36 0,40 PRIM 0,00 0,00 0,02 0,03 0,06 0,06 0,09 0,12 0,16 0,19 0,22 0,23 MST 80351 160083 240013 319950399930 479925 559921 639920719920 799920 879920 959920 При тестировании алгоритмов LINK и TREE генерировались также раз- реженные связные и несвязные графы с различным числом вершин и ребер, и результаты вычислений сравнивались с результатами, полученными для этих графов алгоритмом Прима. Результаты эксперимента для связного 0 0,1 0,2 0,3 0,4 0,5 100 0 200 0 300 0 400 0 500 0 600 0 700 0 800 0 900 0 100 00 110 00 120 00 Число вершин в графе В ре м я в се к. SORT LINK TREE LSUM TSUM PSUM Рис. 1. Сравнение времени работы алгоритмов на полных графах в зависимости от числа вершин в графе Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології, 2015, № 3 57 и несвязного графа содержащего 11000 вершин при изменении степени вер- шин (параметра VAL ) показаны на рис. 2. Из приведенных данных видно, что алгоритмы LINK )(LSUM и TREE )(TSUM с учетом времени на сортировку ребер на разреженных связных графах работают быстрее алгоритма Прима )(PRIM при VAL 6000 и числе ребер vVALe  5,0 не больше, чем 227,0 v . Полученная оценка уточнена и лучше, чем показанная в работе [20]. Для сильно разреженных графов бы- стродействие алгоритмов LINK и TREE с учетом времени сортировки может значительно превышать быстродействие алгоритма Прима — в 15 и более раз. Для несвязных разреженных графов алгоритмы LINK )(LSUM и TREE )(TSUM с учетом времени сортировки лучше алгоритма Прима )(PRIM при VAL 300, 2014,0 ve  и VAL 200, 2009,0 ve  соответственно. На рис. 3 показаны результаты сравнения алгоритмов на несвязных графах, содержащих полные несвязные подграфы или изолированные вер- шины. Из рис. 2б и 3 видно, что на несвязных графах алгоритм LINK ,(LSUM )LINK при увеличении степени вершин начинает заметно опере- жать алгоритм TREE ,(TSUM .)TREE Из графиков на рис. 2б и 3 следует, что временная сложность построения MST для несвязных графов больше сложности сортировки ребер алгоритмом SORT. Проведем асимптотическую оценку сложности алгоритмов LINK и TREE. Ясно (см. таблицу), что .KPUSKSLIKNOVKPRIKPUSKOSTe  Все операции KPUSKSLIKNOVKPRI ,,, выполняются в основном цикле по ND при выборе ребер для анализа. Поскольку сложность каждой из этих операций в алгоритме LINK составляет ,)1(O а всего просматривает- ся e или e ребер соответственно для связных и несвязных графов, то их общая сложность составит )(eO  или )(eO . Если учесть, что сложность опе- раций инициализации массива A вхождения вершин в компоненты графа (операции make set) составляет )(vO , получим время порядка )( veO  или Рис. 2. Сравнение времени работы алгоритмов на разреженных связных (а) и не- связных (б) графах при изменении степени вершин и постоянном числе вершин v = 11000 SORT LINK TREE LSUM TSUM PSUM 0 0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 В ре м я в се к. 0 0,2 0,4 0,6 0,8 1 1,2 50 200 400 600 800 Степень вершин графа при v = 11000 5 300 0 500 0 700 0 900 0 109 99 Степень вершин графа при v = 11000 а б А.Н. Трофимчук, В.А. Васянин ISSN 1681–6048 System Research & Information Technologies, 2015, № 3 58 )( veO  . Осталось оценить сложность операций обновления указателей в массиве A при выполнении операций слияния компонент с меньшим чис- лом вершин в компоненты с большим числом вершин. В работах [14, 15] показано, что сложность таких операций в худшем случае составляет )log( vvO . Однако, если проанализировать таблицу, то очевидно, что число вершин, для которых обновляются указатели не соизмеряется с ростом функции .log vv Значения KSUZL в таблице для числа вершин v от 1000 до 12000 изменяются неравномерно от 1040 до 2754, а среднее число обновле- ний указателей за одну операцию слияния   / KSLIKSUZL изменяется в пределах от 5 до 8, где [ ]  — знак округления числа до ближайшего цело- го. Выразить функцию для числа обновлений указателей через параметры исходного графа v и e затруднительно, поэтому запишем ее в виде некото- рой медленно растущей функции вида ),/( vKSLIKSUZL . Ожидаемую полную сложность алгоритма LINK без сложности сортировки e ребер запишем в виде )),/(( vKSLIKSUZLKSLIveO  для связных и  veO( )),/( vKSLIKSUZLKSLI для несвязных графов, причем KSLI  0,02 e   0,020,0025 e  0,00005 e является малой величиной по сравнению с .e В древовидной реализации MST-алгоритма Краскала (алгоритм TREE) каждая из операций KSLIKNOVKPRIKPUS ,,, имеет сложность )1(O и выполняется в процедуре merge/union. Общая сложность этих операций составит )(eO  и )(eO для связных и несвязных графов соответственно. Сложность операций make set составляет )(vO . Операции find set выполня- ются для каждого ребра дважды, т.е. имеем e2 или e2 входов в процедуру find set. Сложность обновления указателей в древовидной структуре с опе- рациями объединения по рангу и сжатия пути (для сжатия пути применяется двойной проход от листа до корня дерева) определяется как ),( ve или ),( ve , где ),(  — очень медленно растущая инверсная функция Аккерма- на. Поэтому сложность древовидной реализации MST-алгоритма TREE без сложности сортировки ребер составит )),(( veeveO   или )),(( veeveO  . В работах Тарьяна и ван Леувена [27, 28] были рассмот- рены также однопроходные варианты эвристик со сжатием пути. Однако, по 0 2 4 6 8 10 12 14 16 18 1 2 3 4 5 6 7 8 9 10 11 12 Число вершин в графе в тыс. В ре м я в се к. SORT LINK TREE PRIM Рис. 3. Сравнение времени работы алгоритмов на несвязных графах c полными изолированными подграфами в зависимости от числа вершин в графе Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології, 2015, № 3 59 нашему мнению, сложность однопроходных процедур find set на практике не будет сильно отличаться от двухпроходных, так как в оценках однопро- ходных процедур скрыты дополнительные константы накладных расходов на их реализацию. Определенный интерес представляет скорость роста функции ),/( vKSLIKSUZLKSLI и в алгоритме Краскала. Тарьян показал [28], что полученная им оценка )),(( vmmO  , где em  или em  асимптотически неулучшаема. В настоящей работе мы экспериментально показали, что в практиче- ских случаях алгоритм LINK, реализованный на списочных структурах с ис- пользованием массивов работает не хуже чем алгоритм, основанный на дре- вовидных АТД с использованием операций сжатия пути и объединения по рангу. На рис. 4 показано число операций производимых для обновления ука- зателей алгоритмами LINK )(KSUZL и TREE )(KSUZT для данных из таб- лицы. ВЫВОДЫ Подводя итог по оценке сложности алгоритмов SORT, LINK и TREE можно сделать следующие выводы: 1. Для связных графов практическая временная сложность обоих алгоритмов построения MST-дерева с «карманной» сортировкой (bucket sort) весов ребер составляет )(eO операций, так как значения ),/( vKSLIKSUZLKSLI , ),( vee  , )( ve  нуль сравнимы со значением ,e где e — число просмотренных отсортированных ребер графа для построе- ния MST-дерева. 2. Для несвязных графов сложность построения MST-леса с «кар- манной» сортировкой и использованием алгоритма LINK —  eveO( )),,/( vKSLIKSUZLKSLI использованием алгоритма TREE —  veO( )),,( veee  но ),/( vKSLIKSUZLKSLI на практике растет медленнее, чем ).,( vee 3. Во всех прогонах алгоритм LINK оказывался немного быстрее алго- ритма TREE. 0 1000 2000 3000 4000 5000 100 0 300 0 500 0 700 0 900 0 110 00 Число вершин в графе Ч ис ло о пе ра ци й о бн ов ле ни я ук аз ат ел ей KSUZL KSUZT Рис. 4. Сравнение алгоритмов LINK ( KSUZL ) и TREE ( KSUZT ) по числу опера- ций обновления указателей при построении MST-дерева на полных связных графах А.Н. Трофимчук, В.А. Васянин ISSN 1681–6048 System Research & Information Technologies, 2015, № 3 60 4. Сложность предложенного алгоритма построения MST-дерева для связных графов с использованием алгоритмов SORT и LINK порядка )(eO получена для практических случаев. В то же время до сих пор не известно о существовании алгоритма построения MST, для которого строго доказано, что его временная сложность составляет )(eO в среднем или в худшем слу- чае для разреженных графов. Поэтому разработка алгоритмов с гарантиро- ванной линейной оценкой для разреженных графов все еще остается недос- тижимой целью [14]. Интенсивному изучению подверглись различные варианты алгоритма Борувки как базиса алгоритмов для вычисления MST на сильно разреженных графах за почти линейное время, а также рандомизиро- ванные алгоритмы поиска MST, математическое ожидание времени работы которых сравнимо с )( veO  [15]. Такие исследования вселяют надежду на успех и будоражат энтузиазм разработчиков более быстрых алгоритмов по- строения MST. 5. В целом эксперимент показал высокую вычислительную эффектив- ность алгоритмов, которые могут с успехом применяться при решении практических задач определения оптимальных остовных деревьев (лесов) для графов и сетей большой размерности. В частности, предложенные алго- ритмы могут быть включены в состав типового инструментария разработ- чика программ и использоваться при решении различных задач анализа и проектирования коммуникационных сетей. ЛИТЕРАТУРА 1. Boruvka O. O jistém problému minimálním // Pràca Moravské Prirodovedecké Spolecnosti. — 1926. — 3. — P. 37–58. 2. Nešetřil J.E., Milková H., Nešetřilová. Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history // Discrete Mathematics. — 2001. — 233 (1–3). — P. 3–36. 3. Jarník V. O jistém problému minimálním // Práce Moravské Prirodovedecké Spolec- nosti. — 1930. — 6. — P. 57–63. 4. Prim R.C. Shortest Connection Networks and Some Generalizations // Bell Syst. Tech. J. — 1957. — 36. — P. 1389–1401. 5. Dijkstra E. A note on two problems in connexion with graphs // Num. Math. — 1959. — 1. — P. 269–271. 6. Kruskal J.B. On the Shortest Spanning Subtree of a Graph and the Traveling Sales- man Problem // Proc. Amer. Math. Soc. — 1965. — 7. — P. 48–50. 7. Loberman H., Weinberger A. Formal procedures for connecting terminals with a minimum total wire length // Journal of ACM. — 1957. — 4. — P. 428–437. 8. Sollin M. Le tracé de canalisation // Programming, Games, and Transportation Net- works (in French). — 1965. 9. Tarjan R.E. Data Structures and Network Algorithms. — Philadelphia: Society for Industrial and Applied Mathematics, 1983. 10. Graham R.L., Hell P. On the History of the Minimum Spanning Tree Problem // An- nals of the History of Computing. — 1985. — 7(l). — P. 43–57. 11. Кнут Д. Искусство программирования для ЭВМ. Т.3 (Сортировка и поиск). — М.: Мир, 1978. — 800 с. 12. Ahuja R.K., Orlin J.B., Magnanti T.L. Network flows: theory, algorithms, and appli- cations. — New Jersey: Prentice-Hail, Inc. Upper Saddle River, 1993. — 846 p. Время работы алгоритма Краскала с древовидной и списочной структурой данных Системні дослідження та інформаційні технології, 2015, № 3 61 13. Ахо А., Дж. Хопхрофт, Дж. Ульман. Структуры данных и алгоритмы: Пер. с англ.: Уч. пос. — М.: Издательский дом «Вильяме», 2000. — 384 с. 14. Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах: Пер. с англ. — СПб: ООО «ДиаСофтЮП», 2002. — 496 с. 15. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1296 с. 16. Mehlhorn K., Sanders P. Algorithms and Data Structures. The Basic Toolbox. — Springer-Verlag Berlin Heidelberg, 2008. — 305 p. 17. Boost.org. Boost C++ Libraries. — www.boost.org. 18. LEDA (Library of Efficient Data Types and Algorithms). — www.algorithmic- solutions.com. 19. Goodrich M.T., Tamassia R. JDSL — the data structures library in Java. — http://www.jdsl.org/. 20. Васянин В.А. О вычислительной эффективности одного алгоритма для нахож- дения основного леса графа с минимальным (максимальным) весом // Еко- логічна безпека та природокористування: Зб. наук. праць. — Київ, 2009. — Вип. 4. — С. 155–169. 21. Tarjan R.E. Efficiency of a good but not linear set union algorithm // Journal of the ACM. — 1975. — 22, № 2. — P. 215–225. 22. Gabow H.N., Galil Z., Spencer T., Tarian R.E. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs // Combinatorica. — 1986. — 6. — P. 109–122. 23. Chazelle B. The Soft Heap: An Approximate Priority Queue with Optimal Error Rate // Journal of the ACM. — 2000. — 47. — P. 1012–1027. 24. Chazelle B. A minimum spanning tree algorithm with inverse-Ackermann type com- plexity // Journal of the ACM. — 2000. — 47. — P. 1028–1047. 25. Pettie S., Ramachandran V. An optimal minimum spanning tree algorithm // In 7th International Colloquium on Automata, Languages and Programming: of Lecture Notes in Computer Science, Springer, 2000. — 1853. — P. 49–60. 26. Pettie S., Ramachandran V. Randomized minimum spanning tree algorithms using exponentially fewer random bits // ACM Transactions on Algorithms. — 2008. — 4, № 1. — P. 1–27. 27. Tarjan R.E., Leeuwen J.V. Worst-Case Analysis of Set Union Algorithms // J. of the ACM. — 1984. — 31, № 2. — P. 245–281. 28. Tarjan R.E. Amortized computational complexity // SIAM J. on Algebraic and Dis- crete Methods. — 1985. — 6, № 2. — P. 306–318. Надійшла 15.06.2014

Время работы алгоритма Краскала с древовидной и списочной структурой данных

Institution

Ähnliche Einträge