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

(22)Заявле с присоедини 7/Е 2 Ввудаувтиеыб канат СССР ав делан кзвбрвтввк и вткрнтв 11) УСТРОЙСТВО ДЛЯПУТЕЙ ЕДЕЛЕНИЯ ЮППЩАЛЬНЬГРАФАХ которых ледовательн дифференцирующей цепочкистолбцов в матричной модменты ИЛИ, входы которьмк выходам дифференцирукщиодноименной строки матрисети 21.Недостаток известногосостоит также в его чрезности при моделированиишинам которого соответст по числуели сети элеподключены цепочек ной мо устройст ерной сл рафов, в уют "вес работ, а дугам - информационные связи между работами. Кроме того, известное устройство обеспечивает лишь получение кода величины критического (минимального) пути для всего графа и не обеспечивает одновременного получения кодов величин минимальных путей для всех вершин графа.Необходимость в этом возникает,например, при решении задач планирования организации выполнения некоторого множества работ, представляеИзобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графиков.Известно устройство для определения минимального пути в графе, содержащее генератор тактовьм импульсов, блок управления, матрицу формирователей дуг, каждый из которых со" держит счетчик, элемент И и триггер,1 О по числу столбцов матричной модели элементы ИЛИ и триггеры 1,1.Недостаток известного устройства - его чрезмерная сложность при модели- ровании графов, вершинам которого соответствуют "веса 1 работ, а дугам - информационные связи между работами.Наиболее близким к предлагаемому. является устройство для определения экстремальных путей в графах, содержащее генератор тактовых импульсов, выход которого подключен к информационному входу элемента совпадения, матрицу формирователей дуг, каждый ержит цепочку из посоеднненных триггера имых сетевым графикам, В этом случае необходимо определение величины критических (минимальных) путей от произвоьной вершины графа до его конечной или (и) начальной вершины, не прибегая при этом к трудоемкому переходу от графа с нагруженными вершинами к графу с нагруженными дугами, как это предусмотрено в аналогичных устройствах. 1 ОЦель изобретения - повышение надежности устройства за счет сокращения аппаратурных затрат и расширение его функциональных воэможностей за счет определения величин минимальных 15 путей от любой вершины графа до его конечной или начальной вершины.Указанная цель достигается тем, что в устройство для определения минимальных путей в графах, содер жащее цепочки по числу строк и столбцов матричной модели сети из последовательно соединенных триггера и дифференцирующей цепочки, элементы ИЛИ по числу строк матричной модели се .ти, входы которых подключены к выходам дифференцирующих цепочек одноименных строк матричной модели сети, группу триггеров по числу столбцов матричной модели сети, первую и вторую группы ЗО элементов И по числу столбцов матричной модели сети, счетчики по числу столбцов матричной модели сети и генератор импульсов, введены группа элементов НЕ по числу столбцов матричной модели сети, группа регистрирующих счетчиков по числу столбцов матричной модели сети, элемент И-НЕ и элемент И, выход которого подключен к информационным входам элементов И первой и второй групп, управляющие входы которых соединены соответственно с выходами соответствующих триггеров группы и элементов НЕ одноименных столбцов матричной модели се 45 ти, выходы элементов ИЛИ подключены ко входам триггеров соответствующих столбцов матричной модели сети, выход каждого элемента И первой группы соединен со входом счетчика одноименного столбца матричной модели сети,50 выход каждого их которых подключен ко входам триггеров соответствующего столбца матричной модели сети, ко входу элемента НЕ одноименного столбца матричной модели сети и к соответствующему входу элемента И-НЕ, выход которого соединен с первым входом элемента И, второй вход которого 8860064подключен к выходу генератора импульсов, третий вход которого являетсявходом устройства, выход каждогоэлемента И второй группы соединенсо входом регистрирующего счетчикагруппы одноименного столбца матрич"ной модели сети.На чертеже представлена структур"ная схема устройства для определения минимальных путей в графах.Устройство содержит матричнуюмодель сети 1, которая состоит изтриггеров 2 1 с дифференцнрукщимицепочками 3 (1= 1,и, где пчисло вершин в моделирующем графе,группу триггеров 4, первую группусэлементов И 5, счетчики 6, группуэлементов НЕ 7, вторую группу элементов И 8, регистрирущцие счетчики 9, элемент И-НЕ О, элемент И11, генератор 12 тактовых импульсов, пусковой вход 13 и элементыИЛИ 4, при этом триггер 2 и диф;ференцирующая цепочка 3 образуютформирователь 5 дуг.Устройство работает следующимобразом,Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети) . При этом триггеры2 формирователей 15 дуг устанавливаются в единичное состояние, еслиесть информационная связь из 4 -ойвершины в-ую вершину, Соответствующий формирователь 15 1 определяется пересечением строки с номером1,( -ая вершина) и столбца с номером( "ая вершина), В счетчики б соответствующих вершин графа заносятсячисла импульсов, дополняющие "веса"вершин до полной емкости счетчиков,а счетчики 9 нахоцятся в сброшенномсостоянии. В нулевое .состояние устанавливаются также и все триггеры 4,за исключением триггера, номер которого соответствует номеру конечнойвершины (этот триггер устанавливается в единичное состояние) . При этомвсе триггеры 2 в строке, соответствующей конечной веошине матричной мо-дели, находятся в нулевом состоянии.С появлением пускового сигналана входе 13 элемента И 11 импульсыс выхода генератора 12 через элементИ 1 начинают поступать на входыэлементов И 5 и 8 групп. Однако первоначально счетные импульсы проходятчерез элементы И 8 на все регистрирующие счетчики 9 и только через те, 886006 011000000 0001 101 00 00001 1000 0000001 10 0000 000 0 0000001 10 00000000 000000001 000000000 3 ФТ =1, 2;где 31; -"вес"емого графа. элементы И 5, на управляемом входе которых имеется высокий потенциал с единичного выхода триггера 4. В начальный момент такой потенциал поступает только на элемент И 5, соответствующий конечной вершине.Отсчитав число импульсов, пропорциональное "весу" моделируемой вершины графа, соответствующий счетчик 6 переполняется, а сигнал переполнения с выхода счетчика 6 устанавливает в нулевое состояние все триггеры 2 в одноименном столбце матрицы. Одновременно высокий потенциал с выхода переполненного счетчика 6 подается на одноименный вход элемента И-НЕ 10 и элемент НЕ 7. Появление низкого потенциана на выходе элемента НЕ 7 (на управляемом входе элемента И 8) вызывает прекращение подачи счетных импульсов через элементы И 8 на вход регистра счетчика 9.Переброс триггеров 2 в одноименном столбце в нулевое состояние вызывает появление импульса через дифференцирующие цепочки 3 и через элементы ИЛИ 1 4 на входе триггера 4 очередного столбца, Этот импульс переводит триггер 4 в единичное сос, тояние, благодаря чему на управляемом входе элемента И 5 одноименного столбца появляется высокий пстенциал. Появление разрешающего потенциала на управляемом входе элемента И 5 обеспечивает возможность прохождения счетных импульсов черезэлемент И 5 на вход счетчика 6"веса" вершины) очередного столбцаматрицы. При этом формируется разрешение поступления счетчиков 6, изсоответствукицих вершин которых исхо-. дят дуги, приводящие в сформированную ранее вершину.Вычислительный процесс продолжается до тех пор, пока на выходахвсех счетчиков 6 не будут присутствовать высокие потенциалы, появляющиеся из-за переполнения счетчиков.Это свидетельствует о том, что всеузлы исследуемого графа сформированы.Наличие высоких потенциалов на выходах счетчиков 6 обеспечивает черезэлемент И-НЕ 10 прекращение подачисчетных импульсов с выхода генератора2 через элемент И 11 на входыэлементов И 5 и 8. Суммарное числоимпульсов, поступившее с выхода генератора 2 через элемент И 1 навходы счетчиков 9, соответствуют бкодам минимальных ( критических,)величин путей графа из данной (в томчисле и начальной) вершины до конечной вершины моделируемого графа сети,Работу устройства при определении минимальных путей в графе поясним на следующем примере. Пусть заданграф, описываемый матрицей смежностиА и вектором Т "весов" дуг, причем Ф 3;4;3;2;5,4;2, О, если нет дуги из1-ой вершины в 1-ую; 1, если есть дуга из 1-ой вершины в -ую.-ой вершины моделируПосле занесения исходной информации на управляемом входе триггера ЗФ 4, появляется высокий потенциал,поэтому после подачи пускового сигнала на вход 13 устройства счетные импульсы с выхода генератора 12 через элемент И 11 постунают на входы эле-д ментов И 5 и 8, а далее - на входывсех регистрирующих счетчиков 9, так как отсутствие сигнала переполнения на счетчиках 6 "весов" вершин обеспечивает наличие высокого потенциала с выходов элементов НЕ 7 (управляемых входов элементов И 8) и прохождение счетных импульсов на счетчики 9. Кроме того, счетные импульсы проходят через элемент И 510 на вход счетчика 61 . Через 10 =2, т.е. с приходом второго импульса, который заполняет до полной емкости счетчик 610, на управляемом входе элемента И 81 появляется низкий потенциал,.прекращается подача счетных импульсой на вход счетчика 90 . Одновременно сигнал переполнения счетчика 6,111 переводит триггеры 2 Ф 1 Ф и 29,0 в нулевое состояние, в результате чего М.с их выходов поступают импульсы напряжения через дифференцирующие цепочки 3 и элементы ИЛИ 148 и 14 р на входы триггеров 4 В и 4, Переброс тоиггеров 4 В и 4 ц обеспечивает подачу счетных импульсов через элементыИ 59 и 5 на счетчики 6 на бр "весов" вершины. С приходом шестого импульса переполняется счетчик 6, после чего прекращается подача счетныхимпульсов на счетчик 9 з н перебрасываются в нулевое состояние триггеры 2 у , 29и 2 у. Импульсы напряжения с выходов этих триггеров через дифференцирующие цепочки 3 и эле.менты ИЛИ 14, 14 и 146 перебрасывают триггеры 4,4 и 46 в единичноесостояние, тем самым обеспечиваетсяпоступление счетных импульсов черезэлементы И 5, 5 и 56 на счетчикиб,бу и бр и т.п.Вычислительный процесс заканчивается с приходом одиннадцатого импульса, после чего все счетчики б переполнены, и с .выхода элемента И-НЕ 10поступает низкий потенциал, поэтомупрекращается подача счетных импульсов с выхода генератора 12 через элемент И 11. Показания счетчиков 9 соответствуют минимальным величинам путей для каждой вершины графа до егоконечной вершины, при этом каждомуномеру вершины сопоставлен свой счетчик, В данном примере эти показания( начиная с первого) следунзцие: 10; 9, 11) 1 О; 9; 8) 7 б 2. 01 1000000 0001 1 1000 000101010 000000100 000000110 0000000 0 000000001 000000001 000000000 А = При определении минимальных путей из первой вершины до любой (в том числе и конечной) вершины графа исходную матрицу А нужно заносить в транспанированном виде относительно не главной диагонали, т.е. матри-, цу А Т =24 в, 5; 2 э Зэ 4 Зф 2 э, 13 По окончании работы устройства показания счетчиков 9 составляют 10, 10, 8; 6) бу 7 у 4, 3; 1. Таким образом, в предлагаемом устройстве для определения минимальных величин путей в графах значительно сокращаются аппаратурные затраты Ю ЗФ 33 ЗФ ЭЭ 4 Ф(приблизительно, с точностью до одного триггера, на(и -0)счетчиков, й которые заносятся числа импульсов, дополняющие "веса" вершин до полной емкости счетчиков) по сравнению с известным устройством.Формула изобретенияУстройство для определения минимальных путей в графах, содержащее цепочки по числу строк и столбцов матричной модели сети из последовательно соединенных триггера и дифференцирующей цепочки, элементы ИЛИ по числу строк матричной модели сети, входы которых подключены к выходам дифференцирующих цепочек одноименных строк матричной модели сети, группу триггеров по числу столбцов матричной модели сети, первую и вторую группы элементов И по числу столбцов матричной модели сети, счетчики по числу столбцов матричной модели сети и генератор импульсов, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности, в него введены группа элементов НЕ по числу столбцов матричной модели сети, группа регистрирующих счетчиков по числу столбцов матричной модели сети, элемент И-НЕ и элемент И, выход которого подключен к информационным входам элементов И первой группы и второй руппы, управляющие входы которых соединены соответственно с выходами соответствующих триггеров группы и элементов НЕ одноименных столбцов матричной модели сети, выходы элементов ИЛИ подключены ко входам триггеров соответствующих столбцов матричной модели сети, выход каждого элемента И первой группы соединен со входом счетчика одноименного столбца матричной модели сети, выход каждого из которых подключен ковходам триггеров соответствующего столбца матричной модели сети, ко входу элемента НЕ одноименного столбца матричной модели сети и к соответствующему входу элемента И-НЕ, выход которого соединен с первым входом элемента И, второй вход которого подключен к выходу генератора импульсов, третий вход которого является входом устройства, выход каждого элемента И второй группы соединен со входом регистрирующего счетчи9886006 ка группы одноименного столбца матричной модели сети. 1. Авторское В 525954, кл. С 2. Авторское У 640314, кл. 6 э (прототип), Составитель М. ДубининаМихеева Техред И. Гайду . Корректор Ред Пожо аказ 10560/78ВНИИПИ ираа 748осударственнам изобретениМосква, ЖПодписноео комитета СССРи открытийРаушская наб., д.4/5 по дел13035,Филиал ППП "Патент", г.узгород, ул.Проектная,Источники информации,принятые во внимание при экспертизе