1294
правки
Силовые алгоритмы: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 14: | Строка 14: | ||
= Алгоритмы = | = Алгоритмы = | ||
Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости или в пространстве, при котором достигается равновесие всех сил, действующих на вершины графа | Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости или в пространстве, при котором достигается равновесие всех сил, действующих на вершины графа. | ||
Простейший из них — это алгоритм, который работает в два следующих этапа. | |||
На первом этапе вершины размещаются на плоскости случайным образом. | На первом этапе вершины размещаются на плоскости случайным образом. | ||
Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин силы и для тех из них, для которых , происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. | Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин силы и для тех из них, для которых , происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. | ||
Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил. | Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил. | ||
Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние | Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние вершины находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные вершины хорошо разнесены. | ||
* [[Алгоритм | * [[Алгоритм Идеса]] (P.Eades) | ||
* [[Алгоритм Фрюхтермана-Рейнгольда]] (Fruchterman | * [[Алгоритм Фрюхтермана-Рейнгольда]] (T.Fruchterman, S.Reingold) | ||
* [[Алгоритм | * [[Алгоритм Камады-Каваи]] (T.Kamada, S.Kawai) | ||
* [[Метод | * [[Метод барицентров Тутте]] (W.Tutte) | ||
= Применение и реализации = | = Применение и реализации = | ||
| Строка 43: | Строка 42: | ||
= Открытые проблемы = | = Открытые проблемы = | ||
Полезность базового силового подхода ограничена небольшими графами, и результаты плохи для графов с более чем несколькими сотнями [[Вершина|вершин]]. Есть несколько причин, почему силовые алгоритмы не работают хорошо для больших графов. | Полезность базового силового подхода ограничена небольшими графами, и результаты плохи для графов с более чем несколькими сотнями [[Вершина|вершин]]. Есть несколько причин, почему силовые алгоритмы не работают хорошо для больших графов. Одно из основных препятствий для масштабируемости этих подходов является то, что физическая модель обычно имеет много локальных минимумов. Даже с помощью сложных механизмов для избегания локальных минимумов силовые алгоритмы не способны постоянно производить хорошие размещения для больших графов из-за проблем с разрешением, поскольку для больших графов минимальное расстояние между вершин становится весьма небольшим. Вместе с тем возникают различные расширения классических силовых алгоритмов, например, связанные с использованием многоуровневого подхода к изображению графа или с переходом при его изображении к геометрии, отличной от геометрии Евклида, позволяющие расширять применимость силовых алгоритмов на графы с десятками тысяч и даже с сотнями тысяч вершин. | ||
= Литература = | = Литература = | ||
* Handbook of graph drawing and visualization / ed. by R. Tamassia [et al.]. – Boca Raton: CRC Press, 2013. – 862 p. | |||
* Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c. | |||
* Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с. | |||
[[Категория:Визуализация графов]] | [[Категория:Визуализация графов]] | ||