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

 

33I406

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Сова Советскив

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

Республик

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

Заявлено 12Х.1970 (Ж 1436277/18-24) с присоединением заявки №

Приоритет

Опубликовано 07.111.1972. Бюллетень ¹ 9

Дата опубликования описания 21.IV.1972

М. Кл. б 06g 7/48

Комитет по делам изобретений и открытиЯ при Совете Министров

СССР

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

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

Институт проблем управления (автоматики и телемеханики) Заявитель

ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

СИММЕТРИЧНОЙ ЗАДАЧИ О КОММИВОЯЖЕРЕ

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

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

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

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

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

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

Устройство состоит из следующих блоков:

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

20 информации.

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

25 матричную панель, состоящую из большого числа элементов, которые, будучи возбуждены, светятся. Экран отображения служит для отображения результатов решения задачи и конструктивно выполнен так же, как и экран

30 ввода.

331406

В качестве примера работы устройства взято множество из пяти точек А, Б, В, Г и

Д (фиг. 2). Работа устройства начинается с подачи первичной информации на вход первичной информации блока 11 вручную оператором или автоматически по внешпему для устройства каналу связи. С двух выходов первичной информации поступают сигналы на соответствующие горизонтальные и вертикальные шHHbl матрицы экрана ввода, на котором появляется заданное множество объектов в виде светящихся точек (возможна конструкция с непосредственным нанесением информации о взаиморасположении точек оператором на экран при помощи «светового карандаша»). Од овремепно с информационного выхода блока 11 на информационный вход блока 10 подаются импульсы, количество которых равно количеству точек на экране ввода, и это количество запоминается. Если точек больше трех, то, согласно заложенной программе, с помощью трубки 2 проводится осмотр экрана ввода (поля) сканирующим пятном. В процессе сканирования пятно периодически начинает движение из точек, названных центрами (на фиг. 2 точки А, В и Г, а также точка левого нижнего угла экрана).

Сканирование происходит вдоль лучевых прямых (лучей) в направлениях, показанных

»а фиг. 2 стрелками. Каждый последующий по порядку сканирования луч получается поворотом предыдущего луча на некоторый угол в одну и ту же сторону в течение всего процесса. В качестве начального центра оерется какая-нибудь граничная точка поля или об ьект заданного множества (светящаяся точка), если объект расположен на границе поля. Поворот луча, т. е. изменение направления движения сканирования, осуществляется за счет того, что на одну из систем развертки трубки 2 подается пилообразное периодическое напряжение с периодом 4 с переменным наклоном пилы от периода к периоду, по с постоянным наклоном пилы внутри каждого периода, а на другую систему развертки в это же время — пилообразное периодическое напряжение с периодом to npu постоянном наклоне пилы от периода к периоду. Величина периода to выбирается из условий динамичности контролируемой системы точек, а скорость изменения наклона меняющейся пилы — из условий точности или разрешающей способности устройства. Направление поворота может быть любым; в данном случае выорано против часовой стрелки, а в качестве исходного центра взят левый нижний угол поля (фиг. 2).

Построение первого выпуклого многоугольника начинается с того, что синхронизирующие импульсы с выхода генератора 9 подаются с периодом 4 на входы генераторов 7 и

8 и запускают их. Выходные напряжения этих блоков изменяются в соответствии с заданной программой. Эти напряжения подаются непосредственно на координатные входы бло5

20 гз

65 ка 10 и одновременно через блок б соответственно на генераторные входы сумматоров 4 и 5. Выходные напряжения сумматоров 4 и

5 поступают соответственно в системы вертикальной и горизонтальной разверток и одновременно на оба координатных входа блока 10, но не проходят в него, Эти напряжения пропорциональны координатам соответственно Y и Х сканирующего пятна трубки 2 в декартовой системе координат. При движении вдоль луча с углом а> (фиг. 2) в момент времени tl сканирующее пятно проходит через точку А и на выходе трубки 2 возникает импульс, поступающий на вход обнаружения блока 10, в результате чего мгновенные значения напряжений сумматоров 4 и 5 проходят в блок 10 и запоминаются (эти напряжения пропорциональны соответственно координатам Y и Х). Одновременно величины напряжения сумматоров 4 и 5 через блок 10 проходят в блок 11 на вход вторичной информации, преобразовываются в цифровую форму и с выхода вторичной информации попадают в блок 1, где на экране отображения появляются светящиеся точки с координатами, соответствующими координатам точки А. Сканирующее пятно продолжает при этом двигаться по лучу с углом а> до конца данного периода to. В момент времени 4, соответствующий концу данного и началу следующего периода 4, запомненные величины из блока 10 подаются на координатные входы сумматоров 4 и 5, в результате чего центр лучей из исходного положения — левого нижнего угла — перемещается в точку А. В процессе сканирования в конце периода 4, во время которого угол поворота луча достигает а=45, величина напряжения генератора 7 достигает предельного значения, равного по абсолютной величине напряжению генератора 8 в конце каждого периода to. Так как оба напряжения поступают в блок 10, то, в

COOTBeTCTBHH C IlPOl PBMMOH, B 3TOT NOMeHT H3 блока 10 подается управляющий импульс на управляющие входы блока б и генератора 7.

Блок б переключает выход генератора 7 с генераторного входа сумматора 4 на выход генератора 8, а выход генератора 8 переключается с генераторного входа сумматора 5 на генераторный вход сумматора 4. Генератор 7 по этому сигналу начинает уменьшать наклон пилы по линейному закону.

При движении вдоль луча с углом а +а в момент времени t, сканирующее пятно проходит через точку Б, возникает импульс на трубке 2 и координаты точки Б записываются в блоке 10, а сканирующее пятно движется далее по этому же лучу. В момент времени t4 оно проходит через точку В и возникающий импульс на трубке 2 записывает координаты точки B в блок 10, а луч продолжает движение вдоль луча с углом а +а до границы поля. При этом вся информация о точке В обрабатывается так же, как и информация о точке А, и принимаются аналогичные реше331406

5 яия: в момент времени t4 на координатные входы сумматоров 4 и 5 из блока 10 подаются запомненные величины напряжений и центр лучей переносится в точку В. На экране отображения возбуждается ячейка, соответствующая точке В в системе декартовых координат. Однако блок 10 не только пропускает сигналы, возбуждающие ячейку, соответствующую точке В, но и добавляет сигналы, по которым возбуждаются ячейки экрана отображения вдоль отрезка, соединяющего ячейки, соответствующие точкам А и В. При движении сканирующего пятна вдоль луча с углом а +а +аз сканирующее пятно проходит через точку Г, информация о которой обрабатывается так же, как и для точек А и В, и принимаются аналогичные решения, в результате чего на экране отображения появляется светящийся отрезок, соответствующий отрезку между точками В и Г, а центр лучей перемещается в точку Г.

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

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

as

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

ВМ: внутри первого ВМ находится второй

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

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

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

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

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

Фиг. 1

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

Текред 3. Тараненко

Редактор И. Грузова

Корректоры: Е. Давыдкина и A. Николаева

Заказ 903/12 Изд. № 388 Тираж 448 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Ж-35, Раушская наб., д, 4/5

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

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

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