Устройство для оценки размещения элементов

(51) 4 С 06 Г 7/00, 15/ ОПИСАНИЕ ИЗОБРЕТЕН А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ 38отехническииоваП, Калычев льство СССР/00, 1,980,ство СССР7/00, 1984л, 4 табл и суммат АРСТВЕННЫЙ НОМИТЕТ СССРЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(54) УСТРОЙСТВО ДЛЯ ОЦНИИ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ(57) Изобретение относится к областицифровой вычислительной техники ипредназначено для моделирования комбинаторных задач при проектированииРЭА. Для расширения функциональныхвозможностей, а именно обеспечениявоэможности оценки текущего размещения по двум критериям: суммарнаядлина ребер и максимальная длина ребра, в устройство дополнительно введены блоки 2 подсчета единиц, блок 3нахождения максимума, блок 5 памятиИзобретение относится к цифровойвычислительной технике и может бытьиспользовано для моделирования комбинаторных задач при проектированииРЭА.Цель изобретения - расширение Функциональных возможностей устройствапутем обеспечения возможности оценкитекущего размещения при изоморфныхпреобразованиях по двум критериямсуммарной длины ребер и максимальнойдлины ребра и запоминания наилучтцегоразмещения элементов,На фиг. 1 изображена функциональ -ная схема предлагаемого устройства;на фиг. 2 - одна из возможных реализаций блока подсчета единиц; нафиг, 3 - одна из возможных реализаций блока нахождения максимума. 20устройство содержит матрицу 1 элементов однородной среды, состоящуюиз элементов однородной среды, блоки2 подсчета единиц, блок 3 нахождениямаксимума, сумматор 4, блок 5 памяти, вход б записи исходного гиперграфа, вход 7 управления перестановкойстолбцов, вход 8 управления перестановкой строк, вход 9 управления записью в блок памяти, выходы 10 и 11 30оценки текущего размещения, информационный выход 12 и вход 1 3 установки,Соединение элементов в матрицуэлементов однородной среды приведенов прототипе,3511 а Фиг, 2 изображен Фрагмент двумерной комбинационной итеративнойсети, которая выттолняет Функцию подсчета единиц, Каждый горизонтальныйряд элементов схемы представляет собой двоичный счетчик,. Координатев ремени, по кото рой ра зво рачиваетсяв послеговательных тактах работаэлемента схемы, соответствует вертикальная пространственная координата 45У, последовательности состоящей изкаждого зэтемента - последовательностьвертикальных межэлементньтх сигналовв соответствующем. столбце двумернойсети. 5011 ожно составить таблицу (табл,1),отобра:талэщую все происходящие в сетипреобразования,55На выходах произвольного т 1-гоэлемента схемы появляются сигналы,которые соответствуют э.-йт строкеи 1-лту разряду таблицы. 1 а фиг. 3 изображено устройство, ориентированное на операцию поиска максимума, представляющее из себя двумерную однородную структуру размером 11 хМ. Дття поиска максимума используется алгоритм поразрядного сравнения всех ттрчзнаков:1-й тцаг, Просматривается содержимое информационных входов элементов левого (1-го) столбца, т,е. старшие разряды всех 11 чисел. Если все эти разряды содержат 0 то на следующем тцаге просматриваются вторые разряды всех Ы чисел. Если же в первом столбце есть "1", то на втором шаге просматриваются только те числа, которые имели единицы в первом разряде,1-й шаг, Просматривается содер -жимое только в тех строках, которыебыли выделены на 1 1 шаге. Логикаработы та же, что и на 1-ом шаге,После подачи граничных сигналов Е о = - 1, и Хо = 6, по окончании переходных процессов сигналы Х= 1 направой границе матрицы устанавливаются в тех строках, на входы которых поступили максимальные числа, а на нижней границе - само это число.устройство предназначено для решения задач оценки размещения элементов. Схема представляется в виде матричного эквивалента графа или гиперграфа описывающего схему, При данной нумерации строк матрицы можно вычислить значение целевой функции оптимизации. Если поменять местами строки, то за счет изменения локальных свойств матрицы изменяется и значение целевой функции оптимизации. Таким образом, решение сводитсяк перестановке строк матрицы, т,е к ее изоморфному преобразованицо с оценкой текущего размецтения. Этациклическая перестановка заканчива -ется в момент получения оптимального значения целевой ф-.ткции иги по истечении лимита времени. Строки матрицы отмечаются элементами схемы, а стогбцы - цепями, соединяющими зти элементы, Таким образом, однородная среда содержащая Б х то элементов, физически отображает матрицу цепей, состоящую из л 1 элементов и тц соединятощих их цепей, Ка пересечении т-й строки и 1 - го стоттбца ставится единица, ;.сли ь-й элеме".т входит в 1-ю цепь, и ноль - в пботивцотт случае,1430949 50 Длиной 1-й пепи называется разностьмежду номерами самой нижней строки,в которой :тоит единица в 1-ом столбце, и номером самой верхней строки,в которой стоит единица в 1-ом столб 5це.Устройство работает следующим образом,На вход 6 записи поступают данныепо сигналу "1", На входе 13 происходит запись информации в элементыоднородной среды. На вход 9 поступает сигнал "Запись" и информация изтриггеров запоминания признака конечной точки переписывается в блок 5 памяти. Для нашего примера в однородную среду были записань 1 данные, приведенные в табл,2 в графе "Состояния элемента однородной среды", На 20индикаторных выходах элементов послеокончания переходных процессов устанавливаются единицы, если элементырасположены между двумя другими элементами в триггерах запоминания конечной точки, в которых содержатсяединицы или в триггерах запоминанияконечной точки самого элемента содержится единица, в противйом случаеустановится "0", Для нашего примера 30состояние индикаторных выходов отражено в соответствующих графах, табл,24. Информация с индикаторных выходовэлементов каждого столбца поступаетв блок подсчета единиц, соответствующий данному столбцу. Блок подсчетаединиц на выходе выдает двоичноечисло, равное количеству поступавших на его входы единиц. Для нашегопримера - это граФа Количество единиц" в соответствующих таблицах,Полученное число поступает навходы, соответствующие данному блокуподсчета единиц, сумматора и нахождения максимума. В сумматоре проис-45ходит суммирование всех двоичныхчисел поступивших на входы, а в блоке нахождения максимума отыскивается максимальное число из них. Полученные оценки поступают на выходы устройства, откуда - на устройство управления. Для нашего примера - это графы пСумма" и "Максимум", Устройство управления сравнивает полученные значения целевой функции с предыдущим наилучшим значением и в случае их улучшения выдает сигнал Запись".на вход управ 4лоция памятью, в противном случае,как и в течение всего цикла работыустройства, на этот вход сигнал"Запись" не поступает,В соответствии с. любым рациональным алгоритмом выбираются строки,которые необходимо переставить ивыдается сигнал на обмен строк. Внашем примере выбраны строки 1 и 3,Затем производится оценка (как былоописано выше) до тех пор, пока небудет найдено решение, удовлетворяющее некоторым критериям, либо покане будет исчерпано время, отведенноена решение задачи. формула изобретения Устройство для опенки размещения элементов, содержащее матрицу из истрок и ш столбцов элементов однород -ной среды, входы управления перестановки столбцов матрицы элементоводнородной среды соединены с входомуправления перестановкой столбцовустройства, входы управления перестановки строк матрицы элементов однородной среды соединены с входомуправления перестановкой строк устройства, входы установки матрицы однородных элементов соединены с входом начальной установки устройства,информационный вход матрицы элементов однородной среды соединен с входом записи исходного гиперграфа уст -ройства, о т л и ч а ю щ е е с ятем, что, с целью расширения Функциональных возможностей путем обеспечения возможности оценки текущего размещения при изоморфных преобразованиях по двум критериям - суммарнойдлины ребер и максимальной длиныребра и запоминания наилучшего размещения элементов, в него введеныш блоков подсчета единиц, блок нахождения максимума, сумматор, блокпамяти, управляющий вход которогосоединен с входом управления памятного устройства, - е индикаторные выходь; матрицы элементов однороднойсреды (з. = 1, гп) соединены с входом-го блока подсчета единиц, выходкоторого соединен с х-ым информационным входом блока нахождения максимума и входом -го слагаемого сумматора, выходы которых соединены с первым и вторым выходами оценки текущего размещения соответственно, 1-еинформационные выходы матрицы эле1430949 6Продолжение табл. 1 Разряд Строка 1 П 111 Т а б л и ц а 1 О О Разряд31 11 1114 Строка Сигнал Начальноесостоя 5 6 ние 1 О О Таблица 2 Номера цепей 1 3 4 5 6 7Номерэлемен 1 1 та Состояние индекса1 11 О О1 О О О О О О 1 1 1 О О О 1 1 1 О О 1 1 О1 1 11 1 1 1 О О О 1 1 1 О 1 О 1 О 1 О 1 О О 1 1 О О О 1 1 1 О 1 О 1 1 1 О О О О 1 1 О О Количествоединиц Сумма Максимум Сигнал на вход памяти при оценкепо сумме по максимуму 1 с 3 Обмен ментов однородной среды соединены с1-ми информационными входами блокапамяти ( - 1, и), выход которогосоединен с информационным выходомустройства. 1 1 1 1 1 1 О О430949 Таблица 3 Номераэлемента Номера целей2 3 4 5 1 Т67 Состояние индекса О 0 0 О 00 11 11 11 01 11 0 1 11 01 00 01 0 1 01 01 01 00 11 01 01 11 00 00 11 11 11 00 Количествоединиц 3 6 31 Сумма Максимум Сигнал на вход памятипри оценке 0 по сумме по максимуму4 с 3 Обмен Т а б л и ц а 41430949 Продолжение табл,4 23 Сигнал на по сумме по максимуму 6 с 5 Обмен и так далее Номерэлемента Количе с твоединиц СуммаМаксимум вход памятипри оценке 1 2 3 .4 5 Состояние индекса 6 7Составитель А Техред Л.Серд Богословскихова Карре Обруч Редак Ревин исно аказ 53 твенно-полиграфическое предприятие, г, Ужгород, ул. Лроектная оиз Тираж 70 ч ВНИИПИ Государственно по делам изобретен 13035, Москва, Ж, Ракомитета ССи открытий ская наб., д