Диссертация (1137145), страница 14
Текст из файла (страница 14)
Однако, он невнес существенного вклада в общую эффективность структуры.921Точность0,80,60,40,200E+00 1E+04 2E+04 3E+04 4E+04 5E+04 6E+04 7E+04 8E+04 9E+04 1E+05Количествозапросовm=1m=2m=4Рис. 44. Точность поиска после улучшения свойств структуры с помощью примененияпроцедуры Repair_By_QueryСокращениечиславычисленияметрики1001010,50,6100kqueries0,7 Точность0,80queries0,911mqueriesРис 45. Общая производительность структуры после применения процедурыRepair_By_Query3.9 ВыводыВ главе эмпирически исследовались свойства алгоритмов предложенныхвовторойглаве.Былопоказано,чтосвысокойвероятностью,предложенные алгоритмы позволяют формировать структуру обладающуюнавигационными свойствами тесного мира.93Так же были исследованы такие свойства структуры, как средняя длинакратчайшего пути между всеми парами вершин, диаметр графа,коэффициент кластеризации, средняя длинна пути пройденная жаднымалгоритмом, устойчивость к выпадению произвольных вершин, точностьпоиска k-ближайших, количество вычислений функции расстоянияалгоритмом поиска.
Была устанавливалась взаимосвязь этих характеристики параметров алгоритмов. Эксперименты производились на различныхвходных данных. Использовались как синтетические данные, так иреальные наборы данных.Были установлены следующие факты:• распределение степеней вершин в формируемой структуреподчиняется экспоненциальному закону,• средняя длина кратчайшего пути в графе в формируемом графепропорциональна log ()• при достаточном большом параметре k, алгоритм добавлениястроит граф имеющий постоянный коэффициентом кластеризации.• Значение коэффициента кластеризации уменьшается с ростомразмерности пространства.• Если рассматривать совокупность предложенных алгоритмов какструктуру данных для приближенного поиска k-ближайшихсоседей, то в сравнении с другими известными алгоритмами,предложенныеалгоритмыдемонстрируютприсравнимойточности значительно меньшую вычислительную сложность• Вычислительнаясложностьалгоритмапоискасоседей k-NNSearch пропорционально O(log ()! )94k-ближайшихГлава 4.
Математическая модель оптимальных графовдля распределённого поискаПредыдущие главы можно рассматривать в качестве демонстрациисостоятельности подхода, при котором информация для эффективногоиспользованияорганизуетсянетрадиционнымспособомввидеиерархической структуры, а в виде сети (в некотором роде равноправныхинформационных объектов, сущностей). то есть в виде графа в самомобщем смысле.
Алгоритмы приведенные в главе 3 являются примерамитого, как может быть сконструирована сеть (см. Алгоритм добавления), соструктуройпозволяющей,решатьзадачуближайшегососедадецентрализованным алгоритмом поиска.В данном месте хотелось бы уточнить понятие распределённого то естьдецентрализованного алгоритма. Алгоритм , работающий на графе(, ) будем называть децентрализованным, если в каждый моментвремени = 1, алгоритм располагает информацией о множестве вершин! ⊆ и в момент алгоритм может расширить своё знание ! , только засчёт множества смежных вершин из тех, которых он знает, то есть вмомент времени + 1 алгоритм может иметь информацию о множествевершин !!! ⊆!∈!! ∪ ! .
Выбор множества !!! определеляетсяконктерным алгоритмом. Предполагается, что изначально множествоизвестных вершин алгоритму состоит из одной вершины ∈ , с которойалгоритм начинает работать ! = {}.В этой главе поднимается вопрос о существовании оптимальнойструктурысетисточкизренияэффективностификсированногодецентрализованного алгоритма поиска. При этом учитывается требованиена то, что алгоритм поиска должен всегда заканчиваться успехом, начинаяработу от произвольного узла сети, то есть в результате поиска долженбыть обнаружен узел, являющийся ближайшим к заданному запросу.
Под95эффективностью алгоритма поиска понимается его вычислительнаявычислительная сложность.В качестве операции, вносящей основной вклад во время работыалгоритма и в создаваемую нагрузку на систему в целом, можнорассматривать две операции: операцию получения списка смежныхвершин и операцию вычисления расстояния между любыми двумяобъектами (вершинами) известными алгоритму на текущий момент.Таким образом в главе демонстрируется идея существования дляфиксированного алгоритма поиска и для фиксированного множестваобъектов с заданной функцией расстояния : × → ! оптимальнойконфигурации рёбер графа с точки зрения вычислительной сложностиалгоритма поиска .В данном случае в качестве децентрализованного алгоритма поискарассматривается алгоритм GreedyWalk, а в качестве элементарнойоперации рассматривается операция вычисления функции расстояния.Материалы главы опубликованы в [Ponomarenko A., Utkina I., Batsyn M.,2017]4.1 Предпосылки разработки моделиГлавная мотивация данной модели заключается в изучение точныхрешений модели, которые могут быть найдены с помощью либоуниверсальных солверов, например таких как cplex, или при помощисобственной реализации одного из точных методов, например методаветвей и границ [E.L.
Lawler, D. E. Wood, 1966], или метода branch and cut[M. Tawarmalani, N. V. Sahinidis, 2005]Более того,данная модель необходима для оценки качестваэвристических алгоритмов. В частности алгоритмом предложенным вглаве 3 (сложность построения графа (()! ∗ ∗ ) ), далеки отточного решения.
В виду того, что данная задача видится NP трудной96задачей, и при том условии, что эвристические решения позволяютобнаружить с большой вероятностью достаточно близкие решения коптимальному, данная модель может сделать вклад в исследование NPтрудных задач.4.2 МодельПусть D - домен (множество всевозможных объектов); V ⊆ D конечноеподмножество и пусть f : D → R+плотность распределения запросов.Математическая модель задачи построения оптимальной структуры надмножеством V для децентрализованного поиска ближайшего соседаалгоритмом Greedy-Walk с заданной функцией плотности распределениязапросов f описывается набором неравенств (1)-(9).Переменные⎧1, if edge (i, j) belongs to the solutionxij = ⎨⎩0, otherwise(1)⎧1, if vertex k belongs to the greedy walk from i to jyijk = ⎨⎩0, otherwise(2)Целевая функция1 nmin ∑ ∑ O(i, jq ) f (q) ,n i=1 q∈D(3a)1 nmin ∑ ∫ O(i, jq ) f (q)dq ,n i=1 D(3б)где jq = arg min d ( j, q)(4)j =1, n{}O(i, jq ) = l ∈ V : ∃k xlk = 1and yijk = 1qОграничения97(5)xii = 0 ∀i ∈V(6)jyiji = yijq = 1 ∀i, jq ∈ Vq(7)qn∑xlkk=1yijk ≥ yijlqq∀i, jq ,l ∈ V(8)*l * = arg min (σ (l,q)) ⇒ yijl ≥ yijkql∈V: xkl =1q∀i, jq ,k ∈ V , jq ≠ i,k ≠ jq(9)Переменные !" (1) определяют матрицу смежности оптимального!графа, который требуется найти.
Переменные индикаторы !"(2)используются для подсчёта числа операций (, ! ) выполняемых во времяпроцедуры поиска от вершины , вершины ! , которая является ближайшейк запросу (4). В данном случае это количество различных вершин, отзапроса до которых было вычислено расстояние. Это число равно!мощности объединения окрестности вершины , для которых !"= 1 (5).Так как требуется найти оптимальную структуру для всех возможныхвариантов запросов и стартовых вершин, целевая функция выглядит каксреднее число операций необходимое для того, чтобы достигнуть вершины(3а, 3б, 4, 5). Ограничение (6) гарантирует отсутствие циклов.
В своюочередь ограничение (7)требует, чтобы процедура GreedyWalk( , )начиналась в вершин и заканчивалась в вершине . Неравенство (8)!связывает переменные !" и !", при этом оно требует, чтобы жадныйалгоритм поиска также проходил через какую-либо вершину изокрестности вершины , если он проходит через вершину .
Ограничение(9) описывает жадную стратегию алгоритма поиска: если вершина !входит в путь жадного алгоритма от вершины до вершины ! (!"= 1),тогда вершина ∗ ближе к , чем любая другая вершина из окрестности ,!и она тоже принадлежит жадному пути (!!= 1).йДаннаямодельприменимадляпроизвольногометрическогопространства. Далее в разделе 4.3 приведены результаты для частного98случая, когда вершины совпадают с узлами регулярной целочисленнойдвумерной решётки с функцией расстояния ! , ! и ! .4.3 Алгоритм Табу-поиска решений предложенной моделиПо причине того, что пространство решений предложенной модели крайневелико (размер пространства решений равен числу возможных рёбер графа2n(n−1)/2 ), было принято решение не использовать универсальные решатели(LpSolve, siplex).
Вместо этого был разработан и реализован алгоритмоснованный на методе ветвей и границ для поиска точных решений наданных небольшого объёма. Для поиска решений на больших объёмах былразработан эвристический алгоритм основанный на метаэвристики Табупоиск (поиска с запретами) [F. Glover 1989]. Алгоритм был разработансовместно с Ириной Уткиной. Авторство программная реализаций обоихалгоритмов также принадлежит Ирине.алгоритма приведён на рисунок 46.99Псевдокод эвристическогоTaboo( number _ of _ fails ∈ Ν , number _ of _ steps ∈ Ν )0102while(true)E ʹ ={(a,b),(c,d ) : a,b,c,d ∈ V ,(a,b) ∉ E,(c,d ) ∈ E}03action = argmin( f )04f _ min = min ( f )e∈ E "eÎ E ʹ05if flag == true then06do action to G07add edges e from action to taboo list08flag = false09else10if f _min == opt then11flag = true12if opt < global _ opt then13global _ opt = opt14global _ G = G15fails = 016else17fails + +18if fails == number _ of _ fails then19return global_G20else21do action to GРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
