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

 

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании РЭА. Для расширения функциональных возможностей, а именно обеспечения возможности оценки текущего размещения по двум критериям: суммарная длина ребер и максимальная длина ребра , в устройство дополнительно введены блоки 2 подсчета единиц, блок 3 нахождения максимума, блок 5 памяти и сумматор 4. 3 ил, 4 табл„

СОВХОЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51) 4 G 06 F 7/00, 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К А ВТ0РСНОМУ СВИДЕТЕЛЬСТВУ (21) 4215277!24-24 (22) 25е03т 87 (46) 15.1 0.88. Бюл. У 38 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) Л,С, Бернштейн, Д.П. Калычев и К.К. Дедюлин (53) 688.3 (088.8) (56) Авторское свидетельство СССР

У 978139, кл. G 06 F 7/00, 1980.

Авторское свидетельство СССР

N - 1291957, кл. G 06 F 7/00, 1984 °

„„SU„„1430949 А 1 (54) УСТРОЙСТВО ДЛЯ ОЦНИИ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ (57) Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании

РЭА. Для расширения функциональных возможностей, а именно обеспечения воэможности оценки текущего размещения по двум критериям: суммарная длина ребер и максимальная длина ребра, в устройство дополнительно введены блоки 2 подсчета единиц, блок 3 нахождения максимума, блок 5 памяти и сумматор 4. 3 ил. 4 табл.

14 30949

Изобретение относится к цифровой вычислительной технике и может быть использовано для моделирования комбинаторных задач при проектировании

РЭА.

Цель изобретения — расширение функционалъных возможностей устройства путем обеспечения возможтгости оценки текущего размещения при изоморфных преобразованиях по двум критериям суммарной длины ребер и максимальной длины ребра и запоминания наилучшего размещения элементов, На фиг. 1 изображена функциональ— ная схема предлагаемого устройства; на фиг. 2 — одна из возможных реали— заций блока подсчета единиц; на фиг, 3 — одна из возможных реализаций блока нахождения максимума. 20 устройство содержит матрицу 1 элементов однородной среды, состоящую из элементов однородной среды, блоки

2 подсчета единиц, блок 3 нахождения максимума, сумматор 4, блок 5 памя- 25 ти, вход 6 записи исходного гиперграфа, вход 7 управления перестановкой столбцов, вход 8 управления перестановкой строк, вход 9 управления записью в блок памяти, выходы 10 и 11 30 оценки текущего размещения, информационный выход 12 и вход 13 установки.

Соединение элементов в матрицу элементов однородной среды приведено в прототипе, 35

На фиг, 2 изображен фрагмент двумерной комбинационной итеративной сети, которая выттолняет функцию подсчета единиц, Каждый Toðèçîíòàëúíûé ряд элементов схемы представляет со- 40 бой двоичный счетчик,. Координате в ремени, по кото рой ра зво рачивается в по следов ательных тактах работа элемента схемы,.соответствует вертикальная пространственная координата

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

11ожно составить таблицу (табл,1), отобра:тающую все происходящие в сети преобразования, 55

На выходах произвольного i j -ro элемента схемы появляются сигналы, которые соответствуют i-й строке и 1-:лу разряду таблицы.

1! а фиг. 3 изображено устройст -:о, ориентированное на операцию поиска максимума, представляющее из себя двумерную однородную структуру размером NxM. Дття поиска максимума ис— пользуется алгоритм поразрядного сравнения всех ттрчзнаков:

i é тцаг, Просматривается содержимое информационных входов элементов левого (1-го) столбца, т.е. старшие разряды всех N чисел. Если все эти разряды содержат "0",, то «а следующем шаге просматриваются вторые разряды всех N чисел. Если же в первом столбце есть "1", то на втором шаге просматриваются только те числа, которые имели единицы в первом разряде, 1-й пгаг, Просматривается содер— жимое только в тех строках, которые были выделены на 1 1 шаге. Логика работы та же, что и на 1 — ом шаге, После подачи граничных сигналов Z =— 1, и Х о = 9, по окончании переходных процессов сигналы 7. = 1 на правой границе матрицы устанавливаются в тех строках, на входы которых поступили максимальные числа, а на нижней границе -. само это число.

Устройство предназначено для решения задач оценки размещения элементов. Схема представляется B виде матричного эквивалента графа или гипе рграфа., описыв ающе го схему, При данной нумерации строк матрицы можно вычислит ° значение целевой функции оптимизации. Если поменять местами строки, то за счет изменения локальных свойств матрицы изменяется и значение целевой функции оптимизации. Таким образом, решение сводится к перестановке строк глатрицьг, т. е „ к ее изоморфному преобразовантлю с оценкой текущего размещения. Эта циклическая перестановка заканчива— ется в момент получения оптимального значения целевой ф -ткции итттл по истечении лимита времени. Строки матрицы отмечаются элементами схемы, а стогбцы †;тенями, соединяющими зти элементы. Таким образом, однородная среда„содержащая N x m элементов, физически, отображает матрицу цепей, состоящую из N элементов и тп соединятощих их цепей. Ка гересечении i-й строки и 1 — го столбца ставится единица, .сли i-й эле..е т входит в j-ю цепь, и в противном случае.

1430949

55

Длиной 1-й цепи называется ра:lHocть между номерами самой нижней строки, в которой =тоит единица в j-ом столбце, и номером самой верхней строки, в которой стоит единица в j-ом столб 5 це.

Устройство работает следующим образом, На вход 6 записи поступают данные по сигналу "1". На входе 13 происходит запись информации в элементы однородной среды. На вход 9 поступает сигнал "Запись" и информация из триггеров запоминания признака конеч- 15 ной точки переписывается в блок 5 памяти. Для нашего примера в однородную среду были записань1 данные, приведенные в табл,2 в графе "Состояния элемента однородной среды". На 20 индикаторных выходах элементов после окончания переходных процессов устанавливаются единицы, если элементы расположены между двумя другими элементами в триггерах запоминания ко в 25 нечной точки, в которых содержатся единицы или в триггерах запоминания конечной точки самого элемента содержится единица, в противйом случае установится "0"1, Для нашего примера З0 состояние индикаторных выходов отражено в соответствующих графах, табл,24. Информация с индикаторных выходов элементов каждого столбца поступает в блок подсчета единиц, соответству- 35 ющий данному столбцу. Блок подсчета единиц на выходе выдает двоичное число, равное количеству поступавших на его входы единиц. Для нашего примера — это графа Количество еди- 40 ниц" в соответствующих таблицах, Полученное число поступает на входы, соответствующие данному блоку подсчета единиц, сумматора и нахождения максимума. В сумматоре проис- ° 45 ходит суммиро в ан ие в сех дво ичных чисел поступивших на входы, а в блоке нахождения максимума отыскивается максимальное число из них.

Полученные оценки поступают на выходы устройства, откуда — на устройство управления. Для на|пего примера — это графы Сумма" и Максимум". Устройство управления сравнивает полученные значения целевой функции с предыдущим наилучшим значением и в случае их улучшения выдает сигнал Запись".на вход управ4 лсния памятью, в противном случае, как и в течение всего цикла работы устройства, на этот вход сигнал

"Запись" не поступает.

В соответствии с. любым рациональным алгоритмом выбираются строки, которые необходимо переставить и выдается сигнал на обмен строк. В нашем примере выбраны строки 1 и 3.

Затем производится оценка (как было описано выше) до тех пор, пока не будет найдено решение, удовлетворяющее некоторым критериям, либо пока не будет исчерпано время, отведенное на решение задачи. формула изобретения

Устройство для опенки размещения элементов, содержащее матрицу из и строк и m столбцов элементов однород— ной среды, входы управления перестановки столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановки строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы однородных элементов соединены с входом начальной установки устройства, информационный вход матрицы элементов однородной среды соед>а-ен с входом записи исходного гиперграфа ycт— ройства, о т л и ч а ю щ е е с я тем, что, с целью рас.пирения функциональных возможностей путем обеспечения возможности оценки текущего размещения при изоморфных преобразованиях по двум критериям — суммарной длины ребер и максимальной длины ребра и запоминания наилучшего размещения элементов, в него введены

1п блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, управляющий вход которого соединен с входом управления памятного устройства, i — е индикаторные выходгп матрицы элементов однородной среды (i = 1, m) соединены с входом

i — го блока подсчета единиц, выход которого соединен с i-ым информационным входом блока нахождения максимума и входом i — ro слагаемого сумматора, выходы которых соединены с первым и вторым выходами оценки текущего размещения соответственно, j-e информационные выходы матрицы эле1430949

Продолжение табл. l

Строка

X XI Пт

Таблица l

О О

Разряд

I II III

Строка Сигнал

Начальное состояо о. о

6 ние

1 О О

Таблица2 Номера цепей

Номер элемен3 4 5 6 7

1 2 та

Состояние индекса

1 1 ) 1 О О ) 1 О О О О О О

l 1 1 О О 0 1 1 1 О О 1 1

О ) 1 1 ) ) 1 1 1 1 О О О 1

1 1 О 1 О 1 О 1 О 1 О О 1 1

О О О l 1 1 О 1 О 1 1 1 О О

) 1 1 1 1 1 О О

О О 1 1 О 0

Количество единиц

5 2

Сумма

Максимум

Сигнал на вход памяти при оценке по сумме по максимуму

l с3

Обмен ментов однородной среды соединены с

)-ми информационными входами блока памяти (j — 1, и), выход которого соединен с информационным выходом устройства.

Разряд

1 1

1430949

Таблица3

Номера элемента

Номера целей

2 3 4 5

1 Т

6 J 7

Состояние индекса

00 00

0 0 1 !

1 ) 1 1

0 1 ) 1

0 1

) ) 0 1 0 0 0 1

0 1

01 01 01 00

0011111100

Ко личе с тв о единиц

3 6

Сумма

Максимум

Сигнал на вход памяти при оценке

0 по сумме. по максимуму

4 с 3

Обмен

Т а б л и ц а 4,Номер элемента

Номера цепей

3 4

Г

6 7

l !

1 2 5

11 00 00 00 00

1 1 1 1

1 1 1 1

0 0

0 0

0 0

0 0 1 1

00 01

00 11

0 0

0 0

0011

1 ) 1 1

1 ) ) 1

1101

00 01

00 11

Состояние индекса

) 1 0 1

) 1 1 1

01 01

1 ) 1 1

0 0 1 1

0 0 1 1

00 00

00 00

1 1 0 0

1430949!

) 6 (7

Номер элемента

4остояиие индекса, Количе с тв о единиц

Сигнал на вход памяти при оценке по сумме по максимуму б с 5

Обмен и так далее

Ю

Сумма

Максимум

2 3 .4 продолже ние табл . 4

1430949

Составитель А. Бо го слов с к их

Техред Л.Сердюкова Корректор А,06pywap

Редактор А. Ревин

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 5342/50

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4