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

 

Изобретение относится к вычислительной технике и может быть ис пользовано для поиска всех возможных путей на транспортной сети, связывающих заданную пару станций. Целью изобретения является повышение точности при определении не только одного пути, но и всех возможных между заданными вершинами в графе. Устройство содержит блоки 1, 2 памяти, регистры 4-8, блоки 9-12, 21 сравнения, накапливающий сумматор 20, счетчики 18, 19, элемент ИЛИ 22, генератор 23 импульсов, блок 24 регистров. I нл.

;СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

09> Ol) (51)4С 06 F15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ (еР

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3771629/24-24 (22) 18.07.84 (46) 23.02.87. Бюл. Р 7 (71) Ленинградский институт авиационного приборостроения (72) M. Б. Игнатьев, В. И. Петров и В. Е. Сорокин (53) 681.325(088.8) (56). Авторское свидетельство СССР

У 962969, кл. G 06 F 15/20, 1981.

Авторское свидетельство СССР

У 8514 11, кл. G 06 F 15/20> 1979. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПУТЕЙ В ГРАФЕ (57) Иэобретение относится к вычислительной технике и может быть ис пользовано для поиска всех возможных путей на транспортной сети, связыва-. ющих заданную пару станций. Целью иэобретения является повьпленне точности при определении не только одного пути, но и всех возможных мелщу эаданными вершинами в граФе. Устройство содержит блоки I, 2 памяти, регистры 4-8, блоки 9-!2, 21 сравнения, накапливающий сумматор 20, счетчики

18, 19, элемент ИЛИ 22, генератор 23 импульсов, блок 24 регистров ° 1 ил.

1292000

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

Цель изобретения — повышение точности, f0

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

Устройство для определения путей в графе содержит блоки 1 и 2 памяти, блок 3 регистрации, регистры 4-8, блоки 9-12 сравнения на равенство, мультиплексоры 13-17, счетчики 18 и

19 накапливаюшего сумматора 20, блок

2! сравнения на больше-меньше, элемент Иг!И 22, генератор 23 импульсов и блок 24 регистров.

Первый вход блока 1 памяти соединен с первыми входами блока 24 регистров (пути) и регистра 6 (предше25 ствующей вершины) . Выход регистра 4 (текущей вершины) подключен к первому входу блока 9 сравнения на равенство, второй вход которого соединен с выходом регистра 5 (конечной вершины). Выход регистра 8 (началь— ной вершины) соединен с первыми входами блока 10 сраннения на равенство и мультиплексора 13, выход которого подключен к первому входу регистра 4 (текущей вершины), выход ко- 35 торого подключен к первым входам блока 1 памяти и мультиплексора 1, входу блока 2 памяти и второму входу блока 10 сравнения на равенство, выход которого соединен с первым входом мультиплексора 15, второй вход которого подключен к выходу блока 11 сравнения на равенство.

Первый вход блока 11 соединен с 45 первым входом блока 1? сравнения на равенство и выходом регистра 6 (предшествующей нерщины), второй вход которого подключен к второму входу мультиплексора 13 первому входу сум- 0 матора 20, входу счетчика 18, выходу элемента ИЛИ 22 и второму входу блока 24 регистров (пути), выход которого соединен с первым входом блока 3.

Второй вход блока 3 подключен к первому входу блока 21 сравнения на больше-меньше и выходу сумматора 20, второй вход которого соединен с первым входом блока 1 памяти и выходом мул!э тп JI. IQK cop p. 6 пер выл вход кото рого подключен к первому выходу блока 2 памяти.

Второй выход блока 2 соединен с вторым входом блока 11 сравнения на равенство и первым входом мультиплексора !7, второй вход которого годключен к второму входу мультиплексора 16 и выходу мультиплексора 15, третий вход которого соецинен с первым выходом счетчика 18, второй ныход которого подключен к второму входу мультиплексора !4, выход которого соединен с вторым входом блока ) памяти.

Выход мультиплексора !7 подключен к третьему входу мультиплексора 13, BT îðoìó входу блока I памяти и второму входу блока 12 сравнения на равенство, выход которого соединен с первым входом элемента ИЛИ 22, второй вход которого подключен к третьеI му входу блока 3, выходу блока 9 сравнения на равенство и входу счетчика 19, выход которого соединен с четвертым входом блока 3. Выход схе мы 21 сравнения на больше-меньше подключен к третьему входу элемента ИЛИ

22. Выход генератора 23 импульсов соединен с вторым входом регистра 4 (текущей вершины) и третьими входами блока 24 регистров (пути), третьего регистра 6 (предшествующей вершины) и сумматора 20. Второй вход схемы 21 сравнения на больше-меньше подключен к выходу регистра 7 (максимального веса).

Входами устройства являются входы регистра 8 (начальной вершины), регистра 5 (конечной вершины), регистра 7 (максимального веса), генератора 23 импульсов и входы обнуления счетчиков 18 и 19 соответственно.

Блоки 1 и 2 памяти выполняются на ППЗУ, шина данных которых распределяется между первым и вторым выходами этих блоков, вход блока 2 памя— ти является шиной адреса, а входы блока 1 памяти составляют его шину адреса. Программирование блоков 1 и 2 памяти осуществляется перед работой устройства в соответствии с графом, на котором определяются пути, на специальных устройствах-программаторах.

Блок 24 регистров (пути) выполняется н виде параллельно включенных сднигающих регистров, число которых!

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

Мультиплексоры 13 и !5-17 осуществляют выбор одного слова из двух поступающих слов в зависимости от управляющего сигнала. В мультиплек— сорах 16 и !7 оба поступающих слова подаются по первому входу (одна половина разрядов шины используется под одно слово, другая — под другое), а в мультиплексоре 14 все поступающие слова подаются по второму входу.

В мультиплексоре 15 осуществляется выбор одного иэ двух поступающих одноразрядных слов.

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

Предварительно в блоки 1 и 2 памяти заносится информация о графе: в блок 1 — информация о ребрах, инцидентных вершинах со степенью больше двух, в блок 2 — информация о ребрах, инцидентных вершинах со степентю два. Если у вершины степень единица, то инцидентное ей ребро указывается дважды. Информация в блоки памяти записывается следующим образом. -30

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

Перед началом работы в регистры

5 и 8 записываются коды конечной и 45 начальной вершин соответственно. После этого обнуляется регистр 7, в результате чего единичный сигнал с выхода блока 21 сравнения на большеменьше через элемент ИЛИ 22 поступа- 50 ет на второй (управляющий) вход мультиплексора 13. По этому сигналу на первый (информационный) вход регистра 4 мультиплексора 13 подает код начальной вершины с выхода регистра

8 и обнуляются третий регистр 6, блок

24 регистров и сумматор 20. Этот код записывается в регистр 4 по начальному единичному импульсу генератора

23 импульсов. Затем в регистр 7 записывается код максимально возможного веса пути в данной графе для определения зацикливания или код максимального веса пути, приемлемого в данном случае. После этого обнуляются счетчики 18 и 19 и запускается генератор

23 импульсов.

Генератор 23 импульсов выр .батывает синхрониэирующие импульсы, которые подаются ча входы записи регистра 4, регистра 6, блока 24 регистров и вход синхронизации сумматора 20.

На каждом шаге работы устройства после записи в регистр 4 кода (очередной текущей вершины ) из блока 1 или

2 памяти осуществляется считывание новых данных. Если очередная текущая вершина имеет степень два, то иэ блока 2 памяти кода весов двух ребер подаются на информационный вход мультиплексора 6, коды двух вершин подаются на информационный вход Мультиплексора 17, а код первой иэ этих вершин — на второй вход схемы 11 сравнения на равенство, на первый вход которого из регистра 6 поступает код предшествующей вершины. С выхода этой схемы сигнал поступает на один информационный вход мультиплексора

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

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

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

1292000

18, и код вершины, инцидентной этому ребру.

Если текущая вершина не совпадает с начальной, то мультиплексор 115 пропускает на управляющие входы муль- 5 типлексоров 16 и 17 сигнал с выхода блока 11 в котором сравниваются ко" ды предшествующей вершины и первой вершины из блока 2 памяти. Если пер" вая вершина иэ блока 2 не совпадает с предшествующей вершиной, то на выходе мультиплексора 17 устанавливается ее код, а на выходе мультиплексора 16 " код веса ребра, инцидентного ей. В противном случае на выхо- 15 дах этих мультиплексоров устанавливаются соответственно код второй вершины из блока 2 памяти и код веса ребра, инцидентного ей.

I 20

По синхроимпульсу от генератора

23 к содержимому сумматора 20 прибавляется вес ребра с выхода мультиплексора 16, в регистр 6 и блок 24 регистров записывается код текущей вер- 25 шины из регистра 4, в который через мультиплексор 13 с выхода мультиплексора 17 записывается код следующей текущей вершины, Дпя того, чтобы при этой записи не происходило поте- 30 ри информации, необходимо в качестве регистров 6 и 4 и блока 24 использовать регистры, построенные на двойных триггерах, "сли текущая вершина имеет сте35 пень больше двух, то из блока 1 памяти считывается информация, записанная по адресу, старшими адресными разрядами которого является код текущей вершины, а младшими — соответ- 40 ствующая группа разрядов счетчика 18, выбираемая мультиплексором 14 по коду текущей вершины, поступающему на его управляющий вход. По синхроимпульсу от генератора 23 к содержимому сумматора 20 прибавляется вес выбранного ребра с первого выхода блока

1 памяти, в .регистр 6 и блок 24 ре— гистров записывается код текущей вершины из регистра 4, в который через мультиплексор 13 с второго выхода блока 1 памяти записывается код сле— дующей текущей вершины. Все это происходит, если код выбранной из блока 1 памяти веРшины не совпадает с кодом предшествующей вершины, что определяет блок 12 сравнения на равенство, и значение содержимого сумматора 20 не превосходит кода, хранимого в регистре 7, что регистрирует блок 2! сравнения на больше-меньше, Если хотя бы одно из этих событий происходит, то по сигналу с выхода элемента ИЛИ 22, на входы которого поступают сигналы с выхода блоков 12

I и 21, происходит обнуление сумматора 20, блока 24 регистров и регистра

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

9 сравнения на равенство, выходной сигнал которого также поступает на вход элемента ИЛИ 22. Но при этом происходит также запись в блок 3 из блока 24 регистров кодов всех вершин найденного пути, а иэ сумматора 20 веса этого пути по адресу, определяемому содержимым счетчика 19, которое при этом увеличивается на единицу, для установления следующего адреса, Таким образом, после полного пересчета всех значений счетчика 18 в блоке 3 будут записаны все пути в графе между начальной и конечной вершинами и их веса.

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

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

Составитель И. Загорбинина

Редактор В, Петраш Техред П.Сердюкова

Корректор В. Бутяга

Заказ 273/49 Тираж 673

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

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

Подписное

Производс.твенно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 выход которого подключен к первому информационному входу первого мультиплексора и к первому входу второго блока сравнения, выход которого соединен с первым информационным входом второго мультиплексора, выход которого подключен к управляющим входам третьего и четвертого мультиплексоров, выход которого соединен с входом управления записью первого блока памяти и с первым входом третьего блока сравнения, выход которого подключен к первому входу элемента ИЛИ, выход которого соединен с управляющим входом первого мультиплексора, входами сброса блока регистров, пер— ваго регистра, накапливающего сумматора и счетным входом первого счетчика, выход которого подключен к управляющим входам второго и пятого мультиплексоров, выход пятого муль— типлексора соединен с информационным входом первого блока памяти, первый выход которого подключен к информационному входу накапливающего сумматора, выход которого соединен с входом веса найденного пути блока регистрации и с первым входом четвертого блока сравнения, выход которого подключен к второму входу элемента ИЛИ, вход задания конечной вершины устройства соединен с информационным входом четвертого регистра, выход которого подключен к первому входу пятого блока сравнения, выход кото- 35 рого соединен с третьим вхо1ом элемента И. 1И и со счетным входом второго счетчика, выход которого подключен к входу количества пути блока pe— гистрации, второй выход первого блока памяти соединен с вторым информационным входом первого мультиплексора, выход которого подключен к информационному входу второго регистра, выход которого соединен с вторыми входами второго и пятого блоков сравнения, с информационными входами блока регистров, первого регистра, пятого, мультиплексора и с адресными входами первого и второго блоков памяти, первый выход которого подключен к информационному входу третьего мультиплексора, выход которого соединен с входом управления считыванием первого блока памяти, выход первого регистра подключен к второму входу третьего блока сравнения, второй выход второго блока памяти соединен с информационным входом четвертого мультиплексора и с вторым входом первого блока сравнения, выход которого подключен к второму информационному входу второго мультиплексора, входы сброса счетчиков объединены и являются входом сброса устройства, вход задания максимального веса пути которого соединен с информационным входом пятого регистра, выход которого соединен с вторым входом четвертого блока сравнения.