Пристрій для комбінаторної оптимізації

Корисна модель належить до пристроїв цифрової обчислювальної техніки. Застосування пристрою дозволить скоротити час розв'язання комбінаторних задач оптимізації за рахунок виділення з усієї множини перестановок тільки допустимих перестановок та здійснення їх аналізу. Відомий пристрій для перебору перестановок, якій містить елементи І, елементи АБО, елементи затримки та лічильники. Цей пристрій дозволяє здійснити генерацію n! перестановок з n елементів. [Авт. св. СССР: №748416. Устройство для перебора перестановок / Борисов С.Н. и др. Опубл. 15.07.80. Бюл. №26]. Недоліком цього пристрою є те, що він не дозволяє виділити з усієї множини перестановок тільки ті перестановки, які задовольняють наперед заданим обмеженням. Найбільш близьким до пропонованого за сукупністю ознак є пристрій для генерування перестановок, який складається з генератора тактових імпульсів, вихід якого підключено до входу синхронізації регістру зсуву та через елемент затримки до входу синхронізації інформаційного регістру, з гр упи виходів якого одержуємо множину перестановок, а групу входів інформаційного регістру з'єднано з групою виходів постійної пам'яті, групу входів якої підключено до групи виходів регістру зсуву [Курейчик В.М. и др. Комбинаторные аппаратные модели и алгоритмы в САПР. - Москва: Радио и связь. 1990.-120с.]. Недоліком цього пристрою є те, що неможливо здійснити селекцію елементів комбінаторної множини перестановок за заданими обмеженнями. В основу корисної моделі поставлена задача створення пристрою з розширеними функціональними можливостями, шляхом введення додаткових блоків та їх з'єднань. Позитивним технічним результатом є те, що наявність блоків завдання обмежень на перестановки та блоків, що забезпечують селекцію перестановок дозволяє одержати підмножину множини перестановок, елементи якої задовольняють заданим обмеженням. Такого технічного результату можна досягти, якщо у пристрої для генерування перестановок, який містить генератор тактових імпульсів, вихід якого підключено до входу синхронізації регістру зсуву та через елемент затримки до входу синхронізації інформаційного регістру, з групи виходів якого одержуємо множину перестановок, а групу входів інформаційного регістру з'єднано з групою виходів постійної пам'яті, групу входів якої підключено до групи виходів регістру зсуву, згідно з корисною моделлю, в нього введені лічильник, блок пам'яті, блок співпадіння, блок розрахунку функції мети, блок виділення екстремального значення, блок реєстрації та блок введення інформації, група входів якого є інформаційними входами пристрою, а група його виходів підключена до групи входів блоку пам'яті, вхід якого з'єднано з виходом лічильника, вхід якого підключено до виходу генератора тактових імпульсів, а групу ви ходів блоку пам'яті підключено до першої групи входів блоку співпадіння, друга група входів якого з'єднана з групою виходів інформаційного регістру, гр упа виходів якого підключена до першої групи входів блоку розрахунку функції мети, другий вхід якого з'єднано з виходом блоку співпадіння, вихід блоку розрахунку функції мети підключено до входу блоку виділення екстремального значення, вихід якого підключено до блоку реєстрації. При пошуку в патентній та науково-технічній літературі не виявлено об'єктів з ознаками, подібними до відмінних ознак технічного рішення, що заявляється, на підставі чого можна зробити висновок про відповідність його критерію "суттєві відмінності". На Фіг. представлено схемну реалізацію пристрою. Пристрій складається з: генератора 1 тактових імпульсів; елемента 2 затримки; інформаційного регістра 3; постійної пам'яті 4; регістра 5 зсуву; лічильника 6; блока 7 пам'яті; блока 8 співпадіння; блока 9 розрахунку функції мети; блока 10 виділення екстремального значення; блока 11 реєстрації; блока 12 введення інформації. Пристрій працює наступним чином. Початкова інформація про обмеження на елементи комбінаторної множини перестановок вводиться блоком 12 вводу інформації до блоку 7 пам'яті. Генератор 1 імпульсів забезпечує подачу тактових імпульсів до регістру 5 зсуву, через елемент 2 затримки на інформаційний регістр 3, через лічильник 6 на блок 7 постійної пам'яті. При цьому, лічильник 6 забезпечує подачу з блоку 7 пам'яті до блоку 8 співпадіння усіх перестановок, заборонених заданими обмеженнями. Регістр 5 зсуву, блок 4 постійної пам'яті та інформаційний регістр 3, згідно з прототипом, забезпечують подачу n! перестановок до блоку 8 співпадіння. Таким чином, до блоку 8 співпадіння надходять послідовно по одній перестановці з інформаційного регістру 3, кожна така перестановка порівнюється послідовно з усіма забороненими перестановками, що надходять з блоку 7 пам'яті. Якщо подані до блоку 8 перестановки однакові, блок 8 співпадіння подає імпульс до блоку 9 розрахунку функції мети, який відключає подальший обчислювальний процес. Якщо перестановка, яка надійшла до блоку 8 не співпадає ні з однією забороненою перестановкою, що надходять з блоку 7 пам'яті, то блок 9 розраховує та запам'ятовує значення функції мети для цієї перестановки. Одержані у блоці 9 значення функції мети подаються до блоку 10 виділення екстремального значення, потім найкраще значення функції мети та відповідна перестановка фіксується блоком 11 реєстрації.