<<
>>

10.2. Расчет нижних оценок

После окончательного разбиения цепей на фрагменты осу­ществляется расчет нижней оценки ξ на основе совместного учета горизонтальных и вертикальных ограничений. Затем для каждого участка fiопределяются возможные магистрали его расположения. Пронумеруем магистрали в канале сверху вниз. Определим по графу вертикальных ограничений Gy для каждо­го фрагмента fiминимальный номер δ( магистрали, в которой может быть помещен fi.

Приведем Алгоритм Alрасчета граничной оценки δ) с уче­том только вертикальных конфликтов.

Алгоритм Al

1. Всем вершинам в графе вертикальных ограничений Gy, у которых нет входящих ребер, присваивается оценка δt = 1. Вершины, для которых определены оценки, помечаются.

2. Среди непомеченных вершин выбирается вершина xi, у которой все входящие в нее ребра исходят только из помеченных вершин (подмножество Xi). Если таких вершин нет, то конец работы алгоритма.

3. Среди оценок подмножества вершин Xiвыбирается мак­симальная δj. Вершине xiприсваивается оценка,

а сама вершина помечается. Переход к п. 2.

Фактически δi— это ближайшая от верхней линейки контак­тов магистраль, в которой может быть в соответствии с графом вертикальных ограничений помещен участок fi.

Пронумеруем теперь магистрали снизу вверх и снова по гра­фу вертикальных ограничений для каждого fiопределим ми­нимальный номер δb— номер ближайшей от нижней линейки контактов магистрали, в которую может быть помещен fi. Если число пронумерованных сверху вниз магистралей Lзадано, при­чем δi+ δb — 1 ≤ L, то fiможет быть размещен в магистралях с номерами от (δi) до (L — δb+ 1). Если существует xi, для которого δt + δb— 1 > L, то трассировка не реализуема в L магистралях.

Теперь пересчитаем значение оценок δiи δ∣с учетом горизон­тальных конфликтов. Пусть в графе вертикальных ограничений две вершины xiи xj∙ являются непосредственными предками вершины Xk (рис. 10.4).

Рис. 10.4. Ситуация, при которой вершины xiи Xjявляются непосредственны­ми предками вершины xk

Это означает, что fkдолжен быть размещен ниже fiи fj∙. Пусть для fiи fj∙ по алгоритму Alопределены оценки, причем δt = δj. В соответствии с Al оценка для xkопределена как δtt = δi+ 1. Однако, если окажется, что fiи fj∙ конфликтуют в со­ответствии с графом горизонтальных ограничений (рис. 10.4), то fiи fj∙ не могут быть размещены в одной магистрали и, следовательно, δtk= δti + 2.

В связи с этим необходимо пересчитать оценки δt и δbдля всех fi. Обозначим через pijдлину максимального пути в графе

вертикальных ограничений между вершинами Xiи Xj. Рассмот­рим методику расчета граничных оценок δiи δ∣с учетом как вертикальных, так и горизонтальных ограничений, задаваемых графами вертикальных и горизонтальных ограничений.

Опреде­лим в графе вертикальных ограничений множество Xi= Γ(xi), состоящее из всех вершин, являющихся предками вершины Xi. Для этих вершин Xiявляется корневой (рис. 10.5, а).

Рис. 10.5. а — множество Xi= Γ(xi), состоящее из всех вершин ГВО, яв­ляющихся предками вершины xi; б — выделение в множестве Xiмножества Ri(a, b) ⊂Xi

Множество Xiсоответствует множеству фрагментов Fi. Вы­делим в множестве Xiмножество Ri(a, b) ⊂ Xi, отличающееся следующими двумя свойствами (рис. 10.5, б):

— для любой вершины Xj ∈Ri(a, b) величина δj > a, т. е. (Vj | Xj ∈Ri(a, b))[δj >а]. Множеству Ri(a, b) соответствует множество участков Fi(a,b). Это значит, что ни один из fj ∈Fi(a, b) не может быть помещен в магистраль с номером, меньшим или равным а;

— для любой вершины Xj ∈Ri(a, b) длина максимального пу­тиPijот Xiдо Xj не меньше величины b, т. Є. (Vj | Xj ∈∈Ri(a,b))[pij > b]. Это значит, что номер магистрали, в ко­торую может быть помещен fj ∈Ri(a, b), не менее чем на b меньше номера магистрали, в которую может быть поме­щен fi. При этом a + b < δ∣.

Определим минимальное число магистралей di(a, b), необхо­димое для размещения участков множества Fi(a, b) без учета вертикальных ограничений между ними. При этом учитываются только горизонтальные конфликты. Значение di(a, b) рассчиты­вается как плотность, создаваемая Fi(a,b). Исходя из этого, минимальный номер магистрали, в которую можно поместить fi, определяется как δi= a + di(a, b) + b.

Задавая различные сочетания целочисленных значений а и bс учетом того, что a + b < δt, определим набор значений δt(a,b). Число их пропорционально (δt)2. Среди всех оценок набора δt(a, b) выбирается оценка с максимальным значением. Эта оценка и будет новым пересчитанным значением δitдля xi с учетом как вертикальных, так и горизонтальных конфликтов, задаваемых ГВО и ГГО.

Аналогичным образом пересчитываются оценки δb. Выбор вершин для пересчета оценок δ∣и δbосуществляется после­довательно в порядке возрастания значений δ∣и δb, начиная с вершин, для которых δt или δbимеют минимальное значение. При таком подходе соблюдается правило, в соответствии с кото­рым до начала пересчета оценки вершины xiдолжны быть уже пересчитаны оценки всех вершин, являющихся предками xi.

Следующий шаг в минимизации комбинаторной сложности связан с учетом ограничений на ширину канала. Для этого необходимо рассчитать оценку минимальной ширины канала.

Рассмотрим методику расчета нижней оценки ширины кана­ла [52].

Проанализируем множество оценок δtiи δbi. Определим среди них две оценки с максимальными значениями. Обозначим их Dt и Db.Тогда имеем (Vi) [Dt~≥ δti, Db~≥ δb]. Затем выберем оценку с наибольшим значением — D.

Зададим два целочисленных параметра a и b, так что a+b≤D.

Пусть F (a, b) — множество таких

участков, что F (a, b) C Fи (Vifi∈∈F (a, b)) [(δit> a)fe(δib>b)](рис. 10.6).

Определим без учета вертикальных конфликтов минимальное число магистра­лей d(a, b), необходимое для размещения участков F (a, b). Тогда минимальное число магистралей для размещения F определит­ся как ξ(a, b) = a + b + d(a, b).

Подмножество F (a, b) полностью опре­деляется значениями параметров a и b, и, в частных случаях, может оказаться, что F (a, b) = 0или F (a, b) = F.

Варьируя значениями параметров a и b так, чтобы a + b ≤ D, подсчитываем все оценки ξ(a, b). Число оценок пропорциональ­но D2. Оценка ξmс максимальным значением будет нижней оценкой числа магистралей, необходимых для размещения всех участков множества F.

Отметим, что при расчете нижней оценки ξmиспользуются уточненные значения оценок δt и δb. После расчета оценок δtiи δb и нижней оценки ширины канала ξmсформируем для каждого участка fiнабор разрешенных магистралей (HPM), в которых он может быть размещен: Mi= {mj∙}. Здесь ширина канала считается равной ξm.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме 10.2. Расчет нижних оценок:

  1. 3.1 Применение коноскопии для численных оценок искажений оптической индикатрисы, связанных с дефектами структуры
  2. 60. Безналичные расчёты по инкассо.
  3. Результаты расчетов и экспериментов
  4. Результаты расчетов и экспериментов
  5. 57. Платежное поручение как форма безналичных расчетов.
  6. 59. Безналичные расчеты чеками.
  7. 58. Аккредитив как форма безналичных расчетов.
  8. РАСЧЕТ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  9. РАСЧЕТ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ С ОДНОСТОРОННИМИ ОПОРНЫМИ СВЯЗЯМИ
  10. Расчет железобетонных конструкций методом конечных элементов
  11. Расчет пластинок в виде частей круга методом масштабирования
  12. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ПО РАСЧЕТУ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ