20
правок
Алгоритм Фрюхтермана-Рейнгольда: различия между версиями
Материал из WEGA
Алгоритм Фрюхтермана-Рейнгольда (посмотреть исходный код)
Версия от 12:21, 10 октября 2019
, 10 октября 2019нет описания правки
Omeln (обсуждение | вклад) |
Omeln (обсуждение | вклад) мНет описания правки |
||
| Строка 1: | Строка 1: | ||
Алгоритм Фрюхтермана-Рейнгольда ([[Fruchterman T. M. J.|Fruchterman T. M. J.]]-[[Reingold E. M.|Reingold E. M.]])) относится к семейству [[силовые алгоритмы | силовых алгоритмов (forced-directed)]] [[Укладка графа|укладки графов]] на плоскости, в котором используется пружинная физическая модель, где [[Вершина|вершины]] определяются как тела системы, а [[Ребро|ребра]] как пружины. Силы могут действовать только на [[Вершина|вершины]], вес пружин при этом не учитывается. | |||
= Постановка задачи = | = Постановка задачи = | ||
Имеется простой неориентированный граф <math>G = (V, E)</math>. У каждой [[Вершина|вершины]] из множества <math>V</math> в качестве переменных используются координаты ее размещения <math>V_x</math> и <math>V_y</math>, а также <math>V_f</math> - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы. Результатом [[алгоритм|алгоритма]] будет [[Layout|размещение графа (layout)]]. | |||
= Описание алгоритма = | = Описание алгоритма = | ||
| Строка 12: | Строка 11: | ||
# Повторяются шаги 2-3 | # Повторяются шаги 2-3 | ||
Алгоритм не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций. Для достижения хорошего результата 100 итераций достаточно. | [[Алгоритм]] не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций. Для достижения хорошего результата 100 итераций достаточно. | ||
= Описание модели = | = Описание модели = | ||
| Строка 34: | Строка 33: | ||
= Применение = | = Применение = | ||
Алгоритм применяется для размещения простых неориентированных графов и хорошо работает для графов с количеством вершин не превышающих 100. | Алгоритм применяется для размещения простых [[Неориентированный_граф | неориентированных графов]] и хорошо работает для [[граф|графов]] с количеством вершин не превышающих 100. | ||
= Модификации = | |||
Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры. | Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры. | ||
