Последовательный алгоритм размещения

Основные правила:

– Наиболее связанные элементы следует располагать максимально близко друг к другу

– На каждом шаге алгоритма (в соответствии с некоторой оценкой) выбирают очередной элемент и очередную позицию для его установки

– Выбор очередной позиции для очередного элемента осуществляется на основе цены назначения i-ого элемента в j-ую позицию, отражающую суммарную длину его связей с уже размещёнными элементами, в том числе и с разъёмом.

Гиперграф зададим аналитически:

– Множеством вершин

– Множеством рёбер

– Множеством отображений X à U: Г X и U à X: Г U

На каждом k-ом шаге алгоритма будем иметь множество

- размещённые элементы

- неразмещённые элементы

Правила возможности выбора следующего элемента:

1. - по максимальной связанности с предыдущим размещённым элементом.

- вершина предыдущего размещённого элемента

1. - по максимальной суммарной связанности со всеми размещёнными элементами
2. - по максимальной разности связей с размещёнными и неразмещёнными элементами

Оценка для выбора позиций, суммарная длина цепей, связывающих элемент со всеми уже размещёнными элементами по ортогональной метке.

Дата добавления: 2014-01-20