Устройство для решения симметричной задачи о коммивояжере

О П И С А Н И Е 385279ИЗОБРЕТЕ Н ИЯН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистицеских РесттубликЗависимое от авт. свидетельства-11,1971 ( 1688395/18 Кл. 6 061 15,3 явлен присоединением заявки-асударатвенныи комите Совета Министров ССС по делам изобретенийи открытий ритет Опубликовано 29,Ч.1973, Б Дата опубликования описа УДК 681,325.етень24 Х 1.197 Авторизобретения В. А, Леонтье Ордена Ленина институт проблем управлеиивител Й ЗАДАЧИ РЕШЕНИЯ СИММЕТРО КОММИВОЯЖЕРЕ СТРОЙСТВ анныи с выходнон изионной трубки и ка программы и папороговый элемент, егратором зарядов, ограммы и памяти. ов, свя й телев дом бло ирующий ом с,ин локом пр интегратор заряд шиной передающе со входом и выхо ,мяти; ди,ффе;ренц соединенный вход а выходом - с б ность и оыстроИзобретение относится к вычислительной технике. Оно предназначено для ускоренного ,решения задачи о коммивояжере с симметричной матрицей расстояний большой размерности и служит для автоматического ввода ,исходных данных в блок памяти. К задаче о коммивояжере сводится значительное количество экономических и технических проблем.В настоящее время, известно устройство для решения задачи о коммивояжере, содержащее блок контролируемого поля, генератор пилообразных напряжений, блок переключения, связанный с первыми входами сумматоровблок программы и памяти, подключенный к вторым входам сумматоров, генератор тактовых импульсов, связанный по выходу с генераторами пилообразных напряжений, которые подключены к входам;и выходам блока программы и памяти.Известное устройство имеет низкое быст родействие, не обеспечивает точного решения задач,и.Предложенное устройство отличается тем, что оно содержит последовательно расположенные за блоком контролируемого поля оптическую систему; полупрозрачное зЕркало; передающую телевизионную труоку с накоплением, входные шины развертки которой подключены к выходам сумматоров; осветитель, подключенный к блоку программы и памяти; Это позволяет повысить точдействие работы устройства.Функциональная блок-схема устройства представлена на чертеже, Предложенное устройство состоит из блока, контролируемого поля 1, передающей телевизионной трубки 2 с накоплением, оптической системы 3, сумматоров 4 и 5 соответственно вертикальной,и горизонтальной резверток, блока б переключения, генераторов 7,и 8 пилообразных напряжений соответственно с переменным и постоянным наклонами пил, генератора 9 тактовых,импульсов, блока 10 программы и памяти, осветителя И с,импульсной лампой-вспышкой, полупрозрачного зеркала 12, интегратора 13 зарядов, дифференцирующего порогового элемента 14,Передающая трубка 2 имеет два входа, ведущих соответственно к системам горизонтальной,и вертикальной разверток, и выход, ведущий к,регистрационному входу интегратора 13. Сумматор 4(5) имеет: генераторный вход, соединенный с соответствующим из двухвыходов блока б, координатный вход, соединенный с соответствующим .из двух координатных выходов блока 10; выход сумматора 4(5) сселинен с системой вертикальной (горизонтальной) развертки трубки 2. Блок б переключения имеет два сигнальных входа, один из которых соединен с выходом генератора 7 и с одним из двух генераторных входов блока 10, другой сигнальный вход сседикен с выходом генератора 8,и с другим генераторным входом блока 10; управляющий вход блока 6 соединен с управляющим входом генератора 7 и с соответствующим из двух управляющих выходов блока 10, Генераторы 7 и 8 имеют каждый по сигнальному входу, соединенному с выходом генератора 9, и по управляющему входу, каждый;из которых соединен с соответствующим,из двух управляющих выходов блока 10; командный вход блока 7 соединен с командным выходом блока 10. Командный выход генератора 9 соединен с генераторным выходом блока 10. Регистрационный выход блока 10 соединяется с внешней,для устройства аппаратурой. Осветитель 11 имсет зхол, соединенный с сигнальным выходом блока 10; световой поток направлен на первую плоскость зеркала 12, На вторую плоскость зеркала 12 световой поток поступает с блока контролируемого поля 1 через оптическую систему 3. Вход сброса интегратора 18 соединен с выходом сброса блока 10; регистрациочный выход соединен с регистрационным входом блока 10,и выход обнаружения соединен со входом дифференцирующего элемента 14. Выход элемента 14 соединен со входом обнаружения блока 10.Устройство работает следующим ооразом. Изображение поля проектируется через оптическую систему 3 и полупрозрачное зеркало 12 на фоточувствительную поверхность трубки 2, после чего поле разворачивается посредством логической развертки электроминным пучком с целью выделения выпуклых многоугольников, вершинами которых являются точечные объекты. Каждый из последующих по порялку выделения выпуклых многоугольников находится целиком внутри предыдущего. Б процессе выделения выпуклых многоугольников определяются декартовые координаты вершин многоугольников и запоминаются в блоке 10.После выделения, выпуклых многсугсльников осветитель 11 дает иощную кратковременную засветку экрана трубки 2 и заряжает мозаику,до полного верхнего уровня, Затем мгновенным переносом элект. ронного пучка последовательно в каждый из точечных объектов высвечиваются точечные области, а суммировавший заряд с этих ооластей;интегратор 13 разряжается по команде из блока 10 (по входу сброса).После этого поочередно, начиная из центра, совмещенного с точечным объектом с наи 1 меньшей координатой, Х, затем из объекта с наименьшей после предыдущей координатой 5 10 5 20 25 30 35 40 45 50 55 60 65 Х и т. д, сканируют изображение поля, вдоль лучевых отрезков прямых в той же последовательности, как и при выделении выпуклых многоугольников, с поворотом лучевых отрезков в ту же сторону, но на 180 вместо 360. По завершении этаких операций в блоке 10 фиксируется полная матрица расстояний между точечными объектами. После выделения всех выпуклых многоугольников,и определения полной матрицы расстояний многоугольники последовательно объединяются с минимизацией длин получаемых фигур на каждом этапе объединения. В,итоге получают гамильтонов цикл, являющийся приближенным решением задачи о коммивояжере.При сианировании электронный пучок движется вдоль лучевых отрезков прямых линий в течение тактового периода 1. Каждый по. следующий лучевой отрезок получают поворотом предыдущего на определенный по знаку и величине угол. При этом через время 1 гекератор тактовых, импульсов выдает импульс на входы генераторов 7,и 8, которые по этой команде вырабатывают пилообразные напряжения, поступающие через блок б переключения на генераторные входы сумматоров 45. С выходов сумматоров 4 и 5 напряжения поступают в отклоняющие системы трубки, Наклон пилы генератора 7 внутри данного периода постоянен, но для каждого периода различен.Поворот лучевых отрезков осуществляется за счет, изменения полярности пил генераторов 7 и 8, изменения наклона пилы генератора 7, а также за счет подключения каждого из этих генераторов с,помощью блока 6 и сумматора 4 или 5, Команды лля указанных действий подаются с управляющих выходов блока 10 на управляющие входы блока 6 и генераторов 7,и 8.При движении электронного паучка мозаичные зерна фоточувствительной поверхности труоки разряжаются и заряд суммируется (интегрируется),интегратором 13. Пороговый элемент 14 оценивает значение производной зо времени от функции накаплизаемого интегратором 13 заряда. После завершен,ия движения электронного пучка по лучевому отрезку интегратор 18 разряжается по,команле сброса .из блока 10.При выделении выпуклых многоугольников начальный центр располагается на границе поля, где координаты центра известны; чаще всего в качестве начального центра берут начало 0 координат. Для выбранного начала координат поля на чертеже поворот лучевых отрезков будет осуществляться против часовой стрелки от оси Х.Сканирование из,начального центра,продолжается до тех пор, пока электронный пучок не пройдет через какой-то из точечных объектов, яркость которого во много раз выше яркости фона между объектамп. В этот момент значение производной функции заряда интегратора 13 превысит положительный5 1 О 15 2 О 25 40 45 50 55 60 пороговый уровень и элемент 14 выдает импульс на вход обнаружения блока 10, в котором по этой, команде запишутся мгновенные значения выходных напряжений сумматоров 4 и 5, пропорциональные декартовым координатам Х и У найденного точечного объекта.Тем времнем электронный пучок, не останав,.иваясь, дойдет до конца данного лучевого отрезка. При этом электронный пучок может проходить через какие-то другие точеч. ные об",.екты, координаты которых также фиксируются в блоке 10. Каждому,из объектами присваивается порядковый номер. В моме т окончания данного периода .на координатные входы сумматоров 4,и 5 с координатных выходов блока 10 поступят напряжения, .оответствующие координатам последнего по сче ту объектаи со следующего периода центр переместится в этот последний по счету гочечный объект.Сканирование,из второго центра будет продолжаться при последовательном повороте лучевых отрезков в ту же сторону, пока эле. т.ронный пучок не пройдет вновь по лучевому отрезку, пересекающему один или несколько точечных объектов, координаты которых присвоенные им номера таиже фиксируются в блоке 10, Центр вновь совмещается с последним по счету объектом и т, д, В итоге лучевой отрезок повернется на утол 180 - 360, и будет выделен лервый по счету выпуклый многоугольник. Аналогично выделяется и вто,рой по счету выпуклый многоугольник, внутренний для первого выпуклого многоугольника, третий выпуклый многоугольник и т. д. В результате в блоке 10 окажутся запомнен,ными координагы,и номера всех точечных объектов, а все множество объектов будет разбито на выпуклые многоугольники,После завершения указанных действий по команде на вход осветителя 11 с сигнального выхода блока 10 фоточувствительная поверхность трубки 2 засвечивается мощным кратковременным световым .импульсом, и моза:;.ка заряжается до верхнего уровня. По известным координатам точечных объектов электронный пучок производит высвечивание (разряжение) точечных областей. Это осуществляется подачей соответствующих постоянных напряжений на координатные входы сумматоров 4 и 5, Анодное напряжение, с целью сохранности потенциального рельефа изображения поля, подается,позже, а снимается раньше включения и выключения тока в катушках отклоняющих систем.После высвечивания всех точечных объектов суммарный заряд, наиалливающийся в интеграторе 13, разряжается командой по входу сброса. Затем электронный паучок перемещается по команде на координатные входы сумматоров 4 и 5 из блока 10 в объект, координата Х которого, наименьшая, н начнется сканирование, как и при выделении выпуклого многоугольника, но первый и последний лучевые отрезки параллельны оси Х,и направленцы в разные стороны. При прохождении электронньгм пучком вдоль лучевого отрезка со скоростью, обеспечивающей полный разряд мозаичных зерен экрана трубки 2, заряд интегратора 13 растет пропорционально пройденному от центра расстоянию (т. е. интегратор 13,интегрирует заряд по длине). Производная функции заряда постоянна в своем периоде,и положительна по знаку. При прохождении электронным пучком через объект значение производной велико по уровню,и знак ее отрицателен. В этот момент элемент 14 выдает, разрешение на запись уровня заряда ингепрагора 13 по регистрационному входу блока 10, который пропорционален расстоянию между объектом - центром и пройденнь м объектом. После поворота лучевого отрезка,на 180 первый цикл измерения расстояний завершается, Экран вновь засвечивается до верхнего уровня заряда мозаики; вновь высвечиваются точечные области, кроме объекта с наименьшей координатой Х. Центр переносится в объект с новой наименьшей координатой Х, и все повторяется как в предыд)ущем цикле, измерений. Таких циклов будет произведено и - 1 (и - число объектов), после чего в блоке 10 окажется заполненной вся матрица расстояний. Окончательное решение задачи о коммивояжере будет найдено. Предмет изобретения Устройство для решения симметричной задачи о коммивояжере, содержащее блок контролируемого поля, генератор пилообразных напряжений, блок, переключения, связанный с 1 первыми входами сумматоров, блок программы :и памяти, подключенный к вторым входам сумматоров, генератор тактовых импульсов, связанный по выходу с генераторами пилообразных напряжений, которые подключены к входам,и выходам блока программы и памяти, отличающееся тем, что, с целью повышения точности и быстродействия устройства, оно содержит последовательно расположенные за блоком контролируемого поля оптическую систему, полупрозрачное зеркало,и передающую телевизионную трубку с накоплением, входные шины развертки которой подключены к выходам сумматоров, осветитель, подключенный к блоку программы и памятиинтегратор зарядов, связанный с выходной шиной передающей телевизионной трубки,с,накоплением,и со входом и выходом блока программы ,и памяти, дифференцирующий пороговый элемент, соединенный входом с интегратором зарядов, а выходом с блоком программы и памяти.385279 Составитель И. Горелова Техред Е. Борисова Редактор Т. Орловская Корректор Г. филатова Тип, Харьк, фил, пред. Патент Заказ 638 Изд. М 647 Тираж 635 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5