Вычислительное устройство для решения симметричной задачи о комливояжере

Сова Советскив Социалистические РеспубликЗависимое от авт. свидетельстваЗаявлено 12.7.1970 (Мч 1436277/18 б 06 д 7/48 с присоединением заявкиПриоритетОпубликовано 07.111.1972. Бюллетень9Дата опубликования описания 21.1 Ч.1972 митет по делам аобретений и открытипри Совете МинистровСССР К 681,333.001.5 (083.8) ф :., Гц.- .фВ, А, Леонтьевавления (автоматики и телемеханики) торобретения нститут пробле явител ЬНОЕ УСТРОЙОЙ ЗАДАЧИ ЫЧИСЛИТ СИММЕТРИ ВО ДЛЯ РЕШЕНИ КОММИВОЯЖЕР Изобретение относится к области вычислительной техники и предназначено для ускоренного решения симметричной задачи большой размерности о коммивояжере, к которой сводится поиск оптимальных или близких к оптимальным маршрутов при оптическом, радиолокационном, механическом и другом контроле или воздействии в дискретных полях, а также в вопросах планирования экономики, организации производства.Задачу о коммивояжере можно решать на универсальных ЭЦВМ,граммы и памяти, блокформации. оразованпя иннии размерности зада- возрастает время реше более чем 50 - 60 точек ВМ решение практиче - создание быстродейстного устройства, пред- ения симметричных зао коммивояжере и виния результата решеблагодаря применению 25ажения, передающей тес оптической системой,переключения, генератонапряжения, генератораимпульсов, блока про Однако при увеличчи (т. е, числа точек)ния ее и при наличиина существующих ЭЦски невозможно.Цель изобретениявующего вычислителназначенного для решдач большого размерзуального представлния.Это достигаетсяблока ввода и отобрлевизионной трубкисумматоров, блокаров пилообразногосинхронизирующих На фиг. 1 изображена блок-схема устройства; на фиг. 2 - экран ввода с выделенными на нем заданными множеством точек А, Б, В, Г и Д и некоторыми траекториями сканирующего пятна.Устройство состоит из следующих блоков;блока 1 ввода и отображения, передающей телевизионной трубки 2 с оптической системой 3, сумматора 4 вертикальной и сумматора 5 горизонтальной разверток, блока б переключения, генератора 7 пилообразного напряжения с переменным наклоном пилы, генератора 8 пилообразного напряжения с постоянным наклоном пилы, генератора 9 спнхронизирующих импульсов, блока 10 программы и памяти, блока 11 преобразования информации.Блок ввода и отображения имеет два экрана. Экран ввода предназначен для отображения информации о расположении точек друг относительно друга. Он представляет собой матричную панель, состоящую из большого числа элементов, которые, будучи возбуждены, светятся, Экран отображения служит для отображения результатов решения задачи и конструктивно выполнен так же, как и экран ввода.3В качестве примера работы устройства взято множество из пяти точек А, Б, В, Г и Д (фиг. 2). Работа устройства начинается с подачи первичной информации на вход первичной информации блока 11 вручную оператором или автоматически по внешпему для устройства каналу связи. С двух выходов первичной информации поступают сигналы на соответствующие горизонтальные и вертикальные шины матрицы экрана ввода, на котором появляется заданное множество объектов в виде светящихся точек (возможна конструкция с непосредственным нанесением информации о взаиморасположении точек оператором на экран при помощи светового карандаша). Одновременно с информационного выхода блока 11 на информационный вход блока 10 подаются импульсы, количество которых равно количеству точек на экране ввода, и это количество запоминается. Если точек больше трех, то, согласно заложенной программе, с помощью трубки 2 проводится осмотр экрана ввода (поля) сканирующим пятном. В процессе сканирования пятно периодически начинает движение из точек, названных центрами (на фиг. 2 точки А, В и Г, а также точка левого нижнего угла экрана).Сканирование происходит вдоль лучевых прямых (лучей) в направлениях, показанных на фиг. 2 стрелками. Каждый последующий по порядку сканирования луч получается поворотом предыдущего луча на некоторый угол в одну и ту же сторону в течение всего процесса. В качестве начального центра берется какая-нибудь граничная точка поля или об ьект заданного множества (светящаяся точка), если объект расположен на границе поля, Поворот луча, т. е. изменение направления движения сканирования, осуществляется за счет того, что на одну из систем развертки трубки 2 подается пилообразное периодическое напряжение с периодом 10 с переменным наклоном пилы от периода к периоду, по с постоянным наклоном пилы внутри каждого периода, а на другую систему развертки в это же время - пилообразное периодическое напряжение с периодом 1, при постоянном наклоне пилы от периода к периоду. Величина периода 1, выбирается из условий динамичности контролируемой системы точек, а скорость изменения наклона меняющейся пилы - из условий точности или разрешающей способности устройства. Направление поворота может быть любым; в данном случае выорано против часовой стрелки, а в качестве исходного центра взят левый нижний угол поля (фиг, 2).Построение первого выпуклого многоугольника начинается с того, что синхронизирующие импульсы с выхода генератора 9 подаются с периодом 10 на входы генераторов 7 и 8 и запускают их. Выходные напряжения этих блоков изменяются в соответствии с заданной программой. Эти напряжения подаются непосредственно на координатные входы бло 5 10 15 20 гз 30 35 40 45 50 55 60 65 ка 10 и одновременно через блок б соответственно на генераторные входы сумматоров 4 и 5. Выходные напряжения сумматоров 4 и 5 поступают соответственно в системы вертикальной и горизонтальной разверток и одновременно на оба координатных входа блока 10, но не проходят в него, Эти напряжения пропорциональны координатам соответственно У и Х сканирующего пятна трубки 2 в декартовой системе координат. При движении вдоль луча с углом а 1 (фиг. 2) в момент времени 1, сканирующее пятно проходит через точку А и на выходе трубки 2 возникает импульс, поступающий на вход обнаружения блока 10, в результате чего мгновенные значения напряжений сумматоров 4 и 5 проходят в блок 10 и запоминаются (эти напряжения пропорциональны соответственно координатам У и Х). Одновременно величины напряжения сумматоров 4 и 5 через блок 10 проходят в блок 11 на вход вторичной информации, преобразовываются в цифровую форму и с выхода вторичной информации попадают в блок 1, где на экране отображения появляются светящиеся точки с координатами, соответствующими координатам точки А. Сканирующее пятно продолжает при этом двигаться по лучу с углом а 1 до конца данного периода 1,. В момент времени 1, соответствующий концу данного и началу следующего периода 1 о, запомненные величины из блока 10 подаются на координатные входы сумматоров 4 и 5, в результате чего центр лучей из исходного положения - левого нижнего угла - перемещается в точку А. В процессе сканирования в конце периода 1 о, во время которого угол поворота луча достигает а=45, величина напряжения генератора 7 достигает предельного значения, равного по абсолютной величине напряжению генератора 8 в конце каждого периода 10. Так как оба напряжения поступают в блок 10, то, в сооетси с рорммой, в этот момент из блока 10 подается управляющий импульс на управляющие входы блока б и генератора 7. Блок б переключает выход генератора 7 с генераторного входа сумматора 4 на выход генератора 8, а выход генератора 8 переключается с генераторного входа сумматора 5 на генераторный вход сумматора 4, Генератор 7 по этому сигналу начинает уменьшать наклон пилы по линейному закону.При движении вдоль луча с углом а 1+а в момент времени 1, сканирующее пятно проходит через точку Б, возникает импульс на трубке 2 и координаты точки Б записываются в блоке 10, а сканирующее пятно движется далее по этому. же лучу. В момент времени 14 оно проходит через точку В и возникающий импульс на трубке 2 записывает координаты точки В в блок 10, а луч продолжает движение вдоль луча с углом а+а до границы поля. При этом вся информация о точке В обрабатывается так же, как и информация о точке А, и принимаются аналогичные реше45 50 55 Оо 65 5яия: в момент времени 14 на координатные входы сумматоров 4 и 5 из блока 10 подаются запомненные величины напряжений и центр лучей переносится в точку В, На экране отображения возбуждается ячейка, соответствующая точке В в системе декартовых координат. Однако блок 1 О не только пропускает сигналы, возбуждающие ячейку, соответствующуюую точке В, но и добавляет сигналы, по которым возбуждаются ячейки экрана отображения вдоль отрезка, соединяющего ячейки, соответствующие точкам А и В. При движении сканирующего пятна вдоль луча с углом а+а 2+аз сканирующее пятно проходит через точку Г, информация о которой обрабатывается так же, как и для точек А и В, и принимаются аналогичные решения, в результате чего на экране отображения появляется светящийся отрезок, соответствующий отрезку между точками В и Г, а центр лучей перемещается в точку Г,Далее при сканировании из центра в точке Г вдоль луча с углом а+а 2+аз+а 4 сканирующее пятно вторично проходит через точку А, на экране отображения появляется светящийся отрезок, соответствующий отрезку между точками Г и А, и на этом цикл построения первого выпуклого многоугольника заканчивается, Так как координаты точек А уже имелись в блоке 10, то на командные входы генераторов 7 и 8 с командного выхода блока 1 О поступают импульсы, в результате чего напряжения генераторов 7 и 8 становятся равными нулю. Одновременно из блока 10 перестают подаваться напряжения на координатные входы сумматоров 4 и б. Поэтому сканирующее пятно оказывается снова в исходном положении - левом нижнем углу.После окончания первого цикла построения первого выпуклого многоугольника, если не все точки заданного множества зафиксированы на экране отображения, начинается второй цикл построения второго многоугольника. В блоке 10 заложена жесткая программа изменения за цикл напряжений генераторов 7, 8 и 9 и момента появления импульсов на блоке б и генераторе 8, поэтому построение второго выпуклого многоугольника (т. е. запоминание, обработка и отображение информации) такое же, как и первого. Однако при сканировании поля, хотя по мере прохождения сканирующего пятна через точки, являющиеся вершинами первого многоугольника, в блок 10 поступают сигналы трубки 2, устройство на эти сигналы не реагирует, поскольку координаты этих точек уже запомнены в блоке 10. На экране отображения блока 1 второй выпуклый многоугольник после его построения будет находиться внутри первого, Таким образом, циклов будет столько, сколько окажется выпуклых многоугольников (ВМ). При этом общим правилом для всех циклов является то, что при прохождении сканирующего пятна во второй раз за цикл через какую-то вершину строящегося ВМ из 5 10 15 20 г 5 30 35 40 Предмет изобретения Вычислительное устройство для решения симметричной задачи о коммивояжере, содержащее блок переключения, блок преобразования информации, генератор синхронизирующих импульсов, блок программы и памяти, блок ввода и отображения, передающую телевизионную трубку с оптической системой, сумматоры вертикальной и горизонтальной разверток, генераторы пилообразного напряжения с постоянным и переменным наклоном, отличающееся тем, что, с целью расширения функциональных возможностей устройства, в нем выходы сумматоров вертикальной и горизонтальной разверток соединены соответственно с системами вертикальной и горизонтальной разверток передающей трубки и с двумя координатными входами блока программы и памяти, один из координатных выходов которого соединен с координатным входом сумматора вертикальной развертки, а другой с координатным входом сумматора горизонтальной развертки, генераторузов кто аказ 903/12 Изд.388 Тираж 448НИИПИ Комитета по делам изобретений и открытий при СовеМосква, Ж, Раушская наб д, 4/5 Подписноепиетров СССР ипография, пр. Сапунова,ный вход сумматора вертикальной развертки соединен с одним из выходов блока переключения, а генераторный вход сумматора горизонтальной развертки соединен с другим выходом блока переключения, один из сигнальных входов которого соединен с одним из генераторных входов блока программы и памяти и с выходом генератора пилообразного напряжения с переменным наклоном, а другой сигнальный вход блока переключения соединен с вторым генераторным входом блока программы и памяти и с выходом генератора пилообразного напряжения с постоянным наклоном, а сигнальные входы генератора пилообразного напряжения с переменным наклоном и генератора пилообразного напряжения с постоянным наклоном соединены между собой и с выходом генератора синхронизирующих импульсов, управляющий вход которого соединен с генераторным выходом блока программы и памяти, командный выход которого соединен с командными входами генераторов пилообразного напряжения с переменным и постоянным наклоном, управляющий вход генератора пилообразного напряжения с переменным наклоном соединен с управляющим входом блока переключения 5 и с одним из управляющих выходов блокапрограммы и памяти, другой управляющий выход которого подключен к утиравляющему входу генератора пилообразного напряжения с постоянным наклоном, а каждый из выхо дов вторичной информации блока программыи памяти подключен к соответствующему входу вторичной информации блока преобразования информации, каждый из выходов вторичной информации которого подключен к 15 соответствующему входу экр ан а ото бр аженияблока ввода и отображения, каждый из входов экрана ввода которого соединен с соответствующим выходом первичной информации блока преобразования информации, ин формационный выход которого подключен кинформационному входу блока программы и памяти, вход обнаружения которого соединен с выходом передающей трубки.