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

Номер патента: 1292000

Авторы: Игнатьев, Петров, Сорокин

ZIP архив

Текст

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ СКОМУ СВИДЕТЕЛЬСТВУ(71) Ленинградский институтонного приборостроения(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛТЕЙ В ГРАФЕ(57) Иэобретение относится к вычислительной технике и может быть искпользовано для поиска всех возможныхпутей на транспортной сети, связывающих заданную пару станций. 1 ельюиэобретения является повышение точности при определении не только одного пути, но и всех возможных мелщуэаданными вершинами в граФе. Устройство содержит блоки 1, 2 памяти, регистры 4-8, блоки 9-2, 21 сравнениянакапливающий сумматор 20, счетчики18, 19, элемент ИЛИ 22, генератор 23импульсов, блок 24 регистров1 ил.Изобретение относится к гяычислительной технике а именно к моделирующим устройствам для определения путей между вершинами графа, и можетбыть использовано, например для поиска всех возможных путей на транспортной сети, связывающих заданнуюпару станций.Цель изобретения - повышение точности,1 ОНа чертеже приведена структурнаясхема предлагаемого устройства.Устройство для определения путейв графе содержит блоки 1 и 2 памяти,блок 3 регистрации, регистры 4-8,блоки 9-12 сравнения на равенство,мультиплексоры 13-17, счетчики 18 и19 накапливаюшего сумматора 20, блок21 сравнения на больше-меньше, элемент ИгИ 22, генератор 23 импульсови блок 24 регистров.Первый вход блока 1 памяти соединен с первыми входами блока 24 регистров (пути) и регистра 6 (предше 25ствующей вершины). Выход регистра 4(текущей вершины) подключен к первому входу блока 9 сравнения на равенство, второй вход которого соединен с выходом регистра 5 (конечнойвершины). Выход регистра 8 (начальной вершины) соединен с первыми входами блока 1 О сравнения на равенство и мультиплексора 13, выход которого подключен к первому входу регистра 4 (текущей вершины), выход которого подключен к первым входамблока 1 памяти и мультиплексоравходу блока 2 памяти и второму входублока 1 О сравнения на равенство, выход которого соединен с первым входом мультиплексора 15, второй входкоторого подключен к выходу блока 11сравнения на равенство.Первый вход блока 11 соединен с 45 первым входом блока 12 сравнения на равенство и выходом регистра 6 (предшествующей вершины), второй вход которого подключен к второму входу мультиплексора 13, первому входу сумматора 20, входу счетчика 18, выходу элемента ИЛИ 22 и второму входу блока 24 регистров (пути), выход которого соединен с первым входом блока 3. Второй вход блока 3 подключен к первому входу блока 21 сравнения на больше в мень и выходу сумматора 20, второй вход которого соединен с первым входом блока 1 памяти и выходом мультп 1 ггексора 6 первыи вход которого подключен к первому выходу блока 2 памяти.Второй выход блока 2 соединен свторым входом блока 11 сравнения наравенство и первым входом мультиплексора 17, второй вход которого годключен к второму входу мультиплексора 16 и выходу мультиплексора 15,третий вход которого соецинен с первым выходом счетчика 18, второй выход которого подключен к второму входу мультиплексора 14, выход которогосоединен с вторым входом блока 1 памяти,Выход мультиплексора7 подключен к третьему входу мультиплексора 13, второму входу блока 1 памяти и второму входу блока 12 сравнения на равенство, выход которого соединен с первым входом элемента ИЛИ 22, второй вход которого подключен к третьему входу блока 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 Если текущая вершина совпадает с начальной, то мультиплексор 15 пропускает на управляющие входы мультиплексоров 16 и 17 старший бит содержимого счетчика 18. Все разряды счетчика 17 разбиты на группы. Старший бит указывает код номера ребра иэ начальной вершины, если ее степень равна двум, а остальные группы разрядов указывают код номера ребра для вершин со степенью больше двух. Каждому коду такой вершины соответствует своя группа разрядов счетчика 18. Полным пересчетом всех значений счетчика 18 осуществляется полный перебор всех основных подграфов, которые могут содержать путь между заданными вершинами. Таким образом, на выходах мультиплексоров 16 и 17 устанавливаются соответственно код веса ребра из начальной вершины, выбранной по старшему биту счетчика равно длине кода вершин. 1 ервый его вход является входом дапгых, второй - обнуления, третий - записи данных со сдвигом хранящихся данных.Мультиплексоры 13 и 5-17 осуществляют выбор одного слова из двух поступающих слов в зависимости от управляющего сигнала. В мультиплексорах 16 и 17 оба поступающих слова подаются по первому входу (одна по ловина разрядов шины используется под одно слово, другая - под другое), а в мультиплексоре 14 все поступающие слова подаются по второму входу. В мультиплексоре 15 осуществляется выбор одного иэ двух поступающих одноразрядных слов.Устройство работает следующим образом. 20Предварительно в блоки 1 и 2 памяти заносится информация о графе: в блок 1 - информация о ребрах, инцидентных вершинах со степенью больше двух, в блок 2 - информация о ребрах, инцидентных вершинах со степентю два. Если у вершины степень единица, то инцидентное ей ребро указывается дважды. Информация в блоки памяти записывается следующим образом. 30 В блоке 1 памяти по адресу, старшими адресными разрядами которого является код вершины, а младшими - код номера ребра, записывается код смежной по этому ребру вершины и вес этого 35 ребра. В блоке 2 памяти по адресу, являющемуся кодом вершины, записываются коды двух смежных вершин и веса двух инцидентных ребер соответственно. Коды вершин выбирают таким обра зом, чтобы в каждый момент времени был активирован только один из блоков 1 и 2 памяти.Перед началом работы в регистры 5 и 8 записываются коды конечной и 45 начальной вершин соответственно, После этого обнуляется регистр 7, в результате чего единичный сигнал с выхода блока 21 сравнения на больше- меньше через элемент ИЛИ 22 поступа ет на второй (управляющий) вход мультиплексора 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, а на управляющий вход - сигнал с выхода блока 1 О, в котором сравниваются коды начальной и текущей вершин.18, и код вершины, инцидентной этомуребру.Если текущая вершина не совпадаетс начальной, то мультиплексор 115пропускает на управляющие входы мультиплексоров 16 и 7 сигнал с выходаблока 11, в котором сравниваются ко"ды предшествующей вершины и первойвершины из блока 2 памяти. Если пер"вая вершина иэ блока 2 не совпадаетс предшествующей вершиной, то на выходе мультиплексора 17 устанавливается ее код, а на выходе мультиплексора 16 " код веса ребра, инцидентного ей. В противном случае на выходах этих мультиплексоров устанавливаются соответственно код второй вершины из блока 2 памяти и код весаребра, инцидентного ей.20По синхроимпульсу от генератора23 к содержимому сумматора 20 прибавляется вес ребра с выхода мультиплексора 16, в регистр 6 и блок 24 регистров записывается код текущей вершины из регистра 4, в который черезмультиплексор 13 с выхода мультиплексора 7 записывается код следующей текущей вершины, Дпя того, чтобыпри этой записи не происходило потери информации, необходимо в качестверегистров 6 и 4 и блока 24 использовать регистры, построенные на двойных триггерах,"сли текущая вершина имеет сте 35пень больше двух, то из блокапамяти считывается информация, записанная по адресу, старшими адреснымиразрядами которого является код текущей вершины, а младшими - соответствующая группа разрядов счетчика 18,выбираемая мультиплексором 14 по коду текущей вершины, поступающему наего управляющий вход. По синхроимпульсу от генератора 23 к содержимому сумматора 20 прибавляется вес выбранного ребра с первого выхода блока1 памяти, в регистр 6 и блок 24 регистров записывается код текущей вершины из регистра 4, в который черезмультиплексор 13 с второго выходаблока 1 памяти записывается код следующей текущей вершины. Все это происходит, если код выбранной из блока 1 памяти вершины не совпадает скодом предшествующей вершины, чтоопределяет блок 12 сравнения на равенство, и значение содержимого сумматора 20 не превосходит кода, хранимого в регистре 7, что регистрирует блок 2 сравнения на больше-меньше,Если хотя бы одно из этих событий происходит, то по сигналу с выхода элемента ИИ 22, на входы которого поступают сигналы с выхода блоков 12 и 21, происходит обнуление сумматора 20, блока 24 регистров и регистра 6, увеличение на единицу содержимого счетчика 8, переход тем самым к рассмотрению следующего основного подграфа и запись в регистр 4 кода начальной вершины из регистра 8 через мультиплексор 3 при поступлении синхроимпульса, То же происходит и в том случае, если код очередной текущей вершины совпадает с кодом конечной вершины, что определяет блок 9 сравнения на равенство, выходной сигнал которого также поступает на вход элемента ИЛИ 22. Но при этом происходит также запись в блок 3 из блока 24 регистров кодов всех вершин найденного пути, а иэ сумматора 20 веса этого пути по адресу, определяемому содержимым счетчика 19, которое при этом увеличивается на единицу, для установления следующего адреса. Таким образом, после полного пересчета всех значений счетчика 18 в блоке 3 будут записаны все пути в графе между начальной и конечной вершинами и их веса.Формула изобретенияУстройство для определения путей в графе, содержащее регистры, счетчики, накапливающий сумматор, блок регистров, блок индикации, первый блок памяти, генератор импульсов и первый блок сравнения, первый вход которого соединен с выходом первого регистра, отличающееся тем, что, с целью повышения точности, в него введены мультиплексоры, элемент ИЛИ, четыре блока сравнения и второй блок памяти, вход запуска генератора импульсов является входом запуска устройства, выход генератора импульсов подключен к входам синхронизации первого и второго регистров, накапливающего сумматора и блока регистров, выход которого соединен с входом вершин найденного пути блока регистрации, вход задания начальной вершины устройства подключен к информационному входу третьего регистра,1292000 Составитель И. ЗагорбининаРедактор В, Петраш Техред Л.Сердюкова Корректор В, Бутяга Заказ 273/49 Тираж 673 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Подписное Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 выход которого подключен к первомуинформационному входу первого мультиплексора и к нерному входу второгоблока сравнения, выход которого соединен с первым информационным входомвторого мультиплексора, ныход которого подключен к управляющим входамтретьего и четвертого мультиплексоров, выход которого соединен с входом управления записью первого блока 10памяти и с первым входом третьегоблока сравнения, выход которого подключен к первому входу элемента ИЛИ,выход которого соединен с управляющим входом первого мультиплексора, 15входами сброса блока регистров, первого регистра, накапливающего сумматора и счетным входом первого счетчика, выход которого подключен к управляющим входам второго и пятого 20мультиплексорон, выход пятого мультиплексора соединен с информационнымвходом первого блока памяти, первыйвыход которого подключен к информационному входу накапливающего сумматора, выход которого соединен с входом веса найденного пути блока регистрации и с первым входом четвертогоблока сравнения, выход которого подключен к второму входу элемента ИЛИ,вход задания конечной вершины устройства соединен с информационнымвходом четвертого регистра, выходкоторого подключен к первому входупятого блока сравнения, выход кото рого соединен с третьим входом элемента И 11 И и со счетным входом второго счетчика, выход которого подключен к входу количества пути блока ре -гистрации, второй выход первого блока памяти соединен с вторым информационным входом первого мультиплексора, выход которого подключен к информационному входу второго регистра,выход которого соединен с нторымивходами второго и пятого блоков сравнения, с информационными входами блока регистров, первого регистра, пятого.,мультиплексора и с адреснымивходами первого и второго блоков памяти, первый выход которого подключен к информационному входу третьегомультиплексора, выход которого соединен с входом управления считываниемпервого блока памяти, выход первогорегистра подключен к второму входутретьего блока сравнения, второй выход второго блока памяти соединен синформационным входом четвертогомультиплексора и с вторым входом первого блока сравнения, выход которогоподключен к второму информационномувходу второго мультиплексора, входысброса счетчиков объединены и являются входом сброса устройства, входзадания максимального веса пути которого соединен с информационным входом пятого регистра, выход которогосоединен с вторым входом четвертогоблока сравнения.

Смотреть

Заявка

3771629, 18.07.1984

ЛЕНИНГРАДСКИЙ ИНСТИТУТ АВИАЦИОННОГО ПРИБОРОСТРОЕНИЯ

ИГНАТЬЕВ МИХАИЛ БОРИСОВИЧ, ПЕТРОВ ВЛАДИСЛАВ ИВАНОВИЧ, СОРОКИН ВЛАДИМИР ЕВГЕНЬЕВИЧ

МПК / Метки

МПК: G06F 15/173

Метки: графе, путей

Опубликовано: 23.02.1987

Код ссылки

<a href="https://patents.su/5-1292000-ustrojjstvo-dlya-opredeleniya-putejj-v-grafe.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для определения путей в графе</a>

Похожие патенты