Решение задачи построения графа с минимальным коэффициентом растяжения методом локального поиска

DOI:

Коэффициент растяжения графа показывает степень искажения расстояний между вершинами. Основная цель построения плоского связного графа на заданном наборе точек с минимальным коэффициентом растяжения связана с поиском эффективного способа связи всех вершин графа. Такие графы имеют важное значение в различных приложениях, включая проектирование сетей связи, размещение элементов в вычислительных системах и оптимизацию маршрутов транспортных потоков. Задачи, связанные с данной характеристикой графов, изучаются в различных научных трудах. Каждый из этих результатов существенно обогащает теорию графов, однако применим исключительно к специфическим классам графов. Например, работы [5; 6; 9; 10] связаны с триангуляцией Делоне, [7] — с выпуклыми многогранниками, вершины которых (почти) лежат на сфере и др.

Метод локального поиска представляет собой эффективный подход к решению сложных оптимизационных задач путем последовательного улучшения текущего решения посредством небольших изменений структуры графа. Несмотря на свою простоту, этот метод часто позволяет находить высококачественные решения за разумное время вычислений. Однако его применение к минимизации коэффициента растяжения геометрических графов сопряжено с рядом сложностей. К их числу относятся: необходимость сохранения планарности в процессе итеративных изменений, оценка влияния локальной модификации на коэффициент растяжения графа, а также риск многократного возврата к уже пройденным состояниям.

Научная новизна состоит в разработке алгоритма локального поиска, в котором:

• 1)    описано локальное изменение графа, которое не нарушает его планарности и связности;

• 2)    предложена формула оценки влияния локальных изменений на коэффициент растяжения графа;

• 3)    разработана стратегия, исключающая многократный возврат к ранее рассмотренным состояниям, что обеспечивает сходимость алгоритма.

Цель настоящей статьи заключается в разработке алгоритма локального поиска для минимизации коэффициента растяжения графа.

1.    Постановка задачи

Определение 1. Средним коэффициентом растяжения графа G ( V,E ) называется среднее для всех пар вершин отношение длины пути между этими вершинами к прямолинейному пути между ними:

\; =

Е i=j,1

d _G ( v i ,V j ) d ( v i ,V j )

N ( N - 1)

Определение 2. Средними потерями графа G будем называть средний коэффициент растяжения, выраженный в процентах:

^ g % = ( A g — 1) * 100.

Задача. Дан конечный набор узлов V = v ₁ ,v ₂ ,...,v ^ . Построить плоский неориентированный граф G ( V,E ) с минимально возможным средним коэффициентом растяжения.

В статье [4] доказана NP-полнота этой задачи. Исходя из допущения об истинности неравенства Р = NP, она не может быть решена никаким полиномиально-временным алгоритмом.

Таким образом, при решении NP-трудной задачи обязательно нужно жертвовать скоростью, правильностью или универсальностью. Для задачи 1 скорость и универсальность стоит в приоритете, в то время как можно удовлетвориться «приближенно правильным» решением. Хорошим вариантом в данной ситуации будет использование алгоритма локального поиска. Алгоритм локального поиска исследует пространство допустимых решений с помощью локальных ходов, которые один за другим улучшают целевую функцию. Подробно ознакомиться с принципами локального поиска можно в книге [2].

2.    Основные характеристики локального поиска

Алгоритм локального поиска предполагает 5 шагов [2]:

• 1)    определить допустимые решения;

• 2)    определить целевую функцию;

• 3)    определить разрешимые локальные ходы;

• 4)    решить, как выбрать первое допустимое решение;

• 5)    решить, как выбрать один из нескольких улучшающих локальных ходов.

Согласно работе [3] для решения поставленной задачи необходимо строить триангуляцию. Таким образом, в качестве допустимых решений нужно рассматривать все триангуляции. Согласно статье [8], верхняя оценка числа триангуляций O(59 ^N N ^{- 6} ). К счастью, алгоритм локального поиска не предполагает перебор всех триангуляций.

Целевой функцией является Л о

За локальный переход можно взять замену одного ребра другим, выполняя нижеописанные шаги.

• 1)    Выбираем не принадлежащее грани ребро (a, b), для которого существует такая пара вершин с и d, что выполнены следующие условия:

• •    четырехугольник ( а, с, b, d ) выпуклый;

• •    четырехугольник ( a,c,b,d ) не содержит внутри себя другие вершины;

• •    замена ребра ( a, b ) на ( с, d ) не приводит к повторному формированию триангуляции, полученной на предшествующих итерациях.

• 2)    Если Л_опосле замены уменьшился, то переход считается успешным.

3.    Алгоритм решения задачи поиска графа с минимальным коэффициентом растяжения методом локального поиска

В качестве первого допустимого решения могут выступать разные триангуляции, причем чем больше запусков алгоритма с разными начальными решениями, тем более близкий к оптимальному получается итог, ведь алгоритм локального поиска приводит только в локальный минимум. Таким образом, при разных стартах могут получиться разные локальные минимумы.

В данной работе за начальные допустимые решения берутся случайные триангуляции и триангуляция Делоне из-за ее полезных свойств.

• 1)    Выбрать начальную триангуляцию G любым способом. Для ускорения работы алгоритма на шаге 3) необходимо провести предварительную обработку.

• •    Составить словарь shortest_paths. Ключами в этом словаре являются пары вершин (s,t), а значениями — кратчайший путь из s в t в графе G.

• •    Для каждого ребра составить список путей из shortest_paths, в которых это ребро участвует.

• 2)    Среди всех допустимых локальных переходов выбрать т наиболее улучшающих значение целевой фунции. Значение т выбирается до начала работы алгоритма. Чем оно выше, тем точнее и дольше работает алгоритм. Если успешных локальных переходов из текущей триангуляции нет, значит найден локальный минимум, и для данной ветки алгоритм заканчивается.

• 3)    Заменить ребро ( a,b) на ( с,^.

• •    Удалить ребро ( a,b ) , а все пути, проходящие по нему, заменить на актуальные любым алгоритмом поиска кратчайшего пути в графе. Л с при замене пути из s в t меняется по формуле:

  Л с = Л с +

  
  

d G \( _a,b ) ( s,t ) - d _G ( s,t d ( s,t ) N ( N - 1)

• •    Вставить ребро ( c,d ) . Все пути, проходящие по ребрам (с, а) и ( a,d) или ( c,b) и ( b,d), сокращаются. Л с при укорачивании пути из s в t, ранее проходящего через вершину а, меняется по формуле:

  ^Л с = ^Л с +

  
  

  d ( c, d ) — ( d ( c, а) + d ( a, d )) d ( s,t ) N ( N — 1)

  
  
  
  

Для путей, ранее проходящих через вершину b, формула аналогична.

• 4)    Алгоритм может закончиться естественным или искусственным образом.

• •    Естественный способ подразумевает попадание в локальный минимум на всех ветках алгоритма. Если за т была выбрана единица, то найденный единственный локальный минимум и является решением алгоритма, иначе среди полученных решений выбирается триангуляция с минимальным Лс.

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

3.1.    Оценка точности алгоритма

С ростом количества точек количество различных триангуляций растет слишком сильно. Результаты экспериментов по перебору всех триангуляций отражены на рисунке 1. Для наглядности значения по оси ординат приведены с масштабирующим множителем 10 7 . Но для малых N все-таки возможно исчерпывающе оценить сложность алгоритма, так как можно получить точное решение перебором всех триангуляций [1].

Рис. 1. Зависимость количества различных триангуляций от количества точек

В ходе эксперимента за начальные выбирались две случайные триангуляции. Решением называлась триангуляция с меньшим коэффициентом растяжения. Средние потери, полученные в результате работы алгоритма, составляют 4,5 %. Рисунок 2 отражает распределение погрешностей полученных триангуляций относительно минимально возможных значений: по оси абсцисс отложена величина погрешности в процентах, по оси ординат — количество экспериментов, в которых была достигнута соответствующая погрешность. В 5 % случаев результатом являлась оптимальная триангуляция (погрешность равна нулю).

Выбор начальной триангуляции сильно влияет на результат. Чем ниже начальный коэффициент растяжения, тем лучше результат. Это ожидаемо, так как локальных минимумов непредсказуемо много. Поэтому разумно брать сразу хорошую триангуляцию. На роль таковой отлично подходит триангуляция Делоне из-за особых свойств и известных способов построения. В этом случае средние потери, полученные в результате работы алгоритма, составляют 3,3 %. Рисунок 3 отражает распределение погрешностей полученных триангуляций относительно минимально возможных значений. При этом триангуляция Делоне являлся оптимальной в 38 % случаев, а локальным минимумом — в 58 %. Оптимальная триагуляция как результат получилась в 55 % случаев.

Во всех экспериментах, даже в тех, в которых поиск оптимальной триангуляции методом перебора занимает неразумно много времени, алгоритм снижает потери в среднем до 5,7 %, а снижение потерь при выборе случайной триангуляции отражено на рисунке 4, в среднем около 17 %.

Но если взять в качестве начальной триангуляцию Делоне, то потери составляют

Погрешность, %

Рис. 2. Погрешность работы алгоритма для малых N . В качестве начальных выбирались

Рис. 3. Погрешность работы алгоритма для малых N. В качестве начальных выбирались триангуляции Делоне в среднем 4,1 %, снижение потерь отражено на рисунке 5, в среднем около 0,16 %.

3.2.    Оценка временной сложности алгоритма

Для экспериментальной оценки эффективности алгоритма локального поиска были проведены замеры времени выполнения на входных данных размером от 10 до 40 точек. В качестве начальной конфигурации использовалась триангуляция Делоне при параметре т = 1 с естественным выходом. Полученные результаты (рис. 6) свидетельствуют об экспоненциальной зависимости времени работы от объема входных данных, что ограничивает применимость алгоритма на больших наборах. Основываясь на этих данных, можно установить практический предел в 50 точек: превышение этого порога делает вычисления непрактичными, поскольку время ожидания превышает один час.

Снижение коэффициента растяжения, %

Рис. 4. Снижение потерь в результате работы алгоритма. В качестве начальных выбирались случайные триангуляции

Рис. 5. Снижение потерь в результате работы алгоритма. В качестве начальных выбирались триангуляции Делоне

Сравнение с алгоритмом полного перебора (см. рис. 7), где для наглядности значения по оси ординат приведены с масштабирующим множителем 10 ⁷ , показывает, что несмотря на экспоненциальную сложность предложенный подход обеспечивает существенный выигрыш в производительности за счет сокращения пространства поиска. Дальнейшее масштабирование алгоритма требует перехода к параллельным вычислениям.

Рис. 6. Сравнение зависимости затраченного времени от количества точек для алгоритма локального поиска.

Рис. 7. Сравнение зависимости затраченного времени от количества точек для алгоритма простого перебора

Заключение

В настоящей работе представлен метод локального поиска для решения задачи построения графа с минимальным коэффициентом растяжения. Подобно другим эвристическим алгоритмам, разработанный подход не гарантирует получение идеального результата, однако позволяет находить триангуляции с потерями около 4,1 %, что свидетельствует о высоком качестве найденных решений.