999
правок
Использование физических аналогий: различия между версиями
Перейти к навигации
Перейти к поиску
Использование физических аналогий (посмотреть исходный код)
Версия от 17:46, 21 октября 2024
, 21 октябрьнет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 7: | Строка 7: | ||
Наиболее простой подход состоит в использовании комбинации пружин и электронных сил, когда каждое ребро рассматривается как пружина, а вершины считаются одинаково заряженными частицами, между которыми действуют силы отталкивания. | Наиболее простой подход состоит в использовании комбинации пружин и электронных сил, когда каждое ребро рассматривается как пружина, а вершины считаются одинаково заряженными частицами, между которыми действуют силы отталкивания. | ||
Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости, при котором достигается равновесие всех сил, действующих на вершины графа. Простейший из них — это алгоритм, который работает в два следующих этапа. На первом этапе вершины размещаются на плоскости случайным образом. Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин | Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости, при котором достигается равновесие всех сил, действующих на вершины графа. Простейший из них — это алгоритм, который работает в два следующих этапа. На первом этапе вершины размещаются на плоскости случайным образом. Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин ''p'' силы ''F(p)'', и для тех из них, для которых ''F(p)≠Ō'', происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил. | ||
В общем случае методы, основанные на использовании физических аналогий, успешно дают хорошие результаты для относительно небольших графов, но не являются хорошо масштабируемыми. Большие графы часто приводят к тому, что функция энергии становится весьма трудной для достижения минимума. Более того, типичный алгоритм, реализующий данные методы, является итерационным. Во время каждой итерации позиции всех вершин переопределяются на основе предыдущей итерации, которая, вероятно, требует O(''n''<sup>2</sup> + ''m'') времени, где ''n'' и ''m —'' количество вершин и ребер соответственно. Хорошая раскладка обычно требует O(''n'') итераций. Следовательно, общая временная сложность алгоритма составляет O(''n''<sup>3</sup>) или даже O(''n''<sup>4</sup>). Кроме того, основанные на физических аналогиях алгоритмы раскладки не обладают предсказуемостью, и это означает, что один и тот же алгоритм, обрабатывая один и тот же граф, может получать совсем не похожие результаты. Непредсказуемость данных алгоритмов может вызывать в некоторых случаях серьезные проблемы, поскольку навигация пользователя сильно зависит от визуального представления графов. | В общем случае методы, основанные на использовании физических аналогий, успешно дают хорошие результаты для относительно небольших графов, но не являются хорошо масштабируемыми. Большие графы часто приводят к тому, что функция энергии становится весьма трудной для достижения минимума. Более того, типичный алгоритм, реализующий данные методы, является итерационным. Во время каждой итерации позиции всех вершин переопределяются на основе предыдущей итерации, которая, вероятно, требует O(''n''<sup>2</sup> + ''m'') времени, где ''n'' и ''m —'' количество вершин и ребер соответственно. Хорошая раскладка обычно требует O(''n'') итераций. Следовательно, общая временная сложность алгоритма составляет O(''n''<sup>3</sup>) или даже O(''n''<sup>4</sup>). Кроме того, основанные на физических аналогиях алгоритмы раскладки не обладают предсказуемостью, и это означает, что один и тот же алгоритм, обрабатывая один и тот же граф, может получать совсем не похожие результаты. Непредсказуемость данных алгоритмов может вызывать в некоторых случаях серьезные проблемы, поскольку навигация пользователя сильно зависит от визуального представления графов. | ||