Устройство для решения задач на графах
Изобретение относится к кибернетике и вычислительной технике и предназначено для использования при решении задач комбинаторной оптимизации на графах. Цель изобретения - упрощение устройства и расширение его функциональных возможностей - достгается путем введения блока 2 формирования корневой вершины и синхронизирукж(их сигналов, блока задания матрицы весов ребер, блоков формирования путей, блоков выделения направлений, блоков фиксации путей, блоков формирования гамильтонова цикла, блоков суммирования и блоков выбора минимума. Сущность изобретения состоит в том, что при выделении направлений передачи путей и их промежуточной фиксации формирование путей различных рангов к одной вершит1 происходит в одном блоке, чго уменьшает чисто блоков формирования путей. Кроме того, введение блоков рыГюра минимума позволяет определять минимальные веса путей и циклов, что расширяет Функциональные ВОЗМОЖНОСТИ устройства. З ТКЛ ОЧЗЮЩИб-С;; В способности определясь кратчайшие пути различного ранга, а гамилыоносы пути и циклы. 1 ил.
Со«03 CORI T<:Il
С011ИАЛИСТ ИЧЕСКИХ
РЕС««УБЛИК (и5 G 06 F 15/419
ГОСУДАРС < ГЗЕ«1НЫЙ КОМИТЕТ
ПО ИЗ06РЕ«ЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГК««< СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4828057/24 (22) 05.03.90 (46) 15.01,92. Бюл, N 2 (72) В,Я.Певнев, С,А.Ильин, С.В.Листровой, Я,В.Боровик и М.Л.Дикий (53) 681,333(088.8) (56) Авторское свидетельство СССР
N- 485451,,кл. 6 06 F15/20,,1971.
Авторское свидетельство СССР
N. 1462352, кл. G 06 F 15/20, 1987. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ
НА ГРАФАХ (57) Изобретение относится к кибернетике и вь<числительной технике и предназначено для использова«<ия при решении задач комбинаторной оптимизации на графах. Цель изобретения — упрощен«1с устроиства и рас:— ширение его функциональных возможностей — достигае ся путем введения блока
Изобретен11е относится к кибернетикe и вычислительнои технике и пред-<азначе«<о для использования при решении задач комбинаторной оптимизации на графах.
Известно устройство для моделирования кратчайших путей на графе, содержащее блок формирования топологии. блок управления, формирователь временного интервала, логические элементы и задатчики адресов вершин. Это устройство не позволяет определять кратчайшие пути определенного ранга, а также тамил ьтоновы пути и циклы и имеет низкое быстродействие.
Наиболее близким к предлагаемому следует считать устройство, содержащее генератор импульсов, блок управления, блок
50 1705841 А1 формирования корневой вершины и синхронизирующих сигналов, блока задания матрицы весов ребер, блоков формирования путей, блоков выделения направлений, блоков фиксации путей, блоков формирования гамильтонова цикла, блоков суммирования и блоков выбора л1инил1ума. Сущность изобретения состоит в том, что при выделении направлений передачи путей и их промежуточной фиксации формирование путей различных рангоь к одчои вершин« происходит в одном бл ке, что ул1еньшае1 число блоков формиргван ««я путей. Крс: л1е 1с го, введение блоков вь«бора минимум"-, пс3Bcляет определять минимальные веса путей и циклов, что рde««<иряеT фу<.«;,I 1она",5 нь«е возможности ус; рой:тва зал ч о Недостаткал«и известного являются его сложность и ограниченные функциональные возможности, заключающиеся в неспособности определять кратчайшие г ути определенного ранга, а также гамильт<>новы пути и циклы. Необходимость определения крат.«айших путей различного ранга, а также гамильтоновых путей и циклов возникает при решении таких задач как оптимальное упорядочение обьектов, маршрутизация сообщений, нахождение оптималь><ого порядка обработки деталей и др. Целью изобретения являе;ся расширение функциональных возможностей устройства за счет определения кратчайших и пей и циклов определенного ранга. 1705841 Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов и блок переименования вершин, введены блок формирования корневой вершины и синхронизирующих сигналов, блок 5 задания матрицы весов ребер.( — 1) блок формирования путей, где B — копичес>(>о вершин в графе. (B — 1) блок выделения направлений, (О - 1) блок. 1>иксэции путей,,B -- 1) блок формирован:<я гамильтонова 10 цикла, ( — 1) блок суммиро».RHuп и В блоков выбора минимума. Выход тактовых импульсов генератора импульсов подкл(очен к входу блока формирования корнев и вершинь. и синхронизирующих сит>(апов, выход кор- 5 невой вершины KOTcpoãо подключен к входу блока задания матрицы ве(.ов ребер, входу - н я в е p . IA t:,1 а х с <." у !(о с<< с R i >; ", в, э ! у ! - >, ч, > ук д > г о Г!. в э !!я и;<тей. а выходы синхро!(изирующих 20 -".lc:,RëîR. и;:оес; и. и путей In по",учен (и веf I -I<< б 1! > к а <»ко»э миг!<, вен и я коснев(>! »ЕГ! л«li И . >: ХРСНИ. Г<У!ОЩИХ ClnfНапОВ под:;ючены к, пра»<»1о каждого блок,! ф(!хсэц(1и путей и 25 "э> ього блока суммировэн(;ч. Выход связей вепшин блока задания ИЦ»! Э- .(>В ОЕГ Р СОRДИНЕН С ВХОДаМИ задания г,3 и К . ра» < а каждого б lo» фср»лирова»<(1я lóT й1, и ей К- о ранга каж дого блока эь!.1епения направлений, с входами задания цикла каждого блока формирования гамильтонова цикла и с входами зацэния весов и, ей К-ro ранга каждого бло- 35 ка -.уммирования, где Y, = 1.. (B — 1), По каждому входу задания путей»,-го ранга, каждому входу задания направлен!1" перед,:.!(и пу>ей К-го ранга, каждому вхс задания ц :!кпа <п каждому входу зада»!ия < 1О сов путей К-ro ранга г>ередается информ,: ц яосвязях-ол-косвоей вершины, Выходь номеров верши!! блока f>(сейме(-.овэния першин г Здключены». нходалл своеи»>ер(!>! ; ы с(ol t <тствующи б <с ков фор»ли(>г RR((" i 1< путей, Выход сформирован»!ых пут и К- о ранга;(эждого блока формировэни(путей подключен к информаци >и«ому вход сооТветствующего блока выде ний. Выход выбранных напр» 3>>ений 59 пЕредачи путей К-го ра! г,> M-co блэка выце— пения направ,!ений I де !Л =- 1,.(В . !. г>одключе-! к Уе-му входу спвпку
К ГО оэ»!(а каждого блок фикгэ(!и <1/T5 В Qxog Зэ<т Pili и<.;iâ<< 1! к . .. Tвй ранга кэ: до(э б>пока ф!.кс". >, чl пу>гп п(дкл!очен . входу переч»!-. ---!,II Ini !ужин "òn!1 К-го ранга соо>ветс; ->((ег» блок- фор рован(;!я г<утеи и RxoJ! « Выход результата определения сумм каждого блока суммирования подкпк>чзн к входу соответствующего блока выбора минимума, а выход веса цикла каждого блока суммирования подключен к соответствующему вхоцу последнего блока выбора миниму»ла. Выход результата опрецеления минимума весов путей каждого, кроме пог. ецнего. блока выбора мини(1умэ сс(ци»!ен ! входом идентификации вершин пути соответствующего блока фиксации путей и входом идентификации вес» пути г. огветствующе(о блока сум!.1и;>.,вания. Я!.!ход резуп! тата опредепе.1,ч м! имэпь-! пг0 Bnса цик !а г!оследнего блокd RI.IF op; »n!nl »н.>ума п(>дкпючен к входу идент(1<1>у(кации вершин цикла каждого блока формировэ!!ия гамипьтонова цикла и входу ,,<;::-нтиф <".><л1л1ирс>(<<>ния. Выходы корн вой вер оины и номеров Rinршин (!мею! разрядно(ть (13K симэпьно;о номера вершины в графе каж дь и из вксдов задания путей V,— о ранга. задания направлений I!åðåäà÷è путей К-fo ранга, задания !(икла и задания весов путей К-го pRHf имеет разряднос ь последовательности весов ребер, связывэ!ощих одну е(0!и«у графа с оста>!ьнь<л1(1 К«жд.!и из акод!ов пере !ня вершин чужих !I с(>оих путей К-fo г<энга инфор»лационных вх.>;lon бп(>кое <>ыдопен»1я «эправпений и блокon фсрмироl.RHl R гамнпьтонова цикла. каждый viз Rxo дов совокуг;><ости путей К-го ран(а имеет р; зрядносгь последовательности вершин. 0(,<>а.<ус<((;! к г!vTIn ( — 11-го ранга, Выходы редел ния сумм имеют разр:<д, с; ь соответствуьэщую разрядности вс".on lly с.й ( — 1)-го ранга, каждый выход пере«;(я .ер(;йч ци"ла имеет разрядность и >следователь«ости номеоов вершин, обраэук>и.их путь Р-гс ранга. а каждый выход гесэ цикла !лмеет разрядность, соответствующую разрядное-и веса !>ути B-ro ранга. F".веде(!нь<й блок формирования корневой в ршичы и 1«хронизиру!ощих сигналов г редназн.э »:! .;и» записи номера :opt .!.!3ой верши» (! у! в,!цачи управ.-.яющих имп!пьсов íà бпо><(фиксации путей и сумМИРОВЭ. ИП ЕаПДЕН:blfn ."1ОК ЗаДЭНИЯ,ЛатРИ<(ч еесо(: ребер ст!ужи- для записи весов ; об > с е„иня! >(ц! дую вершину гра1705841 фа с остальными вершинами. Введенные блоки формирования путей предназначены для формирования путей различнык рангов к соответствующей вершине в виде перечня вершин, начиная с корневой. Введенные блоки выделения направлений обеспечивают передачу информации о путях (перечни номеров вершин) на те блоки фиксации путей. номера которых соответствуют номерам вершин, имеющил1 связь с посл,дней вершиной сформированного пути и не встречавшимся ранее в перечне номеров вершин этого пути. Введенные блоки фиксации путей служат для передачи информации о путях, поступившей на них с различных блоков выделения направлений, на свои блоки формирования путей, а также выдачи перечня вершин, составляющих пути различного ранга, в том числе и гамильтоновы, на свои блоки суммирования и формирования гамильтонова цикла. Введенные блоки формирования гамильтонова цикла предназначены для формирования гамильтонова цикла в виде перечня вершин. Введенные блоки суммирования служат для получения весов путей и циклов. Введенные блоки выбора минимума предназначены для определения меньшего по весу ути (цикла) среди всех путей различного ранга (циклов), в том числе и гамильтоновых, к каждой вершине. Сущность предлагаемого решения состоит е том, » го при выделении направлений передачи путей и их промежуточной фиксации формирование путей раэлИчнь»х оа».:гов к одной вершине происходит в од»»ом блоке, что уменьшает число блоков формирования путей с В до 4В. Кроме»ого. введение бло2 ков выбора минимума позволяет определять минимальные веса путей и циклов. что расширяет функциональные воэможности устройства, заключа сщиеся в способности определять кратчайшие пути различного ранга, а также гамильтоновы пути и циклы, Возможность достижения положительного эффекта подтверждается тем, что введение блоков формирования корневой вершины и синхрониэирующих сигналов, задания матрицы весов ребер. формирования путей, выделения направлений, фиксации путей, формирования гамильтонова цикла, суммирования, выбора минимума и обусловленных ими связей позволяют упростить устройство и расширить его функциональные воэможности. На чертеже представлена функциональная схема устройства для определения путей и циклов в графе. Устройство для определения пут».й и циклов в графе содержит генерато-» 1 импульсов. блок 2 формирования корневой вершины и синхрониэируюших сигналов, 5 блок 3 задания матрицы весов ребер, бг»ск 4 переименования вершин, блоки 5.1 .5 (В— — 1) формирования путеи, блоки 6.1...6.(Š— 1) выделения направлений, блоки 7.1... ».{Е 1) фиксации путей, блоки 8.1...8.( — 1) форми10 рования гэмильтонова цикла, блоки 9.1...9.( — 1) суммирования. блоки 10,1„..10.В выбора минимума, выход 11 тактовых импульсов, выход 12 корневой вершины, выход 13 синхронизирующик сигн.)лов 15 пересылки путей, выход 14 синхронизирующих сигналов получения весов путей, выход 15 связей вершин, выходы 16,1...16.( — 1) номеров вершин, входы 17.1.„17.( — 1) перечня вершин чужих путей К-го ранга в> оды 20 18,1...18.( — 1) задания путей К-го ранга, выходы 19.1..19.( — 1) сформированных путей К-го ранга, входы 20.1...20.( — 1) задания»ÿïðàoëåí»»»» передачи путей К-го ранга, выходы 21.1...21,( — 1) выбранных направ25 лений передачи путей К-го ранга, вхо,1ь» с 22.1.1...22,( — 1),1 по 22.1.( — 1),..22 (В— — 1),( — 1) совокупности путей К-го ранга, выхсдь. 23 1 .,23.( — 1) зафиксировэ» нык путей К го ранга вь»ходь» 24. »...24.{»3 1) 30 зафиксированных»амильтоновых п »ей, входы 25,1...25.(B — 1) зада»»ия ци;л . в оды 26.1...26.( —. 1) идентификации Bpрши». »»»кла. выходы 27.1...27.( — ») пе»;t- »ня вор и:н цикла, входы 28.1...28 (Р— 11 задания в сов 35 путей k-го ранга, входь» 29.1..23.(H 1» и»речня вершин свои»»утей K-»»»:i" »»ãà, в о,»ь» 30.1 330 (Е» 1 » иден;иф,кации веса ii "ла, выходы 3!.1...31.( — 1) реэ"л тата определения сумм. вь.ходы 32.1...32.{B - 1. веса 40 цикла, выходы 33.1...33,( — 1) результата определения минимума весов путей, в»»ход 34 результата определения минимума зеса цикла. Генератор 1 импульсов подает на ;код 45 блока 2 формирования корневой вершины и синхронизирующих сигналов последовательноСть тактовых импульсов, управ,lяющих работой блоков устройства. Бл»>к 2 формирования корневой вершины и синхро50 ниэирующих сигналов управляет раб.»той блоков 3, 4. 7.1.„7.( — 1), 9.1...9.(B — 1) и служит для записи номера корневой ве»»шины. Выход 12 корневой вершины подкл».»чен к входу блока 3 задания матрицы восо«ре55 бер, входу блока 4 переименования вершин и входу корневой вершины каждого 6 ока 5.1...5.(S — 1) формирования путеи. В ыхсд 13 синхронизирующих сигналов пересылки путей блока 2 соединен с управляющим входом каждого блока 7.1...7.( — 1) фикс;»ции 1705841 55 ли корневая вершина — В,то перераспределения не происходит) и эти номера с Gblxo дов 16.1...16,(B — 1) поступают на соответствующие блоки 5.1...5.( — 1) формиоования путей 0 блоке 3 присходит перераспределение связей вершин графя в соптве;ствии с перераспределением номер< в вен.нин в блоке 4 и связи каждой(кроме корн.-. ой) вершины (веса ребер, соед:няющих в;-ршпну с остальными вершинами графа; если связи нет, то на месте веса ребра передается О") выдаются в соответсгвующие блоки 5.1...5.( — 1) формирования путей, блоки 6.1 ..6.( — 1) выделения направлений, блоки 8.1...8,( — 1) формирования гамил тонова цикла и блоки 9, 1 ...9,(B -- 9 сумм 1 рояания. В блока", 5, вг р.нины которых имеют связь с корневой вершиной. формируются пути первого ранra. которые с выходов 19 поступают в саотннтс яующие блоки 6 ныцеления направлений. В этих блоках учитывается, что путь прошел ywe через две вершины и цикл не должен образоваться (т,е. дважды ерез одну вершину путь не должен пройти), а также определя отся вершины, с которыми;.вязана последняя (втсрая) нср. ин". пути, чтобы образовать пути второго ранга) и пссле этого пути первого ранга иэ блсхо1 6 передаются в соответствующие блоки 7 фик.ации путей. Затем нэ каждого бгпка ". по и",иходу .игналл с выхода 13 блока 2 путь первого ранга к своей вершине 1ередаетс-. н: соответствующий блок 9 суммиоования,; остальные пути первого ранга к чужим верн-инам передаются на соответствующий блок 5 формирования путей. В блоках 8 суммирования по и-.налу с выхода 14 блока 2 происходит определение веса пути 1ервого панга. Это вес передаетсч ча соотеетствук щий баoK ". bLI Gopa MH" нимума и опредсляе1ся там как минимальный (путь первого ранга к каждой вер ии.<е может быть только один). а сигнал с выхода 33 результата определения минима ьных весов путеи позволяет зафиксировать этот путь в блоках 7 (перечень верUJèí пути) и 9 (вес пути). Б блоках 5.1...5,(В - 1) формируются пути второго ранга, которые через блоки 6.1...6.( — 1) выделения направлений передаются на соответствующие блоки 7,1...7.( — 1) фиксации путей, а из них— опять на "свои" блоки 5 формирования путей, где формируются пути третьего par ra, и "свои" блоки 9 суммирования и 10 выбора минимума — определяются кратчайшие пути второго ранга (в блоке суммирования определяются веса путей, а в блоке выбора минимума находится меньший из этих весов), 5 Таким образом, при одном цикле работы устройства определяются кратчайшие пути какого-то ранга к каждой вершине, На ( — 1) цикле в блоках 5 формируются гамильтоновы пути, которые также через бло-. ки 6 передаются в блоки 7, а из них в блоки 9 и 10.1..,10,( — 1) — определяются кратчайшие гамильтоновы пути. Кроме того, гамильтоновы пути иэ блоков 7.1...7.(B — 1) фиксации путей передаются в соответствующие блоки 8,1„,8.( — 1) формирования гамильтонова цикла, в которых определяется наличие связи между последними вершинами гамильтоновых путей и корневой вершиной и при наличии такой связи сформированные гамильтоновы циклы в виде перечня вершин передаются в соотг ветствующие блоки 9.1...9.( — 1) суммировачия, где определяются веса гамильтоновых циклов. Веса циклов передаются нв блок 10.R выбора минимума, где определяется цикл с минимальным весом и идентифициругощий сигнал об этом с выхода 34 блока 10.В передается на соответствующий блок 8 формирования гамильтонова цикла (фиксируется перечень вершин цикла) и соответствующий блок 9 суммирования (фиксируется нес цикла), устройство завершает работу. Гехнико-зкономическая эффек ивность предлагаемого изобрстения =акл очается B том, что возможность определения кратчайших путсй различного ранга. а также гамильточояых путей и цикл;в Il03B0ляет с аыс..ким бы-,родейстнием решагь большой ,асс задач, имеющи.-.:. пакти <еское примен ;. Нио е различФ" и:" . Обл;-."-.Тях,вычислитель ные системы и сети, транспорт, системы управ ения и др.j. Крогле n ro, изобретение проще по сравнени о с прототипом, .3К как уменьшено число блоков формирова;;ия пупz тей с В „ 4B и уменьшено число связей между блокамл. Положительный эффект, который может быть достигнут при использовании предлагаемого изобретения по сравнению с прототипом, состоит в том, что повышается гибкость и эффективность управления вычислительными сис1 емами и сетями ЭВМ. Формула изобретения Устройство для решения задач на графах, содержащее генератор импульсов и блок переименования вершин, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей устройства путем определения кратчайших путей и циклов определенного ранга, в него введены блок формирования корневой вершины и 1705841 12 синхронизирующих сигналов, блок задания матрицы весов ребер, ( — 1) блок формирования путей, где  — количество вершин в графе,  — 1 блок выделения направлений,  — 1 блок фиксации путей,  — 1 блок формирования гамильтоновых циклов,  — 1 блок суммирования и В блоков выбора минимума, причем выход генератора импульсов подключен к тактовому входу блока формирования корневой вершины и синхронизирующих сигналов, выход номера корневой вершины которого подключен к одноименным входам блока задания матрицы весов ребер блока переименования вершин и всех блоков формирования путей, выходы синхронизирующих сигналов пересылки путей и выходы получения веСов путей блока формирования корневой вершины и синхрониэирующих сигналов подключены к управляющим входам всех блоков фиксации путей и всех блоков суммирования соответственно, выход связей вершин блока задания матрицы весов ребер подключен к входам задания путей К-го ранга всех блоков формирования путей (К = 1,...,  — 1), к входам задания направлений передачи путей К-го ранга всех блоков выделения направлений, к входам задания цикла каждого блока формирования гамильтонова цикла и к входам задания весов путей К-го ранга каждого блока суммирования, выходы номеров вершин блока переименования вершин подключены к входам одноименных вершин соответствующих блоков формирования путей, выход сформированных путей К-го ранга каждого блока формирования путей подключен к информационному входу соответствующего блока выделения нап равлений. выход выбранных направлений пере5 дачи путей К-го ранга М-го блока выделения направлений (М = 1,...,  — 1) подключен к M-му входу совокупности путей К-го ранга всех блоков фиксации путей, выход зафиксированных путей К-го ранга каждого блока 10 фиксации путей подключен к входу перечня вепшин ччжих пчтей К-го ванга соответствчющего блока формирования путей и к входу перечня вершин своих путей К-ro ранга соответствующего блока суммирования, вы15 ход зафиксированных гамильтоновых путей каждого блока фиксации путей подключен к информационному входу соответствующего блока формирования гамильтонова цикла, выход перечня вершин цикла которого под20 ключен к одноименному входу соответствующего блока суммирования, выход суммы каждого блока суммирования подключен к информационному входу соответствующего блока выбора минимума, выход результата 25 каждого иэ которых (исключая В-й) подключен к входу идентификации вершин пути соответствующего блока фиксации путей и к входу идентификации веса пути соответствующего блока суммирования, выход ре30 эультата В-го блока выбора минимума подключен к входам идентификации вершин цикла всех блоков формирования гамильтонова цикла и к входам идентификации веса цикла всех блоков сум35 мирования. 1705841 Составитель B. Певнев Редактор А. Маковская Техред М.Моргентал Корректор Т, Патай Заказ 195 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5 Производственно-издательский комбинат Патент" г. Ужгород, ул.Гагарина. 101
