Диссертация (1137145), страница 11
Текст из файла (страница 11)
Квадратныемаркеры на графике 3Кроме того для сравнения на графике приводится информация ораспределение длин кратчайших путей «GW» от вершины графаявляющихся ближайшими к точкам запросам из множества и всемиостальными вершинами графа.Очевидно, что количество шагов необходимое алгоритму GreedyWalkдля нахождения оптимума не может быть меньше, чем длиннакратчайшего пути между глобальным минимумом и вершиной, с которойалгоритм стартует. Поэтому вполне ожидаемо, что процент успешных«жадных» поисков, имеющих длину менее длины кратчайшего пути, равеннулю.
Большому числу коротких неуспешных поисков соответствуетлевый горб ряда «GW».Так же закономерно увеличения общего числа успешных поисков сростом параметра u, уменьшением и исчезновением горба неуспешныхкоротких «жадных» поисков ряда «GW». Для значения параметра u=10 (4й сверху график) горб соответствующим коротким «жадным» путямполностью отсутствует и распределение длины пути жадного алгоритма65совпадает с процентом успешных поисков, что свидетельствует о том, чтокаждый поиск завершается успехом.Стоит отметить, чтобы внести в эксперимент большую определенность,значение параметра w было выбрано достаточно большим (w=20), для тогочтобы во время добавления каждый элемент гарантированно соединялся сu ближайшими элементами присутствующих в данный момент времени вструктуре.Эксперимент аналогичный эксперименту со 100,000 случайнымиточками из единичного отрезка прямой был произведен для размерности2,3,4,10 и 20. Результаты экспериментов приведены на рисунке 29 дляразмерности 2 (параметр dim), на рисунке 30 – для размерности 3, нарисунке 31 для размерности 4, на рисунке 32 для размерности 10 и нарисунке 33 для размерности 20.6620%18%gw16%14%succeed12%sp10%dim:1u:2recall:0,2558458%6%4%2%0%0510152025303540455025%gw20%succeed15%spdim:1u:3recall:0,69999010%5%0%0510152025303540455025%gw20%succeed15%sp10%dim:1u:4recall:0,8948255%0%0510152025303540455030%gw25%succeed20%sp15%dim:1u:5recall:0,9572610%5%0%0510152025Длина3035404550Рис.
27. Распределение длины пути жадного алгоритма до остановки в локальномминимуме – ряд «gw». Процент успешных поисков данной длинны – ряд «succeed»Распределение длин кратчайшего пути - ряд «sp». Входные данные – 100,000 точекравномерно распределенных в единичном отрезке. Параметры алгоритма добавления:w = 20; u=2;3;4;5 для графиков с верху вниз соответственно. «dim” – размерностьпространства.6730%gw25%succeed20%sp15%dim:1u:6recall:0,98242510%5%0%051015202530354035%30%gw25%succeed20%sp15%dim:1u:10recall:0,99924510%5%0%051015202530354045%gw40%35%succeed30%sp25%20%dim:1u:20recall:115%10%5%0%051015202530354060%gw50%succeed40%sp30%dim:1u:30recall:120%10%0%0510152025303540Рис.
28. Распределение длины пути жадного алгоритма до остановки в локальномминимуме – ряд «gw». Процент успешных поисков данной длинны – ряд «succeed»Распределение длин кратчайшего пути - ряд «sp». Входные данные – 100,000 точекравномерно распределенных в единичном отрезке.
Параметры алгоритма добавления:dim=1 w = 20; u=6;10;20;30 для графиков с верху вниз соответственно.6820%gw15%succeedsp10%dim:2u:2recall:0,0793155%0%0510152025303540455025%gw20%succeed15%spdim:2u:3recall:0,51881510%5%0%0510152025303540455025%gw20%succeed15%sp10%dim:2u:4recall:0,5228485%0%0510152025303540455040%35%gw30%succeed25%sp20%dim:2u:10recall:0,97163515%10%5%0%05101520253035404550Рис. 29. Распределение длины пути жадного алгоритма до остановки в локальномминимуме – ряд «gw». Процент успешных поисков данной длинны – ряд «succeed»Распределение длин кратчайшего пути - ряд «sp». Входные данные – 100,000 точекравномерно распределенных в единичном отрезке.
Параметры алгоритма добавления:dim=2 w = 20; u=2;3;4;10 для графиков с верху вниз соответственно.6925%gwsucceedsp20%15%dim:3u:2recall:0,03926510%5%0%051015202530354025%4550gwsucceedsp20%15%dim:3nn:3recall:0,31165510%5%0%051015202530354030%4550gwsucceedsp25%20%dim:3u:4recall:0,60702515%10%5%0%051015202530354040%4550gwsucceedsp35%30%25%20%dim:3u:10recall:0,97163515%10%5%0%05101520253035404550Рис. 30. Распределение длины пути жадного алгоритма до остановки в локальномминимуме – ряд «gw». Процент успешных поисков данной длинны – ряд «succeed»Распределение длин кратчайшего пути - ряд «sp».
Входные данные – 100,000 точекравномерно распределенных в единичном отрезке. Параметры алгоритма добавления:dim=3 w = 20; u=2;3;4;10 для графиков с верху вниз соответственно.7025%gwsucceedsp20%15%dim:4u:2recall:0,02798510%5%0%051015202530354030%gwsucceedsp25%20%dim:4u:4recall:0,4606515%10%5%0%051015202530354035%gwsucceedsp30%25%20%dim:4u:6recall:0,76006515%10%5%0%05101520253040%3540gwsucceedsp35%30%25%20%dim:4u:10recall:0,93103515%10%5%0%0510152025303540Рис.
31. Распределение длины пути жадного алгоритма до остановки в локальномминимуме – ряд «gw». Процент успешных поисков данной длинны – ряд «succeed»Распределение длин кратчайшего пути - ряд «sp». Входные данные – 100,000 точекравномерно распределенных в единичном отрезке. Параметры алгоритма добавления:dim=4 w = 20; u=2;3;4;10 для графиков с верху вниз соответственно.7135%gwsucceedsp30%25%20%15%dim:10u:2recall:0,0110110%5%0%024681012141650%1820gwsucceed40%30%dim:10u:5recall:0,21799520%10%0%024681012141660%1820gwsucceedsp50%40%30%dim:10u:10recall:0,50943565520%10%0%024681012141660%1820gwsucceedsp50%40%30%dim:10u:20recall:0,7468520%10%0%024681012141670%1820gwsucceedsp60%50%40%dim:10u:30recall:0,8371630%20%10%0%02468101214161820Рис.
32. Распределение длины пути жадного алгоритма до остановки в локальномминимуме – ряд «gw». dim = 107240%gwsucceedsp30%20%dim:20u:2recall:0,00619510%0%024681060%12gwsucceedsp50%40%30%dim:20u:10recall:0,20019520%10%0%0246880%1012gwsucceedspdim:20u:20recall:0,37615560%40%20%0%024681080%12gwsucceedsp60%40%dim:20u:40recall:0,5622120%0%0246810100%12gwsucceedsp80%60%dim:20u:60recall:0,66806540%20%0%0246810100%12gw80%succeed60%spdim:20u:70recall:0,6943840%20%0%024681012Рис.
33. Распределение длины пути жадного алгоритма до остановки в локальномминимуме – ряд «gw». dim = 20733.3 Средняя длина пути жадного алгоритма в графе взависимости от числа элементов в структуреГрафики, отражающие зависимость значения средней длины путижадного алгоритма от количества элементов в структуре для размерностей1,2,6 и 10 приведены на рисунке 34. Знаком «+» в легенде графиковобозначены кривые, соответствующие кривым, длинам путей жадныхпоисков, заканчивающихся успехом, то есть в результате, которых былобнаружен глобальный минимум.
Для большей наглядности, кривыесоответствующие одинаковым параметрам, обозначены одним цветом. Каквидно из графиков, средняя длина успешных поисков во всех случаяхбольше средней длины всех поисков (совокупности успешных и неуспешных). Ожидаемо, что с увеличением параметра «u», разность междузначением средней длинны пути успешных поисков и всех поисков,сокращается (кривые цвета охра на всех 4-х графиках). Кроме того, изграфиков видно, что кривые хорошо приближаются функцией логарифма.Однако кривые для параметра «u=2», возможно имеют рост нижелогарифма, что в свою очередь говорит о крайне маленькой стоимостижадного поиска при данных значениях пара метра «nn».74252520Длинапути30Длинапути20151015105501000100001000000100010000001000001000000Количествоэлементоввструктуре,nКоличествоэлементоввструктуре,n+dim=1;u=2dim=1;u=2+dim=1;u=3dim=1;u=3+dim=1;u=4dim=1;u=4dim=1;u=6+dim=1;u=61610000+dim=4;u=2;+dim=4;u=4+dim=4;u=6dim=4;u=9dim=4;u=2dim=4;u=4dim=4;u=6+dim=4;u=91014810ДлинапутиДлинапути1286464220100010000100000100000001000Количествоэлементоввструктуре,n+dim=6;u=2;+dim=6;u=5+dim=6;u=7dim=6;u=10100001000001000000Количествоэлементоввструктуре,n+dim=10;u=7dim=10;u=7+dim=10;u=10dim=10;u=10+dim=10;u=14dim=10;u=14dim=10;u=20+dim=10;u=20dim=6;u=2dim=6;u=5dim=6;u=7+dim=6;u=10Рис 34.
Зависимость средней длинны пути жадного алгоритма (включая неуспешныепоиски) в зависимости от числа элементов в структуре.751E+000100200300400500600700dim=1;u=6;size=100k1E-01dim=4;u=10;size=100kdim=10;u=4;size=100kДолявершин1E-02dim=10;u=20;size=100kdim=10;u=30;size=100k1E-031E-041E-051E-06СтепеньвершиныРис. 35.
Распределение степеней вершин. В структуре построенной над множеством из100 тысяч случайных точек распределенных равномерно в единичном гиперкуберазмерностью соответствующей параметру dim.3.4 Распределение степеней вершинИз графика на рисунке 35 легко увидеть, что распределение степенейвершин в графе подчиняется экспоненциальному закону. Подобнаякартина сохраняется и для других размерностей и при других параметрах,когда получается собирать структуру достаточно точно. Однако, когдатекущая структура сети или слишком высокая размерность уже непозволяют достаточно находить k-ближайших соседей этапе построения,распределение степеней вершин становится степенным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
