Компоновка схемы: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 81: | Строка 81: | ||
которое оценивает сверху функцию HPWL с произвольно малой относительной ошибкой, так как <math>p \to \infty \;</math> и <math>\beta \to 0 \;</math> [7]. Кроме того, HPWL также можно аппроксимировать при помощи функции, задаваемой формулой | которое оценивает сверху функцию HPWL с произвольно малой относительной ошибкой, так как <math>p \to \infty \;</math> и <math>\beta \to 0 \;</math> [7]. Кроме того, HPWL также можно аппроксимировать при помощи функции, задаваемой формулой | ||
(3) <math>HPWL_{log-sum-exp}(G_h) = \alpha \sum_{e_k \in E_h} \bigg[ ln \bigg( \sum_{i \in C_k} exp \bigg( \frac{x_i}{ \alpha} \bigg) \bigg) + ln \bigg( \sum_{v_i \in C_k} exp \bigg( \frac{- x_i}{ \alpha} \bigg) \bigg) \bigg] \;</math> | (3) <math>HPWL_{log-sum-exp}(G_h) = \alpha \sum_{e_k \in E_h} \bigg[ ln \bigg( \sum_{i \in C_k} exp \bigg( \frac{x_i}{ \alpha} \bigg) \bigg) + ln \bigg( \sum_{v_i \in C_k} exp \bigg( \frac{- x_i}{ \alpha} \bigg) \bigg) \bigg] \;</math>. | ||
где <math>\alpha > 0 \;</math> – параметр сглаживания [6]. Обе аппроксимации можно оптимизировать с использованием | где <math>\alpha > 0 \;</math> – параметр сглаживания [6]. Обе аппроксимации можно оптимизировать с использованием метода сопряженных градиентов. | ||
| Строка 91: | Строка 91: | ||
Распространение под действием силы | '''Распространение под действием силы''' | ||
Базовая идея заключается в использовании постоянных по величине сил f, которые «отталкивают» вершины от перекрытий, и перевычислении сил на нескольких итерациях, отражая изменения в распределении вершин. Для квадратичной компоновки новые условия оптимальности выглядят следующим образом: | Базовая идея заключается в использовании постоянных по величине сил f, которые «отталкивают» вершины от перекрытий, и перевычислении сил на нескольких итерациях, отражая изменения в распределении вершин. Для квадратичной компоновки новые условия оптимальности выглядят следующим образом: <math>\mathbf{Q} \mathbf{x} + \mathbf{c} + \mathbf{f} = \mathbf{0} \;</math> [8]. Постоянная по величине сила может изменять компоновку различными способами, добиваясь удовлетворения целевых ограничений плотности. Сила '''f''' вычисляется при помощи дискретной версии уравнения Пуассона. | ||
Распространение с неподвижной точкой | '''Распространение с неподвижной точкой''' | ||
Неподвижная точка f представляет собой псевдовершину с нулевой площадью, зафиксированную в точке (xf,yf) и связанную с одной вершиной H(f) в гиперграфе при помощи псевдоребра весом иун(о-. Квадратичная компоновка с неподвижной точкой задается формулой Ф(х) = 5Z; wi;j(xi ~ xj)2 + дф | Неподвижная точка f представляет собой псевдовершину с нулевой площадью, зафиксированную в точке (xf,yf) и связанную с одной вершиной H(f) в гиперграфе при помощи псевдоребра весом иун(о-. Квадратичная компоновка с неподвижной точкой задается формулой Ф(х) = 5Z; wi;j(xi ~ xj)2 + дф | ||