окривають відокремлені клітини.
. Видалити з розгляду покриті клітини. Викинути з розгляду куби, які покривали щось з обраних клітин, якщо клітини, що покриваються, що відскакують кубами, мають інше покриття у вигляді іншого куба рівною або більшою розмірності в порівнянні з відкидати кубом.
. Продовжити процес пошуку.
Таким чином, слідуючи даним принципом мінімізації відкинутими з розгляду кубами будуть: 00Х0Х, 00ХХ0. 111ХХ.
Кубами ввійшли в мінімальне покриття стануть:
X1X1, 001XX, X11X0, 0101X, 0000X, 0X010
Остаточне мінімальне покриття буде виглядати наступним чином:
Функціональна схема після мінімізації
Розрахуємо вартість:
Розрахуємо економію:
Вартість схеми до мінімізації (C (F))=34
Вартість після мінімізації (C (F)) min=25
Малюнок 5 - Функціональна схема після мінімізації функції
Виграш у вартості становить
ДW=34-25=9
. Факторизація покриттів
В основі першого алгоритму факторизації (м-алгоритм) лежить м-твір, яке позначається a м b, складається з результатів покоординатно творів
і виконується відповідно до таблиці 1:
Таблиця 1.
Таким чином, м-добуток двох координат дорівнює нулю, якщо обидві координати дорівнюють нулю, дорівнює одиниці, якщо обидві координати дорівнюють одиниці і дорівнює м у всіх інших випадках.
1. Беремо отримане минимизированное покриття C 0 (F):
2. Визначають м-твори всіх кубів зі C 0 (F). Це зручніше проробити з допомогою наступної таблиці (Табл. 2). По вертикалі в першій зліва колонці розміщені куби покриття C 0 (F), по горизонталі в першій зверху сходинці розміщені ті ж куби, без останнього. На місці перетину кубів самих із собою ставлять прочерки.
Оскільки таблиця виходить симетричною, то м-твори відповідних кубів заповнюють тільки в нижній частині таблиці.
Таблиця 2 - м-твори всіх кубів зі C 0 (F)
1X1X1001XXX11X00101X0000X1X1X1 ---- - 001XX? ?1 ? ? ---- X11X0? ?1 ? ?? ?1 ? ?-- - 0101X? ? ? ? ?0 ? ? ? ??1 ? ? ?- - 0000X? ? ? ? ?00 ? ? ?? ? ? ? ?0 ?0 ? ? - 0X010? ? ? ? ?0 ? ? ? ?? ? ? ?00 ?01 ?0 ?0 ? ?
. Вибираємо маскує куб C м, що має максимальну вартість. Вартість куба визначається за формулою:
,
де Rм - загальне число координат куба, які не рівних м.
Кубом, які мають максимальну вартість, буде куб
.
. У таблиці відзначаємо куби, отмаскірованние обраним маскуючим кубом. Ними будуть куби 0X010, 0101X.
. Покриття C 0 (F) розбиваємо на три частини. Вгорі розташовують куби, куби, що не покриваються маскуючим кубом. Потім записується маскує куб. Під ним поміщаються отмаскірованние куби з прочерками на тих координатах, які не рівні м в маскирующем кубі.
6. Отмаскірованние куби виключаємо з розгляду. Після виключення отмаскірованних кубів алгоритм повторюється.
. Знову будується таблиця (таблиця 3)
Таблиця 3 - м-твори всіх кубів зі C 1 (F)
1X1X1001XXX11X00000X1X1X1 --- - 001XX? ?1 ? ? --- X11X0? ?1 ? ?? ?1 ? ?- - 0000X? ? ? ? ?00 ? ? ?? ? ? ? ? - 0 ?01 ?? ? ? ? ?0 ? ? ? ?? ? ? ? ?0 ?0 ? ?
8. Вибирається маскує куб максимальною вартістю.
Виберемо один з кубів, їм буде куб
. Відзначаються куби, отмаскірованние cм3. В даному випадку такими будуть 0000Х, 0 ?01 ?.
. Покриття C2 (F) розбивається знову на три частини.
.
. Знову будуємо таблицю
Таблиця 4 - м-твори всіх кубів зі C 2 (F)
1X1X1001XXX11X01X1X1-- - 001XX? ?1 ? ? - X11X0? ?1 ? ?? ?1 ? ? - 0 ?0 ? ?? ? ? ? ?0 ? ? ? ?? ? ? ? ?
Вибираємо маскують куби з максимальною вартістю.
Відзначаємо куби, отмаскірованние Cм5. В даному випадку такими будуть 001ХХ, Х11Х0, 1х1х1. І будуємо покриття.
. Так залишилися ще неотмаскірованние куби, знову будуємо таблицю.
Таблиця 5 - м-твори всіх кубів зі C 3 (F)
0 ?0 ? ?0 ?0 ? ?-? ? 1 ? ?? ? ? ? ?
. Алгоритм закінчується, коли не залишиться неотмаскірованних кубів, або маскує куб максимальної вартості буде складатися тільки з одних м (нульова вартість).
Таким чином, остаточне факторізовано покриття буде ви...
