В птб

397915 Союз СоветскихСоциалистическихРеспублик ависимое от авт. свидетельствааявлено 23.Ч 11.1971 ( 1684397/18-24). Кл, С 061 15/32 рисоединением заявкиоритет сударственны оиота Министр по делам изоои открыти амитет "ССРениуу Опубликовано 17.1 Х.1973. Бюллетень37Дата опубликования описания 23.1.1974 681.333.001,5(088,8) Авторизобретения впт1,. - гус 11 г,ергуО 3 Д 1 Оу В еонть аявитель РОЙСТВО ДЛЯ ВЫБОРКИ ПЕРСПЕКТИВН ДУГ ГРАФАИзобретение относится к технике автоматической предварительной обработки исходных данных задач математического программирования. Устройство предназначено для использования при поиске оптимальных решений комбинаторных задач некоторого класса, в частности, о коммивояжере, назначении и отыскании кратчайшего дерева на конечных полных прафах, вершины которых расположены в непрерывных эвклидовых:пространствах, описанных симметричными матрицами длин (стоимостей) дуг. К указанным формальным задачам на практике сводят такие задачи, как отыскание кратчайших замкнутых путей (циклов) на транспорте, циклов движения измерительного и режущего инструмента при контроле и воздейстьии в отдельных точках (областях) технологического объекта, составление сложных энергетических сетей, линий связи и т, п.Известно устройство для,решения задачи о коммивояжере, содержащее телевизионную трубку с оптической системой, входы которой соединены с выходом соответствующего сумматора и входом блока управления и памяти, каждый выход которого подключен ко входу соответствующего сумматора, блок пилообразного напряжения и блок деления импульсов. В процессе поиска решения это уст,ройство выделяет выпуклые многоугольники,которые затем объединяются в гамильтонов цикл с минпмизацией общей его длинны.Известное устройство можно применить крешению задач единственного класса - коммивояжера; оно отбирает,для каждого узла только две, идентичные ему и двум другим узлам, дуги (ребра), руководствуясь взаиморасположением этих трех узлов, причем отобранные дуги считаются,перспективными на О участке в кратчайшем гамильтоновом цикле(кгц). Цель изобретения - создание устройствадля решения залач несколыких классов с повышенной размерностью, а также для вы 1 лсления более чем,двух перспективных на участке в кгц л; лля каждого зла конечного графа, вершины которого расположены в двумерном свклиловом пространстве. описанного симметричной матрицей.0 Предлагаемое устройство для выборки перспективных дуг графа отличается тем, что в него введены генератор синусоидального напряжения, блок переиоженля, блок сдвига синусоилального напряжения и блок переключения, входы которого соединены соответственно с телевизионной трубкой и выходом блока деления импульсов: каждый пз выходов блока переключения соединен с соответствующим вхолом блока управления и памяти, выход которого соединен со входом бло55 60 65 ка синусоидального напряжения, Выход последнего соединен с первым входом блока перемножения, второй вход которого соединен с регистрирующим входом блока управления и памяти; выход блока перемножения соединен со входом блока сдвига спнусоидального напряжения н входом одного из сумматоров, а выход блока сдвига спнусоидального напряжения связан со входом другого сумматора.Блок-схема устройства приведена на чертеже.Устройство содержит двумерную область расположения узлов, представленных, предположим, в виде светящихся точечных объектов, разделенную на восемь конусов А - 3; передающую телевизионную трубку 1 с оптической системой 2; сумматоры 3 и 4 соответственно горизонтальной и вертикальной развсрток, выходы которых присоединены соответственно ко входам,горизонтальной и вертикальной разверток трубки;,блок 5 сдвига синусоидального напряжения ,на +90, вход которого соединен с сигнальным входом олока 4, а выход - с сигнальным входом блока 3; блок перемножения бвыход которого соединен со входом блока 5; генератор синусондального напряжения 7, выход которого соединен с первым сигнальным входом блока б; блок пилообразного напряжения 8, выход которого соединен со вторым, сигнальным входом блока б; блок деления импульсов 9, блок переключения 10, регистрационный вход которого соединен с,выходом трубки, а сигнальный вход - с выходом блока 9; блок управления и памяти П, каждый из девяти сигнальных входов которого соединен с соответствующим сигнальным выходом блока 10.Один из координатных входов блока 11 соединен с выходом блока 3, а другой - с выходом блока 4. Регистрирующий вход блока 11 соединен с выходом блока 8, один координатный вьпод блока 11 - с координатным входом блока 3, а другой - с координатным входом блока 4; сигнальный выход блока 11 - со входами, блоков 7, 8, 9; выходом устройства является ниформационный выход блока 11.Импульс с сигнального выхода блока 11включает блоки 7 и 8, с выходов, которых на сигнальные входы блока б поступают синусоидальное и пилообразное напряжения. Результат их перемножения подается в блок 3 через блок 5 и в блок 4 непосредственно и далее через указанные блоки в катушки отклоняющих систем телевизионной трубки, сканирующее пятно (СП) которой начинает двигаться по спирали в области расположения объектов пз некоторой точки области (в заданной системе координат) до тех пор, пока СП не наткнется на какой-либо ооъект 1 ь В этот момент с выхода трубки снимается импульс, который проходит через блок 10 и с его нулевого сигнального выхода попадает в блок 11, где по этой команде записываются 5 10 15 20 25 30 35 40 45 50 мгновенные значения выходных напряжений сумматоров 3 и 4, пропорциональные декартовым координатам объекта ь На этом заканчивается нулевой цикл работы устройства и обнуляюгся выходы блоков 3 - 8, Первый цикл работы начинается подачей импульса с сигнального выхода блока 11 на входы блоков 7, 8 и 9 и подачей мгновенных напряжений сумматоров;в,виде постоянных,во времени напряжений (на все время первого цикла) на координатные входы сумматоров, вследствие чего центр спирали совмещается с объектом г,. Блоки 7 и 8 формируют спираль, как описано выше, а блоки 9 и 10 разбивают двумерное пространство (области расположения объектов) согласно программе на конусы А - 3. Во время движения СП по спирали вдоль одного витка параметр оМ синусоиды (выходного,напряжения У 7 блока 7) изменяется от 0 до ЗбО. При этом от 0 до 45 сигнал с выхода трубки может попасть в блок 11 только через первый сигнальный выход блока 10, соединенный с группой ячеек, относящихся к конусу А, при 45 с выхода блока 9 снимается импульс с 19, после чего выходной сигнал трубки может пройти только через второй сигнальный выход блока 10 вплоть до угла 90 (конус Б) после нового,переключения сигнального выхода блока,10 и т, д. по всем конусам в течение полного оборота СП по вижу. В момент 360 - 405 запись информации об объекте может вновь попасть в блок,11 только по первому сигнальному входуВнутри конуса объекты разбиваются на классы так: если при движении по какому-то из конусов СП проходит через объект, то по команде с выхода трубки вместе,с координатами объекта в блок 11 записывается расстояние до него от центра спирали, которое пропорционально мгновенному значению выходного напряжения блока 8, так,как движение СП описывается формулой С,1 С 11", где сомножитель С 1 есть выходное напряжение блока 8, 1=У - 1. При задании отбора дуг, предположим, по двум классам (1=2), координаты объектов и,расстояния до них будут записаны по объектам, находящимся на двух различных расстояниях до центра спирали, а по остальным объектам блок 11 записи не произведет, хотя данные о них на его входы будут поступать,Первый цикл, заканчивается, когда по всем конусам отобраны дуги двух, классов, либо, при невыполнении этого условия, - после выхода СП за пределы ограниченной (что всегда происходит на практике) области расположения объектов. При окончании первого цикла обнуляются выходы блоков 3 - 8,Второй рабочий цикл, как и первый, начинается подачей импульса с сигнального выхода блока 11 и подачей на координатные входы сумматоров постоянных напряжений, соответствующих координатам объекта 12, с которым397915 Составитель В. Озеро Техред Л. Богданова дактор А. Синицын олудева кт 717/ 7ЦНИИПИ Подписное Тираж 647комитета Совета Миннсретений и открытийРаушская наб., д. 475 Изд.26 сударственного по делам из Москва, Жов СС ипография, пр. Сапунова,теперь совмещается центр спирали. Далее происходят те же действия, что и на первом рабочем, цикле. После производства и - 2 рабочих циклов по выборке дуг, т. е. последовательного ,перемещения центра спирали и - 1 .раз в каждый из объектов , устройство останавливается.Спираль движения СП, начало которой совмещено с выбранным объектом и которая пересекает другой объект, показана на чертеже. Предмет изобретения Устройство для выборки перспективных дуг графа, содержащее телевизионную трубку с оптической системой, входы которой соединены с выходом соответствующего сумматора и входом блока управления и памяти, .каждый выход которого подключен ко входу соответствующего сумматора, блок пилообразного напряжения и блок деления импульсов, отличающееся тем, что, с целью расширения области применения устройства, в него введены генератор синусоидального напряжения, 5 блок перемножения, блок сдвига синусоидального напряжения и,блок переключения, входы которого соединены соответственно с телевизионной трубкой и выходом блока деления импульсов, каждый из выходов блока 10 переключения соединен с соответствующимвходом блока управления и памяти, выход которого соединен со входом блока синусоидального напряжения, выход которого соединен с первым входом блока перемножения, 15 второй вход которого соединен с регистрирующим .входом блока управления и памяти, выход блока перемножения соединен со входом,блока сдвига синусоидального напряжения и входом одного из сумматоров, а выход 20 блока сдвига спнусоидального наоряжениясвязан со,входом лругого сумматора.