4551
правка
Компоновка схемы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
Также могут добавляться такие ограничения, как выравнивание, минимальное и максимальное расстояние и другие. Многие техники компоновки временно ослабляют ограничение на перекрытие, заменяя его ограничением плотности во избежание скопления вершин в областях малого размера. Регулярная структура B размера <math>m \times n \;</math> контейнеров накладывается на неподвижный контур, площади вершин присваиваются контейнерам, расположенным в позициях вершин. Обозначим за | Также могут добавляться такие ограничения, как выравнивание, минимальное и максимальное расстояние и другие. Многие техники компоновки временно ослабляют ограничение на перекрытие, заменяя его ограничением плотности во избежание скопления вершин в областях малого размера. Регулярная структура B размера <math>m \times n \;</math> контейнеров накладывается на неподвижный контур, площади вершин присваиваются контейнерам, расположенным в позициях вершин. Обозначим за <math>D_{ij} \;</math> плотность контейнера <math>B_{ij} \in B \;</math>, определяемую как общая плотность клеток, присвоенных контейнеру <math>B_{ij} \;</math>, деленная на его емкость. Перекрытие вершин неявно ограничивается условием <math>D_{ij} \le K, \forall B_{ij} \in B \;</math>, для некоторого <math>K \le 1 \;</math> (целевой показатель плотности). | ||
Задача 1 (компоновка схемы) | '''Задача 1 (компоновка схемы)''' | ||
Дано: гиперграф схемы | Дано: гиперграф схемы <math>G_h(V_h, E_h) \;</math> и неподвижный контур области размещения. | ||
Требуется: найти положение каждой вершины | Требуется: найти положение каждой вершины <math>v_i \in V_h \;</math>, такое, что: | ||
(1) длина проводов минимальна; | |||
(2) ограничения на плотность <math>D_{ij} \le K \;</math> удовлетворяются для всех <math>B_{ij} \in B \;</math>. | |||
== Основные результаты == | == Основные результаты == | ||