ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИММЕТРИЧНОЙ ЗАДАЧИ О КОМЛ^ИВОЯЖЕРЕ Советский патент 1972 года по МПК G06G7/122 

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

Задачу о коммивояжере можно решать на универсальных ЭЦВМ.

Однако при увеличении размерности задачи (т. е. числа точек) возрастает время решения ее и при наличии более чем 50-60 точек на сушествуюших ЭЦВМ, решение практически невозможно.

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

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

На фиг. 1 изображена блок-схема устройства; на фиг. 2 - экран ввода с выделенными на нем заданными множеством точек А, Б, В, Г и Д и некоторыми траекториями сканирующего пятна. Устройство состоит из следующих блоков:

блока / ввода и отображения, передающей телевизионной трубки 2 с оптической системой 3, сумматора 4 вертикальной и сумматора 5 горизонтальной разверток, блока 6 переключения, генератора 7 пилообразного напряжения с переменным наклоном пилы, генератора 8 пилообразного напряжения с постоянным наклоном пилы, генератора 9 синхронизирующих импульсов, блока W программы и памяти, блока 11 преобразования

информации.

Блок ввода и отображения имеет два экрана. Экран ввода предназначен для отображения информации о расположении точек друг относительно друга. Он представляет собой

матричную панель, состоящую из большого числа элементов, которые, будучи возбуждены, светятся. Экран отображения служит для отображения результатов решения задачи и конструктивно выполнен так же, как и экран 3 В качестве примера работы устройства взято множество из пяти точек А, Б, В, Г -л Л (фиг. 2). Работа устройства начинается с подачи первичной информации на вход первичпой информации блока 11 вручную опера-5 тором или автоматически по внешнему для устройства каналу связи. С двух выходов первичной информации поступают сигналы на соответствующие горизонтальные и вертикальные шины матрицы экрана ввода, на ко-ю тором появляется заданное множество объектов в виде светящихся точек (возможна конструкция с непосредственным нанесением информации о взаиморасположении точек оператором на экран при помощи «светового15 карандаша). Одновременно с информационного выхода блока 11 на информационный вход блока 10 подаются импульсы, количество которых равно количеству точек на экране ввода, и это кол 1чество запоминается. Если20 точек больше трех, то, согласно заложенной программе, с помощью трубки 2 проводится осмотр экрана ввода (поля) сканирующим пятном. В процессе сканирования пятно нериодически начинает движение из точек, на-25 званных центрами (на фиг. 2 точки А, В и Г, а также точка левого нижнего угла экрана). Сканирование нроисходнт вдоль лучевых прямых (лучей) в направлениях, показанных на фиг. 2 стрелками. Каждый последующийзо по порядку сканирования луч получается поворотом предыдущего луча на некоторый угол в одну и ту же сторону в течение всего процесса. В качестве начального центра берется какая-нибудь граничная точка поля или35 объект заданного множества (светящаяся точка), если объект расположен на границе поля. Поворот луча, т. е. изменение направления движения сканирования, осуществляется за счет того, что на одну из систем раз-40 вертки трубки 2 подается пилообразное нернодическое напряжение с периодом to с переменным наклоном пилы от периода к периоду, но с постоянным наклоном пилы внутри каждого периода, а на другую систему45 развертки в это же время - пилообразное периодическое напряжение с периодом о при постоянпом наклоне пилы от периода к периоду. Величина периода о выбирается из условий динамичности контролируемой си-50 стемы точек, а скорость изменения наклона меняющейся пилы - из условий точности или разрешающей способности устройства. Направление поворота может быть любым; в данном случае выбрано против часовой55 стрелки, а в качестве исходного центра взят левый нижний угол поля (фнг. 2). Построение первого выпуклого многоугольника начинается с того, что синхронизирующие иМпульсы с выхода генератора 9 пода-60 ются с периодом to на входы генераторов 7 и 4 ка 10 и одновременно через блок 6 соответственно на генераторные входы сумматоров 4 и 5. Выходные напряжения сумматоров 4 и 5 поступают соответственно в системы вертикальной и горизонтальной разверток и одновременно на оба координатных входа блока 10, но не проходят в него. Эти напряжения пропорциональны координатам соответственно Y и X сканирующего пятна трубки 2 в декартовой системе координат. При движеннн вдоль луча с углом ai (фиг. 2) в момент времени ti сканирующее пятно проходит через точку Л и на выходе трубки 2 возникает импульс, поступающий на вход обнаружения блока 10, в результате чего мгновенные значения напряжений сумматоров 4 и 5 проходят в блок 10 и запоминаются (эти напряжения пропорциональны соответственно координатам Y и X). Одновременно величнны напряжения сумматоров 4 н 5 через блок 10 проходят в блок // на вход вторичной информации, преобразовываются в цифровую форму н с выхода вторичной ннформадии попадают в блок /, где на экране отображения появляются светящиеся точки с координатами, соответствующими координатам точки А. Сканирующее пятно продолжает при этом двигаться ло лучу с углом ai до конца данного периода to. В момент времени 2, соответствующий концу данного н началу следующего периода U, запомненные величины из блока 10 подаются на координатные входы сумматоров 4 н 5, в результате чего дентр лучей из исходного положения - левого нижнего угла - перемещается в точку А. В процессе сканирования в конце периода to, во время которого угол поворота луча достигает а 45°, величина напряжения генератора 7 достигает предельного значения, равного по абсолютной величине напряжению генератора S в конце каждого периода to. Так как оба напряжения поступают в блок 10, то, в соответствии с программой, в этот момент из блока 10 подается управляющий импульс на управляющие входы блока 6 и генератора 7. Блок 6 переключает выход генератора 7 с генераторного входа сумматора 4 на выход генератора 8, а выход генератора 8 переключается с генераторного входа сумматора 5 на генераторный вход сумматора 4. Генератор 7 по этому сигналу начинает уменьшать наклон пилы по линейному закону, При движении вдоль луча с углом в момент времени t сканирующее пятно проходит через точку Б, возникает импульс на трубке 2 и координаты точки Б записываются в блоке 10, а сканирующее пятно движется далее по этому же лучу. В момент времени оно проходит через точку В и возникающий импульс на трубке 2 записывает координаты точки В в блок 10, а луч продолжает движеяия: в момент времени t на координатные входы сумматоров 4 и 5 из блока 10 подаются запомненные величины напряжений и центр лучей переносится в точку В. На экране отображения возбуждается ячейка, соответствующая точке В в системе декартовых координат. Однако блок 10 не только пропускает сигналы, возбуждающие ячейку, соответствующую точке В, но и добавляет сигналы, по которым возбуждаются ячейки экрана отображения вдоль отрезка, соединяющего ячейки, соответствующие точкам Л и Б. При движении сканирующего пятна вдоль луча с углом ai+tta+aa сканирующее пятно проходит через точку Г, информация о которой обрабатывается так же, как и для точек А и В, и принимаются аналогичные решения, в результате чего на экране отображения появляется светящийся отрезок, соответствующий отрезку между точками S и Г, а центр лучей перемещается в точку Г.

Далее лри сканировании из центра в точке Г вдоль луча с углом а1-}-а, сканирующее пятно вторично проходит через точку А, на экране отображения появляется светящийся отрезок, соответствующий отрезку между точками Г и Л, и на этом цикл построения первого выпуклого многоугольника заканчивается. Так как координаты точек Л уже имелись в блоке 10, то на командные входы генераторов 7 и S с командного выхода блока 10 поступают импульсы, в результате чего напряжения генераторов 7 и S становятся равными нулю. Одновременно из блока 10 перестают подаваться напряжения на координатные входы сумматоров 4 и 5. Поэтому сканирующее пятно оказывается снова в исходном положении - левом нижнем углу.

После окончания первого цикла построения первого выпуклого многоугольника, если не все точки заданного множества зафиксированы на экране отображения, начинается второй цикл построения второго многоугольника. В блоке 10 заложена жесткая программа изменения за цикл напряжений генераторов 7, 8 и 9 и момента появления импульсов на блоке 6 и генераторе 8, поэтому построение второго выпуклого многоугольника (т. е. запоминание, обработка и отображение информации) такое же, как и первого. Однако при сканировании поля, хотя по мере прохождения сканирующего пятна через точки, являющиеся вершинами первого многоугольника, в блок 10 поступают сигналы трубки 2, устройство на эти сигналы не реагирует, поскольку координаты этих точек уже запомнены в блоке 10. На экране отображения блока / второй выпуклый многоугольник после его построения будет находиться внутри первого. Таким образом, циклов будет столько, сколько окажется выпуклых многоугольников (ВМ). При этом общим правилом для всех циклов является то, что при прохождении сканирующего пятна во второй раз за цикл через какую-то вершину строящегося ВМ из

блока 10 подается сигнал на командные входы генераторов 7 и 8 для прекращения данного и начала нового циклов. С выполнением последующих циклов устройство уже не будет реагировать на прохождение пятна через все, ранее просканированные во вре.мя других циклов точечные объекты, координаты которых уже запомнены в блоке 10. Процесс построения и отображения ВМ продолжается

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

ВМ, внутри второго ВМ - третий ВМ и т. д.

В данном примере для множества на

фиг. 2 выполняются два цикла. При первом

цикле выделен и построен ВМ с верщинами

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

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

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

Вычислительное устройство для решения

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

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

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

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

соответствующему входу экрана отображения блока ввода и отображения, каждый из входов экрана ввода которого соединен с соответствующим выходом первичной информации блока преобразования информации, информационный выход которого подключен к информационному входу блока программы и памяти, вход обнаружения которого соединен с ВЫХОДОМ передающей трубки.