4551
правка
Компоновка схемы: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
'''Линеаризованная квадратичная компоновка''' | '''Линеаризованная квадратичная компоновка''' | ||
Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (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), вычисляя <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-точечных гиперребер можно применять / | Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять <math>\beta \;</math>-регуляризацию [1]. Для m-точечного гиперребра (при <math>m \ge 3 \;</math>) можно переформулировать HPWL в виде максимума (по норме <math>l_{\infty} \;</math>) среди всех m(m — 1)/2 попарных расстояний <math>|x_i - x_j| \;</math> и аппроксимировать <math>l_{\infty} \;</math>-норму <math>l_p \;</math>-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме '''0''', что впоследствии убирается при помощи <math>\beta \;</math>-регуляризации. Полученная аппроксимация HPWL задается формулой | ||
(2) <math>HPWL_{p - \beta - reg} (G_h) = \sum_{e_k \in E_h} \bigg( \sum_{i,j \in C_k} |x_i - x_j|^p + \beta \bigg)^{1/p} \;</math>. | |||
Каждая неподвижная точка f вводит квадратичный член WF;H(F) (xH(f) —xf)2-. Манипулируя положениями неподвижных точек, можно добиться того, что компоновка будет удовлетворять целевым ограничениям плотности. По сравнению с постоянно действующими силами неподвижные точки повышают контролируемость и стабильность итераций алгоритма компоновки [ ]. | |||
