В ПТБ Советский патент 1973 года по МПК G06T9/20 G06F15/173 

1

Изобретение относится к технике автоматической лредварительной обработки исходных данных задач математического программирования. УсТ|роЙ1Ство П:редназ начено для использования при поиске оптимальных решений комбинаторных задач «вкоторого класса, в частности, О коммивояжере, назначении и отыскании кратчайшего дерева на конечных поляых прафах, вершины которых расположены в непрерывных эвклидовы/х пространствах, описанных симметричными матрицами длин (стоимостей) дуг. К указанным формальным задачам на практике сводят такие задачи, как отыскание кратчайших за мкнутых путей (циклов) на транспорте, циклов движения измерительного и режуи1,его инструмента пр-и контроле и воздействии в отдельных точках (областях) технологического объекта, соста(Вление сложных энергетических сетей, линий связи и т. п.

Известно устройство для решения задачи о коммивояжере, содержащее телевизионную трубку с оптической системой, входы .которой соединены с .выходом соответствуюш,его сумматора и входОМ 1блока управления и памяти, каждый выход которого подключен ко входу соответствуюш;его сумматора, блок пилообразного напряжения и блок деления импульсов. В .процессе поиска решения это устройство выделяет выпуклые многоугольники,

которые затем объединяются в гамильтонов цикл с М1ииимиза.цней общей его длины.

Известное устройство можно применить к решению задач единственного класса - коммивояжера; оно отбирает для каждого узла только две, идентичные ему и двум .другим узлам, дуги (ребра), руководствуясь взаиморасположением этих трех узлов, причем отобранные дуги считаются лерспективнымИ на участке в кратча1 1шем гамильтоновом -цикле (кщ).

Цель изобретения - создание устройства для решения задач нескольких классов с повышенной размерностью, а также для выделения более чем двух перспективных на участке в КГЦ дуг для каждого узла конечного графа, вершины которого .расположены в двумерном евклидовом пространстве, описанного симметричной матрицей.

Предлагаемое устройство для выборки перспективных дуг графа отличается тем, что в него введены генератор синусоидального напряжения, блок перемножения, блок сдвига синусоидального напряжения и блок переключеиия, входы которого соединены соответственно с телевизионной трзбкой и выходом блока деления импульсов: каждый из выходов блока переключения соединен с соответствующим входом блока управления и памяти, выход которого соединен со входом блока синусоидальнОГО Напряжения. Выход последнего соединен с первым входом блока пе:ремножения, второй вход которого соединен с регистрнрующнм входом блока управления и Памяти; выход блока .перемножения соединен со входом блока сдвига синусоидального напряжения и входом одного из сумматоров, а выход блока сдвига синусоидального иалряжения связан со входом другого сумматора.

(Бло:К-схема устройства приведена на чертел е.

Устройство содержит двумерную область расположения узлов, представленных, предположим, (В светяш,ихся точечных объектов, разделеннзю на восемь .конусов Л-3; передающую телевизионную трубку / с оптической системой 2; сумматоры 3 к 4 соответственно горизонтальной и вертикальной развсрто.к, выходы Которых -присоединены соответственно ко входам .горизонтальной и вертикальной раЗ вертОК трубки; .блок 5 сдвига сииусои.дального напряжения иа +90°, вход которого соединен с сигнальным входом блока 4, а выход - с сигнальным входом блока 5; бло;К (иеремиожения 6, выход которого соединен со входом блока 5; генератор сииусои.дального (На.пряжения 7, выход которого соединен с первым сигнальным входом блока 6; блок пилоо,браз«ого на1пряжения 8, выход которого соединен со вторым сигнальным входом блока 6; блок деления импульсов Я блок переключения 10, регистрационный ВХод которого соединен с (Выходом трубки, а сигнальный вход - с выходом блока 9; блок управления и памяти 11, каж.дый из девяти сигнальных входов которого соединен с соответствующим сигнальным выходом блока 10. Один из координатных входов блока // соединен с выходом блока 3, а другой - с выходом блока 4. Регистрирующий вход блока // соединен с выходом блока 8, один координатный выход блока /,/ - с координатным входом блока 3, а другой - с координатным входом блока 4; сигнальный выход блока // - со входал и блоков 7, S, 9; выходом устройства является ин1формационный выход блока I//.

Импульс с сигнального выхода блока И включает блоки 7 и 8, с выходов которых на сигнальные входы |блока 6 поступают синусоидальное и пилообразное напряжения. Результат их перемножения подается в блок 3 через блок 5 и в блок 4 непосредственно и далее через указанные блоки в катушки отклоняющИХ систем телеви знойной трубки, сканирую.щее Пятно (СП) которой начинает двигаться но спирали в области расположения объектов из некоторой точ.кн области (в заданной системе координат) до тех пор, пока СП не наткпется на какой-либо объект /i. В этот момент с выхода трубки снимается импульс, который проходит через блок 10 и с его нулевого сигнального выхода попадает в блок 1/7, где по этой команде записываются

мгновенные значения выходных напряжений сум1М.аторов 3 и 4, пропорциональные декартовым коор.динатам объекта ii. На этом заканчивается нулевой цикл работы устройства и обнуляются выходы блоков 3-8. Первый цикл работы начинается подачей импульса с сигнального выхода бло.ка // на входы блоков 7, 8 и 5 и нодачей мгновенных напряжений сумматоров ;в виде постоянных во времени напряжений (на все время первого цикла) на координатные входы сумматоров, вследствие чего центр спирали совмещается с объектом гь Блоки 7 « 8 формируют спираль, как описано выше, а блоки 9 и 10 разбивают двумерное пространство (области расположения объектов) согласно программе на конусы Л-3. Во врем-я движения СП по спирали вдоль одного витка параметр mt синусоиды (1ВЫХО.ДНОГО напряженЕЯ f/y блока 7)

изменяется от О до 360°. При этом от О до 45° сигнал с выхода трубки может лопасть в блок // только через первый сигнальный выход блока 10, соединенный с группой ячеек, относящихся к конусу Л, нри 45° с выхода блока 9 снимается импульс Ug, после чего выходной сигнал трубки может пройти только через второй сигнальный выход (блока 10 вплоть до угла 90° (конус Б) после нового .переключения сигнального выхода блока ,10 и т. д. по

всем конусам в течение полного оборота СП по витку. В момент 360-405° запись информации об объекте может вновь попасть в блок :11 только ПО Первому сигнальному вхоДУВнутри конуса объекты разбиваются на классы так: если цри движении по какому-то из конусов СП прохо.дигг через объект, то по команде с выхода трубки вместе с координатами объекта в блок //записывается расстояние до него от центра спирали, которое пропорционально мгновенному значению выходного напряжения блока 8, так как движеиие СП описывается формулой Cit-C li , где сомножитель есть выходное напряжеНие блока 8, / / -1. При задании отбора дуг, предположим, по двум классам (), координаты объектов и расстояния до них будут записаны по объектам, находящимся на двул различных расстояниях до центра

спирали, а по остальным объектам блок И записи на произведет, хотя данные о них на его входы будут поступать.

Первый цикл заКанчнвается, когда по всем конусам отобраны дуги двух классов, либо, при невыполнении этого условия, - после выхода СП за пределы олраниченной (что всегда происходит на практике) области расположения 0|бъектов. При окончании первого цикла обнуляются выходы блоков 3-8.

Второй рабочий цикл, как и первый, начинается подачей импульса с сигнального выхода блока 11 и подачей па координатные входы сумматоров постоянных напряжений, соответствующих координатам объекта iz, с которым теперь совмещается центр спирали. Далее происходят те же действия, ,что и. «а первом рабочем дйкле. После производства п-2 рабочих циклов ПО выбор.ке дуг, т. е. последовательного .перемепдания eHTipa спирали п-1 ра,з в каждый из объектов i, устройство останавливается. Спираль движения СП, начало которой совмещено с выбранным объектом и которая пересекает другой объект, .показана на чер- ю теже. Предмет изобретения Устройство для выборки перспективных дуг is графа, содержащее телевизионную Т1рубку с оптической системой, входы которой соединены с выходом соответствующего сумматора и вхояОМ бло1ка управления и памяти, каждый выход которого подключен ко входу соответ- 20 ствующего сумматО|ра, блок пилообразного 5 напряжения и блок деления пм1пульсов, отличающееся тем, что, с |целью расширения области применения устройства, в него введены генератор синусоидального напряжения, блок перемножения, блОК сдвига синус01Идальното лапряження и -блок переключения, входы которого соединены соответственно с телевизионной трубкой н выходом блока деления ИМПУЛЬСОВ, Каждый из выходов блока переключения соединен с соответствующем входом блока управления и памяти, выход которого соединен со входом блока сннусоидального напряжения, выход которого соединен с первым ВХОДОМ блока перемйож-бния. второй вход которого соединен с региютрирующим .влодом блока управления и ламят-и, выход блока перемножения соединен со еходом блока сдвига синусоидального .наиряжения и входом одного из сумматоров, а выход блока сдвига си«усоидального напряжения связан со входол другого суМ|Матора.