4446
правок
Компоновка схемы: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
Целевая функция | '''Целевая функция''' | ||
Пусть <math>C_k \;</math> – набор индексов вершин гиперграфа, инцидентных гиперребру <math>e_k \;</math>. ''Полная длина проводов полупериметра'' (half-perimeter wirelength, HPWL) схемы гиперграфа задается формулой <math>HPWL(G_h) = \sum_{e_k \in E_h} HPWL(e_k) = \sum_{e_k \in E_h} [max_{i, j \in C_k} |x_i - x_j| + max_{i, j \in C_k} |y_i - y_j|] \;</math>. Функция HPWL является кусочно-линейной, сепарабельной по измерениям x и y, выпуклой, но не строго выпуклой. Среди многих целевых функций, используемых для компоновки схемы, эта является самой простой и распространенной. | |||
Ограничения | |||
'''Ограничения''' | |||
1. Перекрытия не допускаются. Площади, занятые любыми двумя вершинами, не могут перекрываться; т.е. должно иметь место либо JXI — Xj\ 1 2(wi + wj), либо \Уг~У)\> i(fei+fy),VVi,V,-€ Vh. | 1. Перекрытия не допускаются. Площади, занятые любыми двумя вершинами, не могут перекрываться; т.е. должно иметь место либо JXI — Xj\ 1 2(wi + wj), либо \Уг~У)\> i(fei+fy),VVi,V,-€ Vh. | ||