УСТРОЙСТВО для РЕШЕНИЯ СИММЕТРИЧНОЙ ЗАДАЧИ О КОММИВОЯЖЕРЕ Советский патент 1973 года по МПК G06T7/20 

1

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

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

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

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

интегратор зарядов, связанный с выходной ШИНОЙ передающей телевизионной трубки и со входом и выходом -блока программы и па:мяти; дифф-ефенцирующий пороговый элемент, соединенный входом с интегратором зарядов, а выходом - с блоком программы и памяти.

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

Функциоиальная блок-схема устройства представлена на чертеже. .Предложенное устройство состоит из блока .контролируемого поля У, передающей телевизионной трубки 2 с накоплением, Оптической системы 3, сумматоров 4 и 5 соответствен.но ве|ртикальной и горизонтальной резвертОК, блока 6 переключения, генераторов 7 и 8 пилообразных напряжений соответственно с переменным и постоянным наклонами пил, генератора 9 тактовых ;импульсов, блока 10 программы и памяти, осветителя 111 с импульсной лампой-вспышкой, полупрозрачного зеркала 12, интегратора 13 зарядов, ди(фферевцирующего порогового элемента 14.

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

вход, соединенный с соответствующим из двух

выходов блока 6, координатный вход, соединен.кый с соответствующим аз двух координатных выходов блока 10; выход сумматора 4(5) соединен с системой вертикальной (горизонтальной) .развертки трубки 2. Блок 6 переключения имеет два сигнальных входа, один из которых соединен с выходом генератора 7 ,и с одним .из двух генераторных входов блока 10, другой сигнальный вход соединен с выходом генератора 8 я с другим генераторным входом блока 10; управляющ.ий вход блока 6 соединен с управляющим входом генератора 7нс соответствующим лз двух управляющих выходов блока 10. Генераторы 7 ,и 8 .имеют каждый по сигнальному входу, сое.дипен,ному с выходом генерато.ра 9, и по управляющему входу, каждый из которых соединен с соответствующим ИЗ двух управляющих выходов блока 10; .командный вход блока 7 соединен с командным выходом блока 10. Командный выход генератора 9 соединен с генерато.рным выходом .блока 10. Регистрационный выход блока 10 соединяется с внешлей для устройства аппаратурой. Осветитель J/ имеет вход, соединенный с сигнальным выходом блока 10; световой поток направлен -на первую плоскость зеркала 12. На вторую плоскость зеркала 12 световой поток поступает с бло«а контролируемого поля / через оптическую систему 3. .Вход сброса интегратора 13 соединен с ВЫХО.ДОМ сброса блока 10; регистрационный выход соединен с регистрационным входом блока 10 ,и выход обнаружения соединен со входом ди|ф|ференц.ирующего элемента 14. Выход элемента 14 соединен со входом обнаружения блока 10.

Устройство работает следующим образом. Изображение поля проектируется через оптяческую систе.му 3 и 1полу1проз|р.ачное зеркало 12 на фоточувствительную поверхность трубки 2, после чего поле разворачивается посредством логической развертки электронным пучком с целью выделения выпуклых многоугольников, верщи-нами которых являются точечные .объекты. Каждый из послед|ую.щих по порядку выделения выпуклых м.нотоугольни.ков находится целиком внутри преды.дущего. Е про.цессе выделения выпуклых многоугольников определяются декартовые координаты верщ.и.н многоугольников И эаломинаются в блоке 10.

После выделения выпу)кл.ых .мно гоу-гольников о.С:Ветитель И дает :мО|Щ|ную кратковременную засвет.К|у Э К|рана трубк.и 2 и заряжает мозаику до полного верхнего уров.ня. Затем мгновенным переносом электpOHHOiro пучка последовательно в каждый из точечных .объектов «высвечиваются точечные .области, а сум.мировавщ.ий заряд с этил областей интегратор 13 разряжается по команде из блока 10 (но .входу сброса).

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

X и т. д. сканируют изображение 1поля, вдоль лучевых отрезков прямых в той же последовательности, .как и при выделении выпуклых М 1огоу1гольников, с поворотом:-лучевых отрезков в ту же сторону, но на 180° вместо 360°. По з.а.вершении этмх олера.ций в блоке 10 фиксируется полная матрица расстояний между точечными объектами. После въ1деления всех -выпуклых .многоугольников и определения полной матрицы .расстояний многоугольники последовательно объединяются с м.инимиза.цией длин получаемых фигур на каждо.м этапе объединения. iB итоге получают га.м.ильтонов цикл, являющийся приближенным решением задачи о коммивояжере.

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

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

При движении электронного пучка мозаичные зерна фоточувствительной поверхности трубки разряжаются и заря.д суммируется (интегрируется) .интегратором 13. Пороговый элемент 14 оценивает значение ироизводной 30 времени от функции накапливаемого .интегратором 13 за.ряда. После заверщения движения электронного пучка по лучевому отрезку интегратор 13 ра.зрял ается по -команде сброса из блока 10.

При вы.делен.И-и выпукл.ых МНОгоугольников -начальный центр располагается на границе -полЯ, где коо.рд:инаты центра известны; чаще всего в качестве начального центра берут начало О коорд-инат. Для -выбран.ного начала коо.рдинат поля на чертеже поворот лучевых отрезков будет осуществляться п-ротив часовой стрелки от .оси X.

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

пороговый уровень и элемент 14 выдает импульс на .вход ойнаружевия блока 10, в котором по этой .команде запишутся мгновенные значения выходны-х напряжений сумматоров и 5, пропор|Ц,ио.нальные декартовым координатам J и У найденного точечного объекта.

Тем времнем электронный лучок, не останавливаясь, дойдет до Кавца даиного лучевого отрез ка. При этом электролный пучок может проходить i4epe3 ка-кие-то другие точечные обг.екты, координаты которых также ф:1ксируются в блоке 10. Каждому ,из объектов присваивается порядковый .номер. В моме IT окончания данного пер.иода .на координатные входы сумматоров 4 и 5 с коор.динатных выходов бл.ока 10 поступят напряжения, соответствующ,ие координатам последнего по сче ту .объекта, .и со следующего перио.да центр переместится в этот последний ino счету точечный объект.

Ска«нрован.ие из второго центра будет продолжаться пр.и последовате.льном повороте лучевых отрезков в ту же сторо.ну, пока электронный пучок не пройдет вновь по лучевому отрезку, пересекающему один или несколько точечных объектов, координаты которых ч Присвоенные .им HOMeipa так1же ф.иксируются Б блоке 10. Центр вновь совмещается с последн.им по счету объектом .и т. .д. В итоге лучевой отрезок повернется «а угол 180-360°, и будет въ1делен первый по счету выпуклый многоугольник. Аналогично выделяется и второй по счету выпуклый многоугольник, внутренний для .первого выпуклого много.угольн,ика, третий выпуклый многоугольник и т. д. В результате в Йлоке dO окажутся запомненными коордииагы и номера всех точечных объектов, а все множество объектов разбито на выпуклые многоугольники.

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

После .высвечивания всех точечных объектов сум,марны1Й за.ряд, 1наиа;плИВающийся в интеграторе 13, разряжается командой-по входу сброса. Затем электронный пучок перемещается по команде на .координатные входы сумматоров 4 И 5 «з блока 10 в объект, координата X кото.рого .на.именьщая, и начнется

сканирование, как и пр.и выделении выпуклого многоугольника, но первый и последний лучевые отрезки параллельны оси X и направлены iB разные стороны. Пр.и про хождеНИИ электронным пучком вдоль лучевого отрезка со скоростью, обеспечивающей полный разряд мозаичных зерен экрана трубки 2, заряд интегратора 13 растет пропорцио.нально пройденному от -центра расстоянию (т. е. интегратор 13 интегрирует заряд по длине). Про.изводная функции заряда постоянна в «своем периоде и полож.ительна оо знаку. При прохождении электронным пучком через объект з.начение про.изво.дной велико по уровню и знак ее отрицателен. В этот момент элемент 14 .выдает разрешение на запись уровня заряда интегратора 13 по регистрационному входу блока Ю, который пр.о,порционален расстоянию между объектом - центром .и пройденным объектом. После поворота лучевого отрезка .на 180° первый цикл измерения расстояний завершается. Экран вновь засвечивается до верхнего уровня заряда моза.ики; вновь высвечиваются точечные области, кроме

объекта с наименьшей .координатой X. Центр переносится в объект с новой .наименьшей координатой X, и все повторяется как в предыд)ущем цикле измерений. Таких циклов будет про.изведено п-1 (п-число объектов),

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

35

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

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

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

за блоком контролируемого .пол.я оптическую систему, полупрозрачное зе|ркало и передающую телеЕизион;ную труб.ку с накоплени.ем, входные ШИНЫ развертки которой подключены к въгходам сумматоров, осветитель, подключенный к блоку программы и памяти, интегратор зарядов, связанный с выходной щ.и.ной передающей телвв.изио,н.ной трубки с .накоплением и со входом и выходом блока программы .11 памяти, дифференцирующий пороговый элемент, соединенный входом с интегратором зарядов, ,а выходом с блоком программы и памяти.