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

 

ОП КСАН ИЕ

ИЗОБРЕТЕ Н ИЯ

385279

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

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

Рестту блик

ASTON CNOMY СВИДЕТЕЛЬСТВУ

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

Заявлено 20.Ч11.1971 (№ 1688395/18-24) с присоединением заявки №вЂ”

Приоритет—

Опубликовано 29.Ч.1973. Бюллетень № 25

Дата опубликования описания 24Х1.1974

М. Кл. G 06f 15/32

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

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

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

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

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

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИММЕТРИЧНОЙ ЗАДАЧИ

О КОММИВОЯЖЕРЕ

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

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

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

Это позволяет повысить точность .и оыстродействие работы устройства.

Функциональная блок-схема устройства представлена на чертеже..Предложенное устройство состоит из блока, контролируемого поля I, передающей телевизионной трубки 2 с накоплением, оптической системы 8, сумматоров 4 и 5 соответственно вертикальной,и горизонтальной резверток, блока б переключения, генераторов 7,и 8 пилообразных напряжений соответственно с переменным .и постоянным наклонами пил, генератора 9 тактовых,импульсов, блока 10 программы и памяти, осветителя И с,импульсной лампой-вспышкой, полупрозрачного зеркала 12, интегратора 18 зарядов, ди фференцирующего порогового элемента 14.

Передающая трубка 2 имеет два входа, ведущих соответственно к системам горизонтальной,и вертикальной разверток, и выход, ведущий к,регистрационному входу интегратора 13. Сумматор 4(5) имеет: генераторный вход, соединенный с соответствующим из двух

385279 выходов блока б, координатный вход, соединенный с соответствующим;из двух координатных выходов блока 10; выход сумматора 4(5) соединен с системой вертикальной (горизонтальной) развертки трубки 2. Блок б переключения имеет два сигнальных входа, один из которых соединен с выходом генератора 7 .и с одним из двух генераторных входов блока

10, другой сигнальный вход сседикен с выходс.,t генератора 8,и с другим генераторныч входом блока 10; управляющий вход блока 6 соединен с управляющим входом генератора

7 и с соответствующим из двух управляющих выходов блока 10. Генераторы 7 и 8 имеют каждый по сигнальному входу, соединенному с выходом генератора 9, и по упразляюще.;у входу, каждый;из которых соединен с соответствующим,из двух управляющих выходов блока 10; командный вход блока 7 соединен с командным выходом блока 10. Командный выход генератора 9 соединен с генераторным выходом блока 10. Регистрационный выход блока 10 соединяется с внешней,для устройства а ппаратурой. Осветитель 11 имсет вход, соединенный с сигнальным выходом блока 10; световой поток направлен на первую плоскость зеркала 12, На вторую плоскость зер: ала 12 световой поток поступает с блока контролируемого поля 1 через оптическую систему 8..Вход сброса интегратора 18 .соединен с выходом сброса блока 10; регистрациочный выход соединен с регистрационным входом блока 10,и выход обнаружения соединен со в одом ди фференцирующего элемента 14. Выход элемента 14 соединен со входом обнаружения блока 10.

Устройство .работает следующим ооразом.

Изображение поля проектируется через оптическую систему 8 и полупрозрачное зеркало

12 на фоточувствительную IICBppxHOcTb трубки 2, после чего поле разворачивается посредством логической развертки .электронным пучком с целью выделения выпуклых многоугольников, вершинами которых являются точечные объекты. Каждый,из последующих по порядку выделения выпуклых многоугольников находится целиком внутри предыдущего. Б процессе выделения выпуклых многоугольников определяются декартовые координаты вершин многоугольников и за поминаются в блоке 10.

После выделения,выну)клых многоугольников осветитель 11 дает .мощеную кратковременную .засветку экрана трубки 2 и заряжает мозаику,до полного верхнего уровня. Затем мгновенным переносом электронного пучка последовательно в кажд ый из точечных объектов «высвечиваются» точечные области, а суммировавший заряд с этих ооластей;интегратор 18 разряжается по команде .из блока 10 (по входу сброса).

После этого поочередно, начиная из центра, совмещенного с точечным объектом с наи меньшей координатой; Х, за тем из объекта с наименьшей после предыдущей координатой

l0

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

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

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

С выходов сумматоров 4 .и 5 напряжения поступают в отклоняющие системы трубки. Наклон пилы генератора 7 внутри данного периода постоянен, но для каждого периода различен.

Поворот лучевых отрезков осуществляется за счет, изменения полярности пил генераторов 7 и 8, изменения наклона пилы генератора 7, а также за счет подключения каждого из этих генераторов с .помощью блока 6 и сумчатора 4 .или 5. Команды для указанных действий подаются с управляющих выходов блока 10 на управляющие входы блока 6 и генераторов 7,и 8.

При движении электронного п уч <а мозаичные зерна фоточувствительной поверхности труоки разряжаются .и заряд суммируется (интегрируется),интегратором 18. Пороговый элемент 14 оценивает значение производной зо времени от функции накаплизаемого интегратором 18 заряда. После завершения движения электронного пучка по лучевому отрезку интегратор 18 разряжается по,команде сброса .из блока 10. При выделении выпуклых многоугольников .начальный центр располагается на границе .поля, где координаты центра из вестны; чаще всего в качестве начального центра берут начало 0 координат. Для .выбранного начала координат поля на чертеже поворот лучевых отрезков будет осуществляться против часовой стрелки от оси Х.

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

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

4 и 5, пропорциональные декартовым коэрд".натам Х и Y найденного -.î÷å÷íîãî объекта.

Тем времнем электронный пучок, не останав, иваясь, дойдет до KQIHIIa данного лучевого отрезка. При этом электронный пучок может проходить через какие- Tole ные oo", екты, координаты которых также ф:Iêсируются в блоке 10. Каждому,из объектами присваивается порядковый номер. В моме IT окончания данного периода .на координатно;е входы сумматоро в 4,и 5 с коордHHBTHHIx. выходов блока 10 поступят напряжения, оответствующие координатам последнего IIo сче ту объекта, .и со следующего периода центр переместится в этот последний IIID счету гочечный объект.

Сканирование,из второго центра будет продолжаться при последовательном повороте лучевых отрезко в в ту же сторон у, пока элект.ронный пучок не пройдет вновь по лучевому отрезку, пересекающему один и".,è несколь о точечных объектов, координаты которых присвоенн|ые .им номера таиже фиксируются в блоке 10. Центр вновь совмещается с последним по счету объектом и т..д. В итоге лучевой отрезок повернется на угол 180 — 360, и будет выделен лервый по счету выпуклый многоугольник. Аналогично выделяется и вто,рой по счету выпуклый многоугольник, внутренний для .первого выпуклого многоуго;IbHèка, третий выпуклый многоугольник и т. д.

В результате в:блоке 10 окажутся запомнен;ными координагы,и номера всех точечных объектов, а все множество объектов будет разбито на выпуклые многоугольники.

После завер шения указанных действий по команде на вход осветителя 11 с сигнального выхода блока 10 фоточувствительная поверхность трубки 2 засвечивается мощным кратковременным световым .импульсом, и .оза .ка заряжается до верхнего уровня. По известным координатам точечных объектов электронный пучок производит «высвечивание» (разряжение) точечных областей. Это осуществляется подачей соответствующих IICOTQHHHbIx напряжений на координатные входы сумматоров 4 и 5. Анодное напряжение, с целью сохранности потенциального рельефа изображения поля, подается,поз же, а снимается раньше включения и выключения тока в катушках отклоняющих систем.

После .высвечивания всех точечных объектов суммарный .заряд, наиалливающийся в интеграторе 18, разряжается командой по входу сброса. Затем электронный паучок перемещается по команде на координатные в оды сумматоров 4 и 5 из блока 10 в объект, координата Х которого .наименьшая, н начнется дет произведено и — 1 (n — число объектов), З0 . после чего в блоке 10 окажется заполненной вся матрица расстояний. Окончательное решение задачи о коммивояжере будет найдено.

60 сканирование, как и при выделении выпуклого многоугольника, но первый и последний лучевые отрезки параллельны оси Х,и направлены в разные стороны. При прохождении электронньгм пучком вдоль лучевого отрезка со скоростью, обеспечивающей полный разряд мозаичных зерен экрана трубки 2, заряд интегратора 18 растет пропорционально пройденному от центра расстоянию (т. е. интегратор 18,интегрирует заряд по длине).

Производная функции заряда постоянна в

«своем» периоде,и положительна по знаку.

При прохождении электронн ым пучком через объект значение производной велико по у ровню,и знак ее отр и цателен. В этот момент элемент 14 выдает .разрешение на запись уровня заряда интегратора 18 по регистрационному входу блока 10, который пропорционален рас стоянию между объектом — центром и пройденным объектом. После поворота лучевого отрезка .на 180 первый цикл измерения расстояний завершается. Экран вновь засвечивается до верхнего уровня заряда мозаики; вновь высвечиваются точечные области, кроме объекта .с наименьшей координатой Х. Центр переносится в объект с новой .наименьшей координатой Х, и все повторяется как в предыд ущем цикле, измерений. Таких циклов бу.Предмет .изобретения

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

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

385279

Составитель И. Горелова

Техред Е. Борисова

Редактор Т. Орловская

Корректор Г. Филатова

Тип. Харьк. фил. пред. «Патент»

Заказ 638 Изд. М 647 Тираж 635 Подписное

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

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