4551
правка
Компоновка схемы: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 65: | Строка 65: | ||
Глобальный минимум <math>\Phi (x) \;</math> можно найти, решив разреженную систему линейных уравнений с симметричной положительно определенной матрицей <math>\mathbf{Q} \mathbf{x} + \mathbf{c} = 0 \;</math> (предполагая, что имеется более одной фиксированной вершины), которая поддается эффективному решению с достаточной точностью при помощи любого числа итеративных алгоритмов решения. Квадратичная компоновка может иметь различные оптимумы в зависимости от модели (клика либо звезда), используемой для представления гиперребер. Однако для k-точечного гиперребра имеет место следующий факт: если вес 2-точечных ребер задается равным <math>W_c \;</math> в модели с кликой и <math>kW_c \;</math> в модели со звездой, то для случая квадратичной компоновки эти модели эквивалентны [7]. | Глобальный минимум <math>\Phi (x) \;</math> можно найти, решив разреженную систему линейных уравнений с симметричной положительно определенной матрицей <math>\mathbf{Q} \mathbf{x} + \mathbf{c} = \mathbf{0} \;</math> (предполагая, что имеется более одной фиксированной вершины), которая поддается эффективному решению с достаточной точностью при помощи любого числа итеративных алгоритмов решения. Квадратичная компоновка может иметь различные оптимумы в зависимости от модели (клика либо звезда), используемой для представления гиперребер. Однако для k-точечного гиперребра имеет место следующий факт: если вес 2-точечных ребер задается равным <math>W_c \;</math> в модели с кликой и <math>kW_c \;</math> в модели со звездой, то для случая квадратичной компоновки эти модели эквивалентны [7]. | ||
'''Линеаризованная квадратичная компоновка''' | '''Линеаризованная квадратичная компоновка''' | ||
Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя | Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя <math>w_{ij} = \frac{1}{|x_i - x_j|} \;</math> на каждой итерации. Другим вариантом может быть решение единичной <math>\beta \;</math>-регуляризованной задачи оптимизации, заданной формулой <math>\Phi(\mathbf{x}) = min_x \sum_{i,j} w_{ij} \sqrt{(x_i - x_j)^2 + \beta} , \beta > 0 \;</math> – например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1]. | ||
Компоновка с учетом полной длины проводов полупериметра (HPWL) | '''Компоновка с учетом полной длины проводов полупериметра (HPWL)''' | ||
Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять /S-регуляризацию [1]. Для m-точечного гиперребра (при m > 3) можно переформулировать HPWL в виде максимума (по норме L1) среди всех m(m — 1)/2 попарных расстояний jxi — xjj и аппроксимировать L1-норму Lp-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме 0, что впоследствии убирается при помощи /S-регуляризации. Полученная аппроксимация HPWL задается формулой Pfwf;H(f)(xH(f) — xf)2. Каждая неподвижная точка f вводит квадратичный член WF;H(F) (xH(f) —xf)2-. Манипулируя положениями неподвижных точек, можно добиться того, что компоновка будет удовлетворять целевым ограничениям плотности. По сравнению с постоянно действующими силами неподвижные точки повышают контролируемость и стабильность итераций алгоритма компоновки [ ]. | Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять /S-регуляризацию [1]. Для m-точечного гиперребра (при m > 3) можно переформулировать HPWL в виде максимума (по норме L1) среди всех m(m — 1)/2 попарных расстояний jxi — xjj и аппроксимировать L1-норму Lp-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме 0, что впоследствии убирается при помощи /S-регуляризации. Полученная аппроксимация HPWL задается формулой Pfwf;H(f)(xH(f) — xf)2. Каждая неподвижная точка f вводит квадратичный член WF;H(F) (xH(f) —xf)2-. Манипулируя положениями неподвижных точек, можно добиться того, что компоновка будет удовлетворять целевым ограничениям плотности. По сравнению с постоянно действующими силами неподвижные точки повышают контролируемость и стабильность итераций алгоритма компоновки [ ]. | ||
