2018-02-14
332
Метод максимальной конъюнкции – минимальной дизъюнкции:
1) Определяется блок, имеющий max кол-во связей с элементами. Если имеется несколько элементов с одинаковым количеством связей, то выбирается элемент с наименьшим номером.
2) Из нераспределённых эл-тов выделяется такое подмн-во, что не нарушается ограничение на количество внешних контактов блока (остальные из этого множества исключаются).
3) Среди выделенного подмн-ва выбирается тот эл-т, который имеет наибольшее число связей с уже размещёнными. Если таких несколько® выбирается тот, включение которого приводит к меньшему числу внешних контактов.При равенстве выбирается эл-т с наименьшим номером.
Ограничения: задано количество элементов в блоке, задано количество выводов блока.
Пример: элементов в куске ≤ 3, количество контактов ≤ 5. r - индекс куска
| r | Ir0 | L1 | ir* | Ir1 | L2 | L3 | Tr1 | Ir2 | L2 | L3 | Tr2 |
| 1 | e1 | 3 | e1 | e2 | 4 | 2 | e1 | e3 | 7 | - | e1 |
| e2 | 3 | e3 | 6 | - | e2 | e4 | 5 | 2 | e2 | ||
| e3 | 3 | e4 | 4 | 2 | e5 | 5 | 1 | e4 | |||
| e4 | 3 | e5 | 6 | - | e6 | 6 | - | ||||
| e5 | 3 | e6 | 5 | 1 | e7 | 6 | - | ||||
| e6 | 2 | e7 | 5 | 1 | e8 | 7 | - | ||||
| e7 | 2 | e8 | 6 | - | e9 | 7 | - | ||||
| e8 | 3 | e9 | 6 | - | |||||||
| e9 | 2 | ||||||||||
| 2 | e3 | 3 | e3 | e5 | 5 | 1 | e3 | e5 | 5 | 1 | e3 |
| e5 | 1 | e6 | 6 | - | e9 | e6 | 6 | - | e9 | ||
| e6 | 2 | e7 | 6 | - | e7 | 6 | - | e8 | |||
| e7 | 2 | e8 | 4 | 2 | e8 | 3 | 2 | ||||
| e8 | 3 | e9 | 3 | 2 | |||||||
| e9 | 2 | ||||||||||
| 3 | e5 | 0 | e6 | e5 | 6 | - | e6 | e5 | 7 | - | e6 |
| e6 | 2 | e7 | 4 | 2 | e7 | e7 | |||||
| e7 | 2 | ||||||||||
| 4 | e5 |
1) Определение первого элемента, назначаемого в первый кусок.
Выбираем элемент с наибольшим количеством связей с остальными.
L1(e1) = e1∧(e2∨e3∨...∨e9) (т.е. не включая e0)
Выбираем max {L1(ei)} и записываем ei как ir*
2) Среди оставшихся элементов (Ir1) выявляются те, помещение которых в текущий кусок не нарушит ограничения.
Если мы к куску {e1} хотим добавить e2
L2(e1, e2) = (e1∨e2)∧(e0∨e3∨...∨e9).
|
|
|
Если мы к куску {e1, e2} хотим добавить e4
L3(e1, e2, e4) = (e1∨e2∨e4)∧(e0∨e3∨e5∨...∨e9)
L2 - сколько внешней связей будет иметь кусок, если туда поместить ei. На этом этапе надо исключить элементы, из-за которых происходит превышение кол-ва контактов.
3) Выбираем из оставшихся элементов те, которые имеют наибольшее количество связей с уже размещенными в куске.
Если мы к куску {e1} хотим добавить e2 ® L3(e1, e2) = e1∧e2 Если мы к куску {e1, e2} хотим добавить e4 ® L3(e1, e2, e4) = (e1∨e2)∧e4
4) Элемент выбирается сначала по max L3, а затем, в случае равенства, по min L2.
В последующих кусках при расчете L1 уже размещенные в предыдущих кусках элементы не учитываются, а при расчете L2 - очень даже учитываются.
|
|
|
