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

 

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

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

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

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

Цель изобретения сокращение времени определения путей экстремальной пропускной способности.

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

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

Устройство содержит модель графа 1 из верхней наддиагональной матрицы моделей дуг 2_i,k, i 1, 2, n 1, k 2, 3, n, каждая из которых состоит из ключа 3 и элемента 4 индикации, группу регистров 5_i,k, i 1, 2, n 1, k 2, 3, n, каждый из которых включает элемента ИЛИ 7j, j 1, 2, m, элемент ИЛИ-НЕ 8₁, элемент ИЛИ 8j, j 2, 3, m, элементы И 9j, j 1, 2, m, триггер 10, элемент И 11, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 12, j, j 1, 2, m (n количество вершин в исследуемом графе, m разрядность используемых регистров). Кроме того цифровые обозначения на схеме имеют вход 13 запуска устройства, тактовый вход 14, вход 15 возврата в исходное и признаковый выход 16 устройства.

Работа устройства основана на последовательном включении моделей дуг в порядке возрастания (убывания) пропускных способностей d_i,k до момента, когда включение одной или нескольких из них не обеспечит составления с ранее включенными путь (пути) из начальной вершины в конечную вершину графа. Перед определением пути с минимальной пропускной способностью в регистры 5_i,k вводится значение V_i,k, равное или пропорциональное значениям d_i,k, если i, k-тая дуга есть в исследуемом графе, и значение V_i,k, равное емкости регистров, если i, k-той дуги нет.

Решение начинается подачей сигнала уровня логической единицы на вход 13 запуска устройства и тактовых импульсов на тактовый вход 14 устройства. При этом сигнал с входа 13 запуска поступает на объединенные информационные входы ключей 3 моделей дуг 2_j,k, k 2, 3, n и считывающие входы регистров 5_i,k, i 1, 2, n 1, k 2, 3, n. С информационных выходов регистров значения V_i поступают на входы соответствующих элементов выбора 6_i,k, i 1, 2, n 1, k 2, 3, n. Содержание j-го разряда в каждом элементе выбора поступает на вход элемента ИЛИ 7j, с выхода элемента 7j оно поступает на вход элемента И 9j и соответствующий вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 12j. При этом, если в j-м разряде всех регистров содержится единица, то на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 12j будет нулевой сигнал, который поступает на другие входы элементов И 9j всех элементов выбора, чем моделируется неразличимость чисел. Аналогично будет, если в j-том разряде всех регистров содержится 0. Если же в j-том разряде регистров содержится как 1, так и 0, то на выходе 12j будет сигнал уровня логической единицы, который, поступая на входы элементов И 9j, приведет к появлению сигнала уровня логической единицы на выходе тех из них, на другой вход которых поступает 1 с информационного входа элемента выбора. Сигнал с выхода этих элементов И 9j поступит на вход элемента ИЛИ 8j, а с его выхода по цепи элементов ИЛИ 8_j-1, 8_j-2 на вход элемента ИЛИ-НЕ 8₁. Этим моделируется исключение из числа альтернативных соответствующей данному элементу выбора модели дуги. Таким образом, в результате сравнения содержимого регистров нулевые сигналы будут на обоих входах элементов ИЛИ-НЕ 8₁ только тех элементов выбора 6_i,k, на вход которых поступают минимальные значения V_i,k. Сигнал уровня логической единицы с выхода этих элементов ИЛИ-НЕ поступает на единичный вход триггера 10 этих элементов выбора через время, достаточное для выбора минимального элемента, единичный сигнал с тактового входа 14 поступает через элемент И 11 на объединенные тактовые входы триггеров 10 всех элементов выбора. При этом те из них, на единичный вход которых поступает единичный сигнал с выхода элемента ИЛИ-НЕ, переходит в единичное состояние. Сигнал с единичного выхода триггера 10 поступает на управляющий вход ключа 3 соответствующей модели дуги и объединенные входы элементов ИЛИ 7m, 8m этого элемента выбора. Во "включенной" модели дуги при этом информационной цепью ключа 3 вход дуги соединяется с входом элемента 4 индикации. Поступление единичного сигнала на элементы ИЛИ 7m, 8m обеспечивает моделирование исключения из числа альтернативных уже "включенной" дуги.

Дальнейшее решение будет аналогично. Наконец, по мере "включения" все большего числа моделей дуг включение одной или нескольких из них обеспечит составление с некоторыми из ранее включенных путь из начальной вершины в конечную вершину графа. При этом создается цепь от входа 13 через информационные цепи ключей 3 и элементов 4 индикации, "включенных" и принадлежащих пути с минимальной пропускной способностью моделей дуг с инверсным входом элемента И 11 и признаковым выходом 16. Появление сигнала на выходе 16 свидетельствует об окончании решения, а "говорящие" элементы индикации идентифицируют дуги, принадлежащие соответствующему пути (путям). Поступление сигнала на инверсный вход элемента И 11 исключает прохождение через него тактовых импульсов и ложные "включения" других моделей дуг.

Аналогичным образом работает устройство и при определении пути с максимальной пропускной способностью за тем отличием, что перед решением в регистры 6_i,k вводятся значения N V_i,k, если дуга ik есть в моделируемом графе.

Таким образом предложенное устройство обеспечивает за R тактов (1 < R < 0,5n(n-1) определение путей экстремальной пропускной способности, тогда как известное устройство может потребовать значительно большего числа тактов для "включения" только одной дуги, что существенно повышает быстродействие.

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

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ ГРАФА, содержащее модель графа из верхней наддиагональной матрицы моделей дуг, каждая из которых состоит из ключа и элемента индикации, информационные входы ключей объединены по строкам матрицы модели графа, а выходы ключей соединены с входами элементов индикации, выходы которых объединены по столбцам матрицы и соединены с управляющими входами ключей соответствующей строки матрицы, объединенные управляющие входы ключей первой строки соединены с входом запуска устройства, а объединенные выходы элементов индикации последнего столбца матрицы - с признаковым выходом устройства, отличающееся тем, что в него введены группа регистров и элементы выбора по числу моделей дуг, элемент И и m элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (m - разрядность регистров), каждый элемент выбора содержит триггер, первую группу из элементов ИЛИ, элемента ИЛИ - НЕ и элемента И и группы со 2 по m из первого и второго элементов ИЛИ и элемента И, при этом считывающие входы регистров группы соединены с входом запуска устройства, а их информационные выходы соединены с информационными входами разрядов соответствующих элементов выбора, в каждом из которых j-тый информационный разряд соединен с входом первого элемента ИЛИ j-той группы, выход первого элемента ИЛИ соединен с первым входом элемента И этой же группы и соответствующим входом j-того элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вторые входы элементов И j-тых групп объединены у всех элементов выбора и соединены с выходом j-того элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход элемента И первой группы соединен с первым входом элемента ИЛИ-НЕ, второй вход которого объединен с входом элемента ИЛИ этой группы и соединен с выходом второго элемента ИЛИ второй группы, выходы элементов И остальных групп соединены с первым входом вторых элементов ИЛИ этих групп, вторые входы которых объединены с первым входом первого элемента ИЛИ этих групп и соединены с выходом второго элемента ИЛИ соответственно последующих групп, а объединенные вторые входы первого и второго элементов ИЛИ m-той группы соединены с единичным выходом триггера и с управляющим входом ключа соответствующей модели дуги, тактовые входы триггеров соединены с выходом элемента И, прямой вход которого соединен с тактовым входом устройства, а инверсный вход - с выходами элементов индикации последнего столбца матрицы модели графа, единичные входы триггеров соединены с выходами элементов ИЛИ - НЕ соответствующих элементов выбора, а нулевые входы триггеров объединены и соединены с входом возврата устройства в исходное состояние.

РИСУНКИ

Рисунок 1