Устройство для решения задач на графах Советский патент 1992 года по МПК G06F15/419 

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

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

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

переименования вершин и блок матриц -.ой модели дерева путей графа.

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

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

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

I-i VJ

О

ел

00

-N

Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов и блок переименования вершин, введены блок формирования корневой вершины и синхронизирующих сигналов, блок задания матрицы весов ребер. (В - 1) блок формирования путей, где В - количество вершин в графе. (В - 1) блок выделения направлений. {В 1) блок фиксации путей, В 1) блок формирования гамильтоноаа цикла, (В - 1) блок суммирования и В блоков выбора минимума. Выход тактовых импульсов генератора импульсогэ подключен к пхо- ду блока формирования корневой вершины и синхронизирующих сигналов, выход корневой вершины которого подключен к входу блока задания матрицы весов ребер, входу ;ока п ::iei;;-v ;: --ГГ ИР eepuiMh и пходу кор- вой еьршинь «зждого блока формирования путей, з выходы синхронизирующих СИГМЙЛОР пореск- п. г- путей и попученчя ве- .о:: рут«с-й блока формирования корнево .1 и .-.-ii М- С-ниг.ипующих сигналов поЈ -.ючены к /прянляк.;гим входам соот- --т. РОННО каждого блока фиксации путей и ажлого блока суммирования.

Выход связей вепшин блока задания а о з pef- p соединен с входами .задания р/тем К о ранга каждого блока Формирования пут(-й. г входами задания направлений передачи путей К-ro ранга каж дого выделения направлений, с входами задания цикла каждого блока формирования гамильтонова цикла и с входами задания весов путей Кто ранга каждого бло- кз суммирования, где К - 1.. (В -- 1).

По каждому входу задания путей Кто ранга, каждому входу задания направлен передачи путей К-то ранга, каждому вхс задания цикла и каждому рходу задания г - сов путей К-го ранга передается информ о связях только своей вершины. Выходы номеров вершин блока переименования першин подключены к входам своей нерии-i иы соответствующие блоков формироаа.п-ь/ путей, Выход сформированных путей К-го ранга каждого блока формирование путей подключен к информационному вход, соответствующего блока выделения ний. Выход выбранных направлений передачи путей К-го ранга M-го блока выделения направлений. де И 1...(В ). подключен к Ме-му входу совокупности путей К-го ранга каждого бпокд фиксаци--1 где е 1 (В 1)

Выход зэ Т-иксиг ивикнпх nv-тей К-ю ранга каждою блока ф ксоцчи путей подключен : входу перечня г-емиин чужих п-, К-го ранга соответс тк -нчего блока фор -1-;-- рования путб;и и вход поречн нешн .ш 1.:эо

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

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

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

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

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

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

0 выделения направлений и блоков фгрмиро- пгния гэммльтонова цикла, каждый из входов совокупности путей К-го ранга имеет разрядность последовательности вершин. . У Ои ,- Х ПУТИ (В - 1)-го ранга. Выходы

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

Введенный блок формирования корне- зой вершимы и синхронизирующих сигна5 not: гфедназнзч -;-|. лл записи номера

ОрНСВОИ БерШИНЫ ; Ы ЗЧИ уПрЭЕЛЯ ЮЩИХ

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

роб1 --ч с -е/;иня1,)Щ1.;. .. дую вершину графа с остальными вершинами. Введенные блоки формирования путей предназначены для формирования путей различных рангов к соответствующей вершине в виде перечня вершин, начиная с корневой. Введенные блоки выделения направлений обеспечивают передачу информации о путях (перечни номеров вершин) на те блоки фиксации путей, номера которых соответствуют номерам вершин, имеющим связь с последней вершиной сформированного пути и не встречавшимся ранее в перечне номеров вершин этого пути.

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

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

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

На чертеже представлена функциональная схема устройства для определения путей и циклов в графе.

Устройство для определения путей и циклов в графе содержит генератор 1 импульсов, блок 2 формирования корневой вершины и синхронизирующих сигналов, блок 3 задания матрицы весов ребер, блок 4 переименования вершин, бпоки 5.1 .5 (В - - формирования путей, блоки 6.1 ...6.(В - 1) выделения направлений, блоки 7.1 ...7.(В 1) фиксации путей, блоки 8.1...8.(В - 1) форми0 рования гэмильтонова цикла, блоки 9,1...9.(В - 1) суммирования, блоки 10.1....10.В выбора минимума, выход 11 тактовых импульсов, выход 12 корневой вершины, выход 13 синхронизирующих сигналов

5 пересылки путей, выход 14 синхронизирующих сигналов получения весов путей, выход 15 связей вершин, выходы 16.1...16.(В - 1) номеров вершин, входы 17.1...17.(В - Г) перечня вершин чужих путей К-го ранга в оды

0 18,1...18.(В - 1) задания путей К-го рлнга, выходы 19.1. .19.(В - сформированных путей К-го ранга, входы 20.1...20.(В - 1) задания направлений передачи путей К-го рянга, выходы 21.1...21.(В - 1) выбранных направ5 лений передачи путей К-го ранга, входы с 22.1.1...22.(В - 1),1 по 22.1.(В - Ц..22.(В - 1).(В - 1) совокупности путей К-го , выходы 23.1 .,23.(В - 1) зафиксированных путей Кто ранга выходы 24.1...24.(В 1)

0 зафиксированных гамильтонопнх путей, входы 25.1...25.(В - 1) задания цикла. 26.1 ...26.(В - 1) идентификации вершин цикла, выходы 27.1...27.(В - 1) перечня вершин цикла, входы 28.1...28 (В - 1) задания

5 путей К-го ранга, входы 29.1. .23.(В 11 перечня вершин своих путей К-го ргнгэ, о- о,иы 30.1...30.fB 1) идентификации оеса . выходы 3.1...31.(В - 1) результата определения сумм, сыходы 32.1...32.(В - Ь зеса

0 цикла, выходы 33.1...33.(В - 1) результата определения минимума весов путей, выход 34 результата определения минимума зеса цикла.

Генератор 1 импульсов подает на иход

5 блока 2 формирования корневой вершины и синхронизирующих сигналов последовательность тактовых импульсов, управляющих работой блоков устройства. Блок 2 формирования корневой вершины и синхро0 низирующих сигналов управляет работой блоков 3, А. 7.1...7.(В - 1), 9.1...9.(В - 1) и служит для записи номера корневой вершины. Выход 12 корневой вершины подключен к входу блока 3 задания матрицы весон ре5 бер, входу блока 4 переименования вершин и входу корневой вершины каждого б тока 5.1...5.(В - формирования путей. Выхсд 13 синхронизирующих сигналов пересылки путей блока 2 соединен с управляющим входом каждого блока 7.1...7.(В - 1) фиксации

путей, а выход 14 синхронизирующих сигналов получения весогэ путей-с управляющим входом каждого блока 9.1...9.(В - 1) суммирования. Блок 3 задания матрицы весов ребер предназначен для хранения и РЫДЗЧЧ информации о связях псех перший между собоГ-. Вы/од 15 связей аершин бпо я .3 распределен по входам 8.1 . 18.(8 1) задания nyjtin К 0 ранга блоков 5,1,,.5,(R - 1} Формирования путей, входам 0.1...2Q.(R i) задания направлений пере- дячг. путей К го ранга блоков 6.1 ..б,(В j выделении па правлении. входам 25.1.. .25.(В - ) задания мчкуи ЛОКОР fi.j...P..(B 1) ормирования гами.г. онсп-д ц п:лэ входам 2В. ..28.(В - 1) задоиим ;( аж ну геи К -: о ранга блоков 9.1 . 9.(С -- 1}

:iii ;;V Lj -i i

, л г .::; именования перши11 служи-. пя перераг,.чрг деления вершин и COOTPGT чмм г ЧЫ ПРНЧСМ корневой вершиной, его

од В. i 16.(8 - 1) номеров вершин ,. ,,--нь, i- i.i. .ЈcH i crrjew вершины r.oor не-. ;,у.онп.-.ч s.-..-,ji-ur 5 i .; (B - 1) форм;/.оо- : я путей, Ьлоки Н.1.-. 5.(В 1) Ф .( мированич путей предназначены :|-.о:)( |рования путей различных рангов ; со . : .i П :О Ие - .нИ тО.

1 -5ыход.,1 ь, i i9(B 1) сформироиян- ir.-i -; путей К го блоков 5 подключены .: информйц оксым входам соответствую щих блоке 6.1 .6.(В - 1) выделения направлений, которые обеспечивают передачу информации о путях, па те блоки фиксации путей, номера которых соответствуют номе сам вершин, имр ощим связь с последней t..- и /tной г.форг шрованного пути и не встречавшимся ранее в перечне номере- 1 nepun-ni этого пути

Выходы 21.1 ..21 (В - 1) выбранных правлений передачи путей К-го ранга гее б подключены к входам с 22.1.1.. 22.(В

. 1 по 22.1,(В 1).. 22 (В - 1).(В - 1; совокупности путей К-го ранга блоков 7 1,..7,(Г. } путей. этом выход 2V пят.пределен по нходам 22.1.1...22.; (0 - 1), :нход21,2 - по входам 22.2.1,..22,2.ГВ - 1)н т.д

Бпоки 7.1...7 (В - 1) фиксации пуюй civ- жат для передачи информации о путях, по ступившей на них с. различных олоков выделения направлений, на свои блоки формирования путей з также выдачи перечня иоршин, оостав.мяющих пути различного | .1лнга. в том числ-г4 ч гамильтоновы, нл оно -ОЛОКИ СУММИРОВАНИЯ И 1.00МИрОЯ. 1Я МИЛЬТОЧОЯЭ ЦИКЛН

Вмчоды 23.1.. 23.(П 1) зафиксирс аь г-:ь;х путей К--л psma б-юкоч 7 , . вводам 17 1.. I Л(В I) перечня р.р.ил ч

чужих путей K-ro ранга соответствующих блоков 5.1 ...5.(В - 1) формирования путей и к входам 29.1...29.(В - 1) перечня вершин своих путей К-го рано соответствующих

блоков суммирования 9.1...9.(В - 1), а выходи 24,1...24.(В - 1) зафиксированных гэмиль- TOHOBLU путей блоков 7 подключены к информационным входам соответствующих бликоо 8,1..,8.(В - 1) формирования (амильi тоноча цикла.

БПОКИ суммирования предназначены для получения весов путей различных рангов и циклов, их выходы 31.1...31.(В - 1) результата определения сумм подключены

к еход-чм соответствующих блоков 10 1 ...10,(В 1) выбора минимума, а выходы М. .32,(В - 1) веса цикла всех блоков 9 с . ммпроЕ зпия подключены к соответствую- (.ими ьходам блока HI В выбора минимума.

Блоки формирования омильтонова цикла для фор.1иропзния гамильтонопа ., в виде перечня верши;, их выходы .г/, 1 ...v/.(B - ) перечня вершин цикл под- :лю)ены к входам перечня вершин цикла

соответствующих блоков 9.1...9.(В - 1) сум- миропания.

Блоки выбора минимума предназначена для определения меньшего по весу пути ( икла) сред-/, всех путей различного рэнга

(цмслов), Р том числе и гэмильтоновых. Вы- .( дь; 33,1...33.(В - 1) результата определе- i: и я м й ним ума весов п у т е й б л оков 10. ..,10,(В - 1) выбора минимума подключены к входам идентификации вершин пути

соответствующих блоков 7 фиксации путей и эходам идентификации веса пути соответствующих блоков 9 суммирования. Выход 34 результата определения минимального зеса чикла блока iO.B выбора минимума соеди: мен с входами 26.1...26,(В - 1) соотоетстэую- блоков 8.1...8.(В - 1} формирования .1|Тьтонс.1оа цикла и входами 30.1 .30.(В - :; идентификации песа цикла соответствующих биокоы 9.1...9.(В - 1; суммирования.

п:лод; см поло;;-.ен1|И в блоке 2 запиcdi; номер корневой вершины, в блоке 3

записаны веса ребер всех смежных вершин,

я блоке записаны номера всех вершин.

Устройство для определения путей и

1 циклов в графе работает следующим образом.

По первому тактовому импульсу с генератора 1 номер корневой вершины из блока ; поступает на блоки 3 задания матрицы

: Biicog ребер, блок , ереименования вершин и бпоки 5. i . S.fP 1) формирования путей В блоке й пр/оис : -/(Ит перераспределения номеров верши:, (номер корневой Беп.лчнь :сключэет-.я, на его месте при- сутг. i луг т номер nrv.:... -;й вершины В; еели корневая вершина - В, то перераспределения не происходит) и эти номера с выходов 16.1...16.(В - 1) поступают на соответствующие блоки 5.1...5.(В - 1} формирования путей о блоке 3 присходит перераспределение связей вершин графа в соответствии с перераспределением номеров веошин в блоке 4 и связи каждой (кроме корн OP ой) вершины (веса ребер, соединяющих вгршпну с остальными вершинам; графа; если связи нет, то на месте веса ребра передается 0) выдаются Б с.оответсгвую- щие блоки 5.1...5.(В - 1} Формирования путей, блоки 6.1 ...5.(В - 1) выделения направлений, блоки 8.1...8,(В - 1) формиро- еания гзмильтонова цикла и блоки 9,1...9.(В - 1) суммирования.

В блоках 5. вершины которых имеют связь с корневой вершиной, формируются пути первого ранга, которые с выходов 19 поступают в соответст вующие блоки б аыде- ления направлений. В этих блоках учитывается, что путь прошел уже через две вершины и цикл не должен образоваться (т.е. дважды через одну вершину путь не должен пройти), э также определяются вершины, с которыми связана последняя (вторая) игр минз пути (чтобы образовать пути второго ранга) и после этого пути первого ранга из блское б передаются е CUOTSRTCT- вующие блоки 7 фиксации путей. Затем из каждого блока 7 по приходу сигналя с выхода 13 блока 2 путь первого ранга к своей вершине передается нл соответствующий блок 9 суммирования, о остальные пути первого ранга к -1ужим вери. инам передаются на соответствующий блок 5 формирования путей.

В блока/ 8 суммирования по сигналу с выхода 14 блока 2 происходит определение веса пути первого ранга. Этот вес передается но соответствующий блок 10 ьыборэ минимума и определяется там как минимальный (путь первого ранга к каждой вершине может быть только один), а сигнал с выходе. 33 результата определения минимальных весов путей позволяет зафиксировать этот путь в блоках 7 (перечень вершин пути) и 9 (вес пути). В блоках 5.1...5,(В - 1) формируются пути второго ранга, которые через блоки 6.1...6.(В - 1)выделения направлений передаются на соответствующие бло ки 7.1...7.(В - 1) фиксации путей, а из них - опять на свои блоки 5 формирования путей, где формируются пути третьего ранга, и свои блоки 9 суммирования и 10 выбора минимума - определяются кратчайшие пути второго ранга (в блоке суммирования определяются веса путей, а в блоке выбора минимума находится меньший из этих весов).

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

Кроме того, гамильтоновы пути из бло0 ков 7.1..,7.(В - 1) фиксации путей передаются в соответствующие блоки 8.1...8.(В - 1) формирования гамильтоновэ цикла, в которых определяется наличие связи между последними вершинами гэмильтоновых путей

5 и корневой вершиной и при наличии такой связи сформированные гамильтоновы циклы в виде перечня вершин передаются в соответствующие блоки 9.1 ...9.(В - 1) суммирования, где определяются веса гамильто0 новых циклов. Веса циклов передаются на блок 10.R выбора минимума, где определяется цикл с минимальным весом и идентифицирующий сигнал об этом с выхода 34 блока 10. В передается на соответствующий

5 блок 8 формирования гэмильтонова цикла (фиксируется перечень вершин цикла) и соответствующий блок 9 суммирования (фиксируется вес цикля), устройство зачершает работу.

0 Технико-экономическая эффективность предлагаемого изобретения заключается в том. что возможность определения кратчайших путей различного ранга, а также га- МУ.ЛЬТОЧОЯЫХ путей и циклов позволяет с

5 высоким быстродействием решать большой класс , -имеющих практическое применение а различных областях (вычислительные системы и сети, транспорт, системы управления и др.). Кроме тсто, изобретение

0 проще по сравнению с прототипом, так как уменьшено число блоков формирования путей с В до 4В и уменьшено число связей между блокамл.

Положительный эффект, который может

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

0

Формула изобретения

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

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

К-го ранга каждого блока формирования путей подключен к информационному входу соответствующего блока выделения направлений, выход выбранных направлений передачи путей К-го ранга M-го блока выделения направлений (М 1,..., В - 1) подключен к M-му входу совокупности путей К-го ранга всех блоков фиксации путей, выход зафиксированных путей К-го ранга каждого блока

фиксации путей подключен к входу перечня веошин ЧУЖИХ путей К-го оанга соответствующего блока формирования путей и к входу перечня вершин своих путей К-го ранга соответствующего блока суммирования, выход зафиксированных гамильтоновых путей каждого блока фиксации путей подключен к информационному входу соответствующего блока формирования гамильтонова цикла, выход перечня вершин цикла которого подключей к одноименному входу соответствующего блока суммирования, выход суммы каждого блока суммирования подключен к информационному входу соответствующего блока выбора минимума, выход результата

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

Изобретение относится к кибернетике и вычислительной технике и предназначено для использования при решении задач комбинаторной оптимизации на графах. Цель изобретения - упрощение устройства и расширение его функциональных возможностей - достгается путем введения блока 2 формирования корневой вершины и синх- ронизирукж(их сигналов, блока задания матрицы весов ребер, блоков формирования путей, блоков выделения направлений, блоков фиксации путей, блоков формирования гамильтонова цикла, блоков суммирования и блоков выбора минимума. Сущность изобретения состоит в том, что при выделении направлений передачи путей и их промежуточной фиксации формирование путей различных рангов к одной вершит1 происходит в одном блоке, чго уменьшает чисто блоков формирования путей. Кроме того, введение блоков рыГюра минимума позволяет определять минимальные веса путей и циклов, что расширяет Функциональные ВОЗМОЖНОСТИ устройства. З ТКЛ ОЧЗЮЩИб-С;; В способности определясь кратчайшие пути различного ранга, а гамилыоносы пути и циклы. 1 ил.