Читайте также:
|
Матрицей взвешенных связей R будем задавать граф схемы, тогда соответствующие правила выбора элементов формулируют следующим образом:
,
,
,
где jk – номер столбца матрицы R, соответствующий индексу последнего размещенного элемента; Jk и 
– множества индексов размещенных и неразмещенных элементов, сопоставленных с их номерами из подмножеств 
и 
.
Показатель качества позиции при использовании матрицы D r:
,
где 
– индекс позиции j-го размещенного элемента.
Для размещения i-го элемента среди незанятых позиций выбирают ту, которая обеспечивает
.
Исходные данные для алгоритма, основанного на рассмотренных выше правилах выбора элемента и позиции его установки, – матрицы R и D r, вектор взвешенных связей элементов с внешними выводами H, множества индексов занятых и свободных позиций 
и 
.
Основные пункты алгоритма последовательного размещения по мультиграфу схемы:
1. По одному из решающих правил находим индекс ik+1 очередного размещаемого элемента:
.
2. Определяем позицию для установки этого элемента:
.
3. Заносим индекс элемента в массив Jk, индекс позиции – в массив Tk, исключая их из массивов
: 
4. Проверяем, все ли элементы размещены: 
. Если условие выполняется, то переходим к п. 1, иначе – к п. 5.
5. Конец работы алгоритма.
Дата добавления: 2015-07-25; просмотров: 62 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Последовательные алгоритмы размещения | | | Общая постановка задачи трассировки |