Устройство для определения путей в графе Советский патент 1987 года по МПК G06F15/173 

fO

15

20

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

Цель изобретения - повыше 1ие точности.

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

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

Первый вход блока 1 памяти соединен с первыми входами блока 24 регистров (пути), и регистра 6 (предше ствующей вершины). Выход регистра 4 (текущей вершины) подключен к первому входу блока 9 сравнения на ра- венс во, второй вход которого соединен с выходом регистра 5 (конечной

.эп

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

45

25

40

Первый вход блока 11 соединен с первым входом блока 12 сравнения на равенство и выходом регистра 6 (пред- шествую1цей верщины) , второй вход которого подключен к второму входу мультиплексора 13, первому входу сум-50 блока 1 памяти составляют его шину матора 20, входу счетчика 18, выходу адреса. Программирование блоков 1

мультип тексора 16, первый нход кот рого подключен к первому выходу бл ка 2 памяти.

Второй выход блока 2 соедиЕ ен с вторым входом блока 11 сравнения н равенство и первым входом мультипл сора 17, второй вход которого подключен к второму входу мультиплекс ра 16 и выходу мультиплексора 15, третий вход которого соединен с пе вым выходом счетчика 18, второй БЫ ход которого подключен к второму в ду мультиплексора 14, выход которо соединен с вторым входом блока 1 п мяти. I

Выход мультиплексора 17 подключ к тpeтьe fy входу мультиплексора 13 второму входу блока 1 памяти и вто му входу блока 2 сравнения на равенство, выход которого соединер с первым входом элег-1ента ИЛИ 22, вто рой вход которого подключен к трет му входу блока 3, выходу блока 9 сравнения на равенство и входу сче чика 19, выход которого соединен с четвертым входом блока 3. Выход сх мы 2I сравнения на больше-меньше по ключен к третьему входу элемента И 22. Вых-од генератора 23 импульсов соединен с вторым входом регистра (теку1чей вериины) и третьими входа блока 24 регистров (пути), третьег регистра 6 (предшествующей вершины и сумматора 20. Второй вход схемы 2 сравнения на больше-меньше подключ к выходу регистра 7 (максимального веса).

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

Блоки 1 и 2 памяти выполняются на ПИЗУ, шина данных которых распре деляется между первым и вторым выхо дами этих блоков, вход блока 2 памя ти, является шиной адреса, а входы

элемента ИЛИ 22 и второму входу блока 24 регистров (пути), выход которого соединен с первым входом блока 3. Второй вход блока 3 подключен к пер- вому входу блока 21 сравнения на больше-меньше и выходу сумматора 20, второй вход которого соединен с первым входом блока 1 памяти и выходом

5

0

п

5

5

5

0

0 блока 1 памяти составляют его шину адреса. Программирование блоков 1

мультип тексора 16, первый нход которого подключен к первому выходу блока 2 памяти.

Второй выход блока 2 соедиЕ ен с вторым входом блока 11 сравнения на равенство и первым входом мультиплексора 17, второй вход которого подключен к второму входу мультиплексора 16 и выходу мультиплексора 15, третий вход которого соединен с первым выходом счетчика 18, второй БЫ- ход которого подключен к второму входу мультиплексора 14, выход которого соединен с вторым входом блока 1 памяти. I

Выход мультиплексора 17 подключен к тpeтьe fy входу мультиплексора 13, второму входу блока 1 памяти и второму входу блока 2 сравнения на равенство, выход которого соединер с первым входом элег-1ента ИЛИ 22, второй вход которого подключен к третьему входу блока 3, выходу блока 9 сравнения на равенство и входу счетчика 19, выход которого соединен с четвертым входом блока 3. Выход схе мы 2I сравнения на больше-меньше подключен к третьему входу элемента ИЛИ 22. Вых-од генератора 23 импульсов соединен с вторым входом регистра 4 (теку1чей вериины) и третьими входами блока 24 регистров (пути), третьего регистра 6 (предшествующей вершины) и сумматора 20. Второй вход схемы 21 сравнения на больше-меньше подключен к выходу регистра 7 (максимального веса).

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

Блоки 1 и 2 памяти выполняются на ПИЗУ, шина данных которых распределяется между первым и вторым выходами этих блоков, вход блока 2 памяти, является шиной адреса, а входы

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

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

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

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

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

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

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

JO

t5

20

30

35

0

40

S

5

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

Генератор 23 импульсов выр- баты- вает синхронизирующие импульсы, которые подаются ча входы записи регистра 4, регистра 6, блока 24 регистров и вход синхронизации сумматора 20. На каждом шаге работы устройства после записи в регистр 4 кода (очередной текущей вершины) из блока 1 или 2 памяти осуществляется считывание .новых данных. Если очередная текущая вершина имеет степень два, то из блока 2 памяти кода весов двух ребер подаются на информационный вход мультиплексора 6, коды двух вершин подаются на информационный вход Мультиплексора 17, а код первой из этих вершин - на второй вход схемы 11 сравнения на равенство, на первый вход которого из регистра 6 поступаГет код предшествующей вершины. С выхода этой схемы сигнал поступает на один информационный вход мультиплексора 15, на другой информационньш вход которого подается старший бит содержимого счетчика 18, а на управляющий вход - сигнал с выхода блока 10, в котором сравниваются коды начальной и текущей вершин.

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

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

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

Если хотя бы одно из этик соб происходит, то по сигналу с выхо элемента ИЛИ 22, на входы которо поступают сигналы с выхода блоко и 21, происходит обнуление сумма ра 20, блока 24 регистров и реги 6, увеличение на единицу содержи счетчика 18, переход тем самым к смотрению следующего основного п графа и запись в регистр 4 кода чальной вершины из регистра 8 че

ного ей. В противном случае на выхо- -5 мультиплексор 13 при поступлении

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

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

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

текущая вершина имеет степень больше двух, то из блока 1 памяти считывается информация, записанная по адресу, старшими адресными разрядами которого является код текущей вершины, а младшими - соответствующая группа разрядов счетчика 18 выбираемая мультиплексором 14 по коду текущей вершины, поступающему на его управляющий вход. По синхроимпульсу от генератора 23 к содержимому сумматора 20 прибавляется вес выбранного ребра с первого выхода блока I памяти, в регистр 6 и блок 24 регистров записывается код текущей вершины из регистра 4, в который через мультиплексор 13 с второго выхода блока 1 памяти записывается код следующей текущей вершины. Все это происходит, если код выбранной из блока 1 памяти вершины не совпадает с кодом предшествую1 ;ей вершины, что определяет блок 12 сравнения на равенство, и значение содержимого сум матора 20 не превосходит кода, хра

нимого в регистре 7, что регистрирует блок 21 сравнения на больше-меньше .

Если хотя бы одно из этик событий происходит, то по сигналу с выхода элемента ИЛИ 22, на входы которогр поступают сигналы с выхода блоков 12 и 21, происходит обнуление сумматора 20, блока 24 регистров и регистра 6, увеличение на единицу содержимого счетчика 18, переход тем самым к рассмотрению следующего основного подграфа и запись в регистр 4 кода чальной вершины из регистра 8 через

мультиплексор 13 при поступлении

0

5

0

5

Q

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

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

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

0

5

}5ыход которого пол;ключен к nppBO fy информационному входу первого мультиплексора и к первому вхолу второг-о блока сравнения, выхох которого соединен с первым информационным входом второго мультиплексора, выход которого подключен к управляющим входам третьего и четйертого мультиплексоров, выход которого соединен с входом управления записью первого блока памяти и с первым входом третьего блока сравнения, выход которого подключен к первому входу элемента ИЛИ, выход которого соединен с управляющим входом первого мультиплексора, входами сброса блока регистров, первого регистра, накапливающего сумматора и счетным входом первого счетчика, выход которого подключен к управляющим входам второго и пятого ьгультиплексоров, выход пятого мультиплексора соединен с информационным входом первого блока памяти, первый выход которого подключен к информационному входу накапливающего сумматора, выход которого соединен с входом веса найденного пути блока регистрации и с первым входом четвертого блока сравнения, выход которого подключен к второму входу элемента ИЛИ, вход задания конечной вершины устройства соединен с информационным входом четвертого регистра, выход которого подключен к первому входу пятого блока сравнения, выход кото-

Редактор В. Петраш

Составитель И. Загорбинина Техред Л.Сердюкова

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, )1{-35, Раушская наб. , д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

O

5

5

0

5

рого соединен с третьим нxoдo t элемента ИЛИ и со счр-тным входом второго счетчика, выход которого подключен к входу количества пути блока регистрации, второй выход первого блока памяти соединен с вторым информационным входом первого мультиплексора, выход которого подключен к информационному входу второго регистра, выход которого соединен с вторыми входами второго и пятого блоков сравнения, с информационными входами блока регистров, первого регистра, пятого ..мультиплексора и с адресными входами первого и второго блоков памяти, первый выход которого подключен к информационному входу третьего мультиплексора, выход которого соединен с входом управления считыванием первого блока памяти, выход первого регистра подключен к второму входу третьего блока сравнения, второй выход второго блока памяти соединен с информационным входом четвертого мультиплексора и с вторым входом первого блока сравнения, выход которого подключен к второму информационному входу второго мультиплексора, входы сброса счетчиков объединены и являются входом сброса устройства, вход задания максимального веса пути которого соединен с информационным входом пятого регистра, выход которого соединен с вторым входом четвертого блока сравнения.

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

Подписное

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