В птб

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

397915

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 23.Ч11.1971 (№ 1684397f18-24) с присоединением заявки №

Приоритет

Опубликовано 17.1Х.1973. Бюллетень ¹ 37

Дата опубликования описания 23Л.1974

M. Кл, б OGf 15/32

Государственный комитет

Совета Министров АЗССР оо долам изобретений и OTKpblTMH

УДК 681.333.001.57 (088.8) Автор изобретения

ВПТБ

В. А. Леонтьев

Заявитель

УСТРОЙСТВО ДЛЯ ВЫБОРКИ ПЕРСПЕКТИВНЫХ

ДУГ ГРАФА

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

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

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

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

1п участке в кратчайшем гамильтоновом цикле (кгц).

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

65 ка синусоидального напряжения. Выход последнего соединен с первым входом блока перемножения, второй вход которого соединен с регистрирующим входом блока управления и памяти; выход блока перемножения соединен со входом блока сдвига спнусоидального на пряжения н входом одного из сумматоров, а выход блока сдвига спнусоидального напряжения с вязан со входом другого сумматора. Блок-схема устройства приведена на чертеже.

Устройство содержит двумерную область расположения узлов, представленных, предположим, в виде светящихся точечных объектов, разделенную на восемь .конусов А — 3; передающую телевизионную трубку 1 с оптической системой 2; сумматоры 8 и 4 соответственно горизонтальной и вертикальной развсрток, выходы которых присоединены соответственно ко входам,горизонталь ной и вертикальной разверток трубки;,блок 5 сдвига синусоидального напряжения,на +90, вход которого соединен с сигнальным входом олока 4, а выход — с сигнальным входом блока

8; блок перемножения б,,выход .которо го соединен со входом:блока 5; генератор синусондального напряжения 7, выход которого соединен с первым сигнальным входом блока б; блок пилообразного напряжения 8, выход которого соединен со вторым, сигнальным входом блока б; блок деления импульсов 9, блок переключения 10, регистрационный вход которого соединен с,выходом трубки, а сигнальный вход — с выходом блока 9; блок управления и памяти П, каждый из девяти сигнальных входов которого соединен с соответствующим сигнальным выходом блока 10.

Один из координатных входов блока П соединен с выходом блока 8, а другой — с выходом блока 4. Регистрирующий вход блока

П соединен с выходом блока 8, один координатный вы ход блока 11 — с координатным входом блока 8, а другой — с координатным входом блока 4; сигнальный выход блока

11 — со входами, блоков 7, 8, 9; выходом устройства является информационный выход блока I l.

Импульс с сигнального выхода блока 11 включает блоки 7 и 8, с выходов, которых на сигнальные входы блока б поступают синусоидальное и пилообразное напряжения. Результат их перемножения подается в блок 8 через блок 5 и в блок 4 непосредственно и далее через указанные блоки в катушки откло няющих систем телевизионной трубки, сканирующее пятно (СП) которой начинает двигаться по спирали в области расположения объектов пз некоторой точки области (в заданной системе координат) до тех пор, пока СП не наткнется на какой-либо ооъект Ii.

В этот момент с выхода трубки снимается импульс, который проходит через блок 10 и с его нулевого сигнального выхода попадает в блок 11, где по этой команде записываются

50 мгновенные значения .выходных напряжений сумматоров 8 и 4, пропорциональные декартовым координатам объекта i . На этом заканчивается нулевой цикл работы устройства и обнуляются выходы блоков 8 — 8. Первый цикл работы начинается подачей импульса с сигнального выхода блока 11 на входы блоков 7, 8 и 9 и подачей мгновенных напряжений сумматоров;в,виде IIIocToHIHíûõ,во времени напряжений (на все время первого цикла) на координатные входы сумматоров, вследствие чего центр спирали совмещается с объектом i . Блоки 7 и 8 формируют спираль, .как описано выше, а блоки 9 и 10 разбивают двумерное пространство (области расположения объектов) согласно программе на конусы А — 3. Во время движения СП .по спирали вдоль одного витка параметр оМ синусоиды (выходного,напряжения U7 блока 7) изменяется от О до Зб0 . При этом от О до 45 сигнал с выхода трубки может попасть в блок

11 только через первый сигнальный выход блока 10, соединенный с группой ячеек, относящихся .к конусу А, при 45 с выхода блока 9 снимается импульс Ug, после чего выходной сигнал трубки может пройти только через второй сигнальный выход блока 10 вплоть до угла 90 (конус Б) после нового,переключения сигнального выхода блока,10 и т. д. по всем конусам в течение полного оборота СП по вижу. В момент 360 — 405 запись информа ц ии об объекте может вновь попасть в блок,11 только по первому сигнальному входу.

Внутри конуса объекты разбиваются на классы так: если при движении по какому-то из конусов СП проходит через объект, то по команде с выхода трубки вместе,с .координатами объекта в блок 11 записывается расстояние до него от центра спирали, которое пропорционально мгновенному значению BbI ходного напряжения блока 8, так .как движе ние СП описывается формулой С,t C l j", где сомножитель C t есть выходное напряжение блока 8, j= ф — 1. При задании отбора дуг, пред положим, по двум классам (2=2), координаты объектов и,расстояния до них будут записаны по объектам, находящимся на двух разл ичных расстояниях до центра спи рали, а по остальным объектам блок 11 записи не произведет, хотя данные о .них на его входы будут поступать.

Первый .цикл, заканчивается, когда по всем ко нусам отобраны дуги двух, классов, либо, при невыполнении этого условия, — после выхода СП за пределы опраниченной (что всегда происходит на практике) области ра сположения объектов. При окончании первого цикла обнуляются выходы блоков 3 — 8, Второй .рабочий цикл, как и первый, начинается подачей импульса с сигнального выхода блока 11 и подачей на координатные входы сумматоров постоянных н пряжен ий, соответствующих координатам объекта iz, с которым

397915

Предмет изобретения

Составитель В. Озеров

Техред Л. Богданова

Редактор А. Синицына

Корректор В. Жолудева

Заказ 3717/17 Изд. № 26 Тираж 647 Подписное

LIHHHIIH Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, )К-З5, Раушская наб., д. 4,5

Типография, пр. Сапунова, 2 теперь совмещается центр спирали. Далее происходят те же действия, что и. на первом рабочем, цикле. После производства n — 2 tðàбочих циклов по выборке дуг, т. е. последовательного;перемещения центра спирали и — 1 ..раз в каждый из объектов, устройство останавливается.

Спи раль движения СП, начало которой совмещено с выбранным о|бъектом и которая пересекает другой о бъект, показана на чертеже.

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

10 переключения соединен с соответствующим входом блока управления .и памяти, выход которого соединен со входом блока синусо идального напряжения, выход которого соединен с первым входом блока перемножения, 15 второй вход которого соединен ic реги стрирующим .входом блока управления и памяти, выход блока перемножения соединен со входом,блока сдвига синусоидального напряжения и входом одного из сумматоров, а выход

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