Устройство для решения задач на графах

 

Устройство относится к вычислительной технике и может быть использовано для определения состава и веса критических путей в орграфе без петель. Задача - повышение быстродействия при определении дерева критических путей и веса критического пути в орграфе без петель, а также расширение функциональных возможностей за счет исследования как минимальных, так и максимальных путей. Задача решается тем, что в устройстве исследование критических путей ведется путем сложения ненулевых весов дуг с последующим отбрасыванием не экстремальных значений, т.е. вычисления производятся по формулам a_m=min(a_k+a_km) или a_m= max(a_k+a_km), где a_km - вес (KM)-ой дуги; a_k - минимальный или максимальный суммарный вес K-ой вершины, а в блоке формирования критических маршрутов задано дерево критических путей. При решении задач на сетях минимальный суммарный вес каждой вершины можно рассматривать как ранний момент начала соответствующего события. 8 ил.

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

Известно устройство для решения задач на графах [1] содержащее блок задания матрицы смежности, блок определения дерева критических путей и блок определения кратчайшего маршрута, причем, вход пуска устройства подключен ко входу пуска блока определения дерева критических путей, выход значения (K. M)-го элемента блока задания матрицы смежности подключен ко входу наличия (K. M)-го дуги блока определения дерева критических путей, K-ый вход задания начальной вершины пути которого является одноименным входом устройства, M-ый вход задания конечной вершины пути которого подключен к одноименному входу блока определения дерева критических путей и к одноименному входу блока определения кратчайшего маршрута, выход признака принадлежности (K. M)-й дуги множеству дуг кратчайшего маршрута которого является выходом признака принадлежности (K. M)-й дуги множеству дуг критического пути устройства, вход задания режима исполнения K-й вершины устройства подключен к одноименному входу блока определения дерева критических путей, выход признака принадлежности (K. M)-й дуги дереву критических путей и выход признака окончания моделирования конечной вершины пути которого подключен ко входу признака принадлежности (K. M)-й дуги дереву критических путей и входу опроса конечной вершины блока определения кратчайшего пути, причем, блок определения дерева критических путей содержит коммутатор, многоканальный счетчик, накапливающий узел логического сложения, узел определения исходящих дуг, многоканальный таймер и узел синхронизации, причем, вход пуска блока определения дерева критических путей подключен ко входу пуска блока синхронизации, первый, второй и третий выходы которого подключены соответственно к тактовому входу, входу установки в "О" признаков и к входу опроса многоканального таймера, выход признака преполнения в K-м канале M-й группы которого является признаком принадлежности (KM)-й дуги дереву критических путей блока определения дерева критических путей, M-ый вход задания конечной вершины подключен к M-му входу коммутатора, выход которого является признаком окончания моделирования, вход задания исполнения K-й вершины и K-ый вход задания начальной вершины пути которого подключены ко входу выбора направления коммутации по K-му разряду информационного входа и к выходу установки в "1" K-го разряда накапливающего узла логического сложения, M-ый разряд информационного выхода которого подключен к M-му информационному входу коммутатора, к входу останова каналов M-й группы и к входу запрета обнуления признаков M-й группы каналов многоканального таймера, выход признака преполнения которого подключен к M-му разряду первого информационного входа накапливающего узла логического сложения и к суммирующему входу K-го канала многоканального счетчика, выход признака преполнения K-го канала которого подключен к K-му разряду второго информационного входа накапливающего узла логического сложения, выход признака наличия (KM)-й дуги блока определения дерева критических путей подключен к одноименному входу узла определения исходящих ветвей.

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

Прототипом изобретения является устройство решения задач на графах [2] содержащее многоканальный блок регистрации, многоканальный блок выбора минимума, многоканальный накапливающий блок формирования маршрутов, блок выбора минимума и блок синхронизации, причем вход задания веса (KM)-го ребра графа устройства (K 1,B, M 1,B, где B количество вершин в графе) подключен к одноименному входу многоканального накапливающего блока формирования маршрута, выход состава маршрутов M-й группы которого подключен к информационному входу M-го канала многоканального блока регистрации, вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу многоканального накапливающего блока формирования маршрутов, второй выход блока синхронизации подключен к входу опроса блока выбора минимума, M-й выход позиции минимума которого подключен к входу признака записи M-го канала многоканального блока регистрации, информационный выход K-го канала которого является выходом состава кратчайшего пути в K-ю вершину графа устройства и подключен к входам задания состава маршрута K-х каналов всех групп, выход веса маршрута K-го канала M-й группы которого подключен к K-му информационному входу M-го канала многоканального блока выбора минимума, K-й выход позиции минимума M-го канала которого подключен к входу опроса состава маршрута M-й группы, информационный выход M-го канала многоканального блока выбора минимума подключен к M-му информационному входу блока выбора минимума.

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

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

Задача решается тем, что в устройство, содержащее многоканальный блок регистрации, многоканальный накапливающий блок формирования маршрутов и блок синхронизации, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу многоканального накапливающего блока формирования маршрутов, дополнительно вводят блок задания матрицы весов дуг, многоканальный суммирующий блок, блок выбора экстремального значения и счетчик, причем, M-я группа выходов значения веса (KM)-й дуги (где K 1,B, M 1,B, а B число вершин в графе) блока задания матрицы весов дуг соединена с M-й группой первого информационного входа многоканального суммирующего блока, второй информационный вход и M-й канал информационного выхода которого соединены соответственно со вторым информационным выходом блока выбора экстремального значения и с M-м каналом информационного входа многоканального блока регистрации, K-я группа информационного выхода которого соединена с K-й группой информационного входа блока выбора экстремального значения, M-й канал выхода значения веса критического пути от начальной до M-й вершины графа которого соединен с M-м каналом первого информационного входа многоканального накапливающего блока формирования маршрутов, (KM)-й выход и второй информационный вход которого соединены соответственно с выходом признака принадлежности (KM)-й дуги критическому пути и с K-й группой информационного выхода многоканального блока регистрации, второй, третий и четвертый выходы блока синхронизации соединены соответственно с тактовыми входами многоканального суммирующего блока, блока выбора экстремального значения и счетчика, информационный выход которого соединен с входами задания номера моделируемой вершины многоканального суммирующего блока, блока выбора экстремального значения, многоканального блока регистрации и первым входом блока синхронизации, второй информационный вход которого является входом задания числа вершин графа, причем вход задания режима работы и вход задания номера исследуемой вершины являются соответственно одноименными входами блока выбора экстремального значения и многоканального накапливающего блока формирования маршрутов.

На фиг. 1 изображена структурная схема устройства решения задач на графах; на фиг. 2 функциональная схема блока задания матрицы весов дуг; на фиг. 3 функциональная схема многоканального суммирующего блока; на фиг. 4 - функциональная схема блока регистрации; на фиг. 5 -функциональная схема блока выбора экстремального значения; на фиг. 6 функциональная схема многоканального накапливающего блока формирования маршрутов; на фиг. 7 - функциональная схема блока синхронизации; на фиг. 8, а-г последовательность по определению критических путей.

Устройство для решения задач на графах (фиг. 1) содержит блок задания матрицы весов дуг 1, многоканальный суммирующий блок 2, многоканальный блок регистрации 3, блок выбора экстремального значения 4, многоканальный накапливающий блок формирования маршрутов 5, блок синхронизации 6 и счетчик 7, причем, входы задания значения веса (KM)-й дуги (где K 1,B, M 1,B, а B - число вершин в графе) графа 8 и 9 устройства являются соответственно входом записи значения веса дуг, заходящих в M-е вершины и входом разрешения записи значения веса дуг, выходящих из K-х вершин блока задания матрицы весов дуг 1, вход задания режима работы 10 и вход задания номера исследуемой вершины 11 являются соответственно одноименными входами блока выбора экстремального значения 4 и многоканального накапливающего блока формирования маршрутов 5, вход пуска устройства 12 подключен к входу пуска блока синхронизации 6, второй информационный вход которого является входом задания числа вершин графа 13, а первый выход подключен к тактовому входу многоканального накапливающего блока формирования маршрутов 5, M-я группа выходов значения веса (КМ)-й дуги блока задания матрицы весов дуг 1 соединена с M-й группой первого информационного входа моногоканального суммирующего блока 2, второй информационный вход и M-й канал информационного выхода которого соединены соответственно со вторым информационным выходом блока выбора экстремального значения 4 и с M-м каналом информационного входа многоканального блока регистрации 2, K-я группа информационного выхода которого соединена с K-й группой информационного входа блока выбора экстремального значения 4, M-й канал выхода значения веса критического пути от начальной до M-й вершины графа 14 которого соединен с M-м каналом первого информационного входа многоканального накапливающего блока формирования маршрутов 5, (KM)-й выход и второй информационный вход которого соединены соответственно с выходом признака принадлежности (KM)-й дуги критическому пути 15 и с K-й группой информационного выхода многоканального блока регистрации 3, второй, третий и четвертый выходы блока синхронизации 6 соединены соответственно с тактовыми входами многоканального суммирующего блока 2, блока выбора экстремального значения 4 и счетчика 7, информационный выход которого соединен с входами задания номера моделируемой вершины многоканального суммирующего блока 2, блока выбора экстремального значения 4, многоканального блока регистрации 3 и первым входом блока синхронизации 6.

Блок задания матрицы весов дуг 1 (фиг. 2) содержит матрицу из B х B элементов памяти 16, причем тактовые входы K-го столбца элементов памяти 16 соединены с входом разрешения записи значения веса дуг, выходящих из K-х вершин 9, входы записи элементов памяти 16 M-й строки соединены с входом записи значения веса дуг, входящих в M-е вершины 8, а выход (KM)-го элемента памяти является выходом значения веса (KM)-й дуги, причем M-я группа выходов блока соединена с M-й группой первого информационного входа многоканального суммирующего блока 2.

Многоканальный суммирующий блок 2 (фиг. 3) содержит коммутатор 17, M-й канал информационного выхода которого соединен с M-м каналом второго информационного входа узла суммирования 18, первый информационный и тактовый входы которого соответственно с информационным выходом блока выбора экстремального значения 4 и вторым выходом блока синхронизации 6, а M-й канал информационного выхода является одноименным выходом блока причем, адресный вход коммутатора 17 являются входом задания номера моделируемой вершины блока и соединен со счетчиком 7, информационный вход коммутатора 17 являются первым информационным входом блока, при этом M-я группа второго информационного входа блока соединена с M-й группой выходов блока задания матрицы весов дуг 1, а M-й канал информационного выхода блока соединена с M-м каналом информационного входа блока регистрации 3.

Коммутатор 17 содержит элемент задержки 19 и группу из B мультиплексоров 20, причем, выход элемента задержки является тактовым выходом коммутатора 17, а вход элемента задержки 19 является тактовым входом коммутатора 17 и соединен с тактовыми входами каждого M-го мультиплексора 20, адресный вход каждого M-го мультиплексора 20 соединен с адресным входом коммутатора 17, K-ый информационный вход каждого M-го мультиплексора 20 является M-й группой информационного входа коммутатора 20, выход каждого M-го мультиплексора 20 является M-м каналом второго информационного выхода коммутатора 17.

Узел суммирования 18 содержит B сумматоров 21, первые информационные и тактовые входы которых соединены соответственно с первым информационным входом и тактовым входом узла суммирования 18, второй информационный вход каждого M-го сумматора 21 является M-м каналом второго информационного входа узла суммирования 18, а выход каждого M-го сумматора 21 является M-м каналом информационного выхода узла суммирования 18.

Многоканальный блок регистрации 3 (фиг. 4) содержит дешифратор 22 и матрицу из B х B элементов памяти 23, причем, информационные входы M-й строки элементов памяти 23 являются M-м каналом информационного входа блока, входы разрешения записи элементов памяти 23 K-го столбца соединены с K-м выходом дешифратора 22, а выходы элементов памяти 23 K-го столбца соединены с K-й группой информационного блока.

Блок выбора экстремального значения 4 (фиг. 5) содержит коммутатор 24, M-й канал второго информационного выхода которого соединен с M-м каналом второго информационного входа узла выбора экстремального значения 25, выход которого соединен с информационным выходом блока, вторым информационным входом многоканального суммирующего блока 2 и с информационным входом запоминающего узла 26, M-й канал выхода которого является выходом значения веса критического пути от начальной до M-й вершины, а M-й канал входа разрешения записи запоминающего узла 26 соединен с M-м каналом второго информационного выхода коммутатора 24, адресный вход которого являются входом задания номера моделируемой вершины блока и соединен со счетчиком 7, информационный вход коммутатора 24 и информационный выход узла выбора экстремального значения являются соответственно вторым информационным входом и одноименным выходом блока, при этом M-я группа второго информационного входа блока соединена с M-й группой выходов блока регистрации 3, M-й канал выхода значения веса критического пути от начальной до M-й вершины блока соединен с M-м каналом первого информационного входа многоканального накапливающего блока формирования маршрутов 5, тактовый и управляющий входы узла выбора экстремального значения 25 соединены соответственно с тактовым выходом коммутатора 24 и с входом задания режима работы 10 блока, тактовый вход коммутатора соединен с тактовым входом блока с третьим выходом блока синхронизации 6.

Коммутатор 24 содержит дешифратор 27 и B мультиплексоров 28 и элемент задержки 29, вход и выход которого соединены соответственно с тактовым входом и выходом коммутатора 24, причем, тактовый вход коммутатора 24 соединен с тактовым входом дешифратора 27, информационный вход которого является адресным входом коммутатора 24 и соединен с адресным входом каждого M-го мультиплексора 28, M-й информационный вход каждого K-го мультиплексора 28 является K-й группой информационного входа коммутатора 24, выход каждого K-го мультиплексора 28 является K-м каналом второго информационного выхода коммутатора 24, а M-е выходы дешифратора 27 являются первым информационным выходом коммутатора 24.

Узел выбора экстремального значения 24 содержит группу из (B-1) элементов сравнения 30, группу из (B-1) элементов ИСКЛ. ИЛИ 31, группу из (B-1) элементов ИСКЛ. ИЛИ 32, группу из (B-1) элементов И 33, группу из (B-1) элементов И 34, группу из (B-1) элементов ИЛИ 35, причем, тактовые входы элементов сравнения 30 группы соединены с тактовым входом узла выбора экстремального значения 25, второй информационный вход каждого K-го (К 1,B-1) элемента сравнения 30 соединен с K-ым каналом информационного входа узла выбора экстремального значения 25, а первый информационный вход первого сравнения 30 группы соединен с первым каналом информационного входа узла выбора экстремального значения 25, выходы > и <каждого элемента сравнения 30 соединены соответственно со вторым входом каждого элемента ИСКЛ. ИЛИ 31 группы и первым входом каждого элемента ИСКЛ. ИЛИ 32 группы, а первый вход каждого элемента ИСКЛ. ИЛИ 31 группы и второй вход каждого элемента ИСКЛ. ИЛИ 32 группы соединены с выходом установки режима работы узла, выходы каждого из элементов ИСКЛ. ИЛИ 31 и 32 групп соединены соответственно со вторым входом элемента И 33 и первым входом элемента И 34, а первый вход элемента И 33 группы и второй вход элемента И 34 группы соединены соответственно с первым и вторым входами элемента сравнения 30 группы, выходы элементов И 33 и 34 групп соединены соответственно с первым и вторым входами элемента ИЛИ 35 группы, выход которого соединен с первым входом элемента сравнения 30 группы, а выход последнего элемента ИЛИ 35 группы является выходом узла.

Запоминающий узел 26 содержит группу из B-элементов памяти 36, информационные входы которых соединены с информационным входом узла, а вход разрешения записи и вход каждого элемента памяти 36 соединены соответственно с M-м каналом входа разрешения записи узла и с M-ым каналом информационного выхода узла.

Многоканальный накапливающий блок формирования маршрутов 5 (фиг. 6) содержит узел синхронизации 37, тактовый вход которого является одноименным входом блока и соединен с первым выходом синхронизатора 6, а первый и второй выходы узла синхронизации 37 соединены соответственно с тактовым входом коммутатора 38 и вторым тактовым входом узла формирования признаков принадлежности вершин 39, первый тактовый вход и первый информационный вход которого соединены соответственно с первым тактовым выходом узла синхронизатора 37 и первым информационным выходом коммутатора 38, K-й канал второго информационного выхода и K-й канал четвертого информационного выхода которого соединен соответственно с K-м каналом второго информационного входа и K-м каналом четвертого информационного входа узла формирования признаков принадлежности вершин 39, K-й канал выхода которого соединен с K-м каналом третьего информационного входа коммутатора 38 и с K-м каналом информационного входа запоминающего узла 40, информационный выход которого является выходом состава критического пути и одноименным выходом 15 блока, а M-й канал входа разрешения записи соединен с M-м каналом четвертого информационного выхода коммутатора 38, третий информационный выход которого соединен с третьим информационным входом узла формирования признаков принадлежности вершин 39, причем, вход задания номера исследуемой вершины коммутатора 38 является одноименным входом 12 блока, M-й канал входа задания веса критического пути коммутатора 38 является одноименным входом блока и соединен с M-м каналом выхода 14 блока выбора экстремального значения, K-я группа входа задания суммарного веса дуг коммутатора 38 является одноименным входом блока и соединена с K-й группы информационного выхода блока регистрации 2.

Узел синхронизации 37 содержит первый элемент задержки 41, вход которого является тактовым входом узла и соединен со вторым выходом узла, а выход соединен со вторым входом элемента ИЛИ 42, выход которого соединен со входом одновибратора 43, выход которого является первым выходом узла и соединен со входом второго элемента задержки 44, выход которого соединен с первым входом элемента ИЛИ 42.

Коммутатор 38 содержит счетчик 45, вход предварительной установки которого является входом задания номера исследуемой вершины коммутатора, а тактовый вход является одноименным входом узла и соединен с первым выходом узла синхронизации, выход счетчика 45 соединен с адресными входами мультиплексора 46, каждого K-го мультиплексора 47 группы, дешифратора 48 и мультиплексора 49, причем, M-ый вход и выход мультиплексора 46 являются соответственно M-ым каналом входа задания веса критического пути и первым информационным выходом коммутатора 38, M-ый вход каждого K-го мультиплексора 47 группы является M-ым каналом K-ой группы входа задания суммарного веса дуг коммутатора 38, а выход каждого K-го мультиплексора 47 группы является K-ым каналом второго информационного выхода коммутатора 38, M-ый выход дешифратора 48 является четвертым информационным выходом коммутатора 38, выход мультиплексора 49 является третьим информационным выходом коммутатора 38.

Узел формирования признаков принадлежности вершин критическому пути 39 содержит первый 50 и второй 51 элементы задержки, группу из B элементов сравнения 52, первую группу из B элементов "И" 53, вторую группу из B элементов "И" 54, элемент "ИЛИ" 55, группу из B элементов "ИЛИ" 56 и группу из B триггеров 57, причем, входы первого 50 и второго 51 элементов задержки соединены с первым тактовым входом узла, выход первого элемента задержки 50 соединен с тактовыми входами всех K-ых элементов сравнения 52 группы, первые информационные входы которых соединены с K-ым каналом второго информационного входа узла, а второй информационный вход и выход каждого элемента сравнения 52 группы соединены соответственно с первым информационным входом узла и первым входом K-го элемента И 53 группы, второй вход которых соединен с третьим информационным входом узла, K-ый канал четвертого информационного входа узла соединен с первым входом K-го элемента "И" 54 группы, второй вход которых соединен со вторым тактовым входом узла и первым входом элемента "ИЛИ" 55, второй вход которого соединен с выходом второго элемента задержки 51, выход K-го элемента "И" 54 группы соединен со вторым входом K-го элемента "ИЛИ" 56 группы, первый вход и выход которых соединены соответственно с выходом K-го элемента "И" 53 группы и с информационным и входом установки в "О" K-го триггера 57 группы, тактовый вход которых соединен с выходом элемента "ИЛИ" 55, а выход K-го триггера 57 группы является K-каналом информационного выхода узла.

Запоминающий узел 40 содержит матрицу из B х B элементов памяти 58, причем, информационные входы K-ой строки которых являются K-ым каналом информационного входа запоминающего узла 40, тактовые входы K-го столбца элементов памяти 58 соединены с M-ым каналом входа разрешения записи, а выходы элементов памяти 58 M-ой строки соединены с М-группой выхода запоминающего узла 40.

Блок синхронизации 6 (фиг. 7) содержит элемент памяти 59, вход и выход которого соединены соответственно с входом задания номера конечной вершины 13 блока и первым информационным входом элемента сравнения 60, второй информационный вход и инверсный выход которого соединены соответственно с выходом счетчика 7 и третьим входом элемента "ИЛИ" 61, первый и второй входы которого соединены соответственно с входом пуска 12 устройства и выходом элемента задержки 62, а выход соединен со входом одновибратора 63, выход которого соединен со входом элемента задержки 62 и первым входом элемента "И" 64, второй вход соединен с инверсным выходом элемента сравнения 60, выход элемента "И" 64 является первым выходом блока и соединен со входом элемента задержки 65, выход которого является выходом блока и со входом элемента задержки 66, выход которого является третьим выходом блока, прямой выход элемента сравнения соединен с четвертым выход блока.

В устройстве используются триггеры D-типа, в качестве которых можно применить микросхемы К155ТМ8, 564ТМ2, К561ТМ2 и аналогичные им [3, стр. 187, 180, 181] Кроме того, триггеры D-типа можно образовать из любого синхронного "RS"- или "JK"-триггера, если на их информационные входы подавать взаимно инверсные сигналы [3, стр. 185] Сумматоры можно реализовать на микросхемах типа 564ИМ2, К155ИМ3 или аналогичных [3, стр. 133-145] Элементы "ИЛИ" можно реализовать на любых микросхемах этого, например К155ЛЛ1 или подобных [3, стр. 49] В качестве элемента "ИСКЛ. ИЛИ" можно применить микросхему К155ЛП5 или реализовать его на стандартных логических элементах типа "И", "ИЛИ" и "НЕ" [3, стр. 47-50] Элементы "И" можно реализовать на микросхемах типа К155ЛА6 и аналогичных. Увеличение числа входов (расширение по "И") можно организовать из нескольких элементов "И-НЕ", пользуясь законами булевой алгебры, или путем подключения внешних диодов к любому из входов микросхемы "И-НЕ" [3, стр. 47-48] Элементы сравнения можно реализовать на цифровых компараторах, в качестве которых применяются микросхемы К555СП1, 564ИП2 и аналогичные [3, с. 147-148] В качестве счетчика можно использовать микросхемы К155ИЕ2, К155ИЕ4, К155ИЕ6, К155ИЕ и аналогичные [3, с. 208-230] Элементы памяти можно реализовать на регистрах, в качестве которых можно использовать микросхемы типа 155ТМ8, 155ТМ5, 155ТМ7, 564ТМ3 и аналогичные [3, стр. 237-240] В качестве одновибратора можно применить микросхему типа К155АГ1, или реализовать его на основе либо типовых логических элементов "И-НЕ", "ИЛИ-НЕ", либо триггеров, например 564ТР2, 564ТМ2 [3, с. 266-270] Элементы задержки можно реализовать при помощи RC-цепочки или последовательно соединенных логических элементов "НЕ", а также использовать триггер [3, стр. 69]
Устройство работает следующим образом.

Перед началом работы в блок задания весов дуг 1 заносится информация о топологии графа по входам 8 и 9 (как например показано на фиг. 8а). По входу 11 многоканального накапливающего блока формирования маршрутов 5 задается номер исследуемой вершины, а по поводу 13 блока синхронизации 6 задается номер конечной вершины графа. По входу 10 блока выбора экстремального значения 4 задается режим работы (определение минимального и максимального пути). Первоначально K-ые элементы запоминающего узла блока определения экстремального значения содержат нули.

При подаче единичного импульса на вход пуска 12 устройства, блок синхронизации 6 начинает вырабатывать последовательность тактовых импульсов для управления устройства. При получении единичного импульса на свой тактовый вход, многоканальный суммирующий блок 2 в соответствии с номером К моделируемой вершины, задаваемой счетчиком 7, выбирает со своего первого информационного входа значения веса дуг, задаваемых М-ми элементами K-ой группы блока задания матрицы весов дуг 1. После этого осуществляется суммирование значений веса M-ых элементов K-ой строки матрицы весов дуг графа со значением суммарного веса K-ой вершины, поступающим на второй информационный вход многоканального суммирующего блока 2 с информационного выхода выбора экстремального значения 4. При этом многоканальный блок регистрации 3 фиксирует и выдает на свой выход суммарные веса (KM)-ых дуг. После этого блок синхронизации 6 выдает единичный импульс на тактовый вход счетчика, и его содержимое инкрементируется. Затем, единичный импульс поступает на тактовый вход блока выбора экстремального значения 4, который определяет и фиксирует значение веса критического пути от начальной до (K+1)-ой вершины графа. Это осуществляется определением минимального (максимального) значения суммарных весов дуг (K+1)-го столбца матрицы графа, которые блок выбора экстремального значения выбирает со своих информационных входов. После этого блок синхронизации 6 проверяет номер моделируемой вершины, задаваемой счетчиком 7. Если этот номер меньше числа вершин в графе, то на тактовый вход многоканального суммирующего блока подается единичный импульс, и указанная последовательность действий циклически повторяется. В результате чего (KM)-ые элементы блока регистрации 2 будут содержать суммарные веса дуг (как, например, показано на фиг. 8б), соответствующие различным возможным маршрутам, а M-ые элементы памяти запоминающего узла блока выбора экстремального значения 4 будут содержать значения веса критического пути для K-ой вершины (на фиг. 8в показано содержимое M-ых элементов памяти для случая определения минимального пути). Как только счетчик 7 будет содержать номер конечной вершины, то моделирование путей завершается, и на выход веса критического пути от начальной до М-вершины 14 поступает значение минимального (максимального) суммарного веса M-ой вершины с выхода блока выбора экстремального значения 4. Блок синхронизации 6 прекращает подачу тактовых импульсов на входы многоканального суммирующего блока 2, блока выбора экстремального значения 4 и счетчика 7 и запускает многоканальный накапливающий блок формирования маршрутов 5, который приступает к формированию дерева критических путей и признаков принадлежности дуг критическому пути. Это осуществляется следующим образом. Вначале, признак принадлежности исследуемой вершины (номер которой задан по входу 11) устанавливается в "1". После этого на вход многоканального блока формирования 5 циклически подают значения суммарных весов (KM)-ых с информационного выхода блока регистрации 2 и значения веса критического пути в M-ую вершину с выхода 14 блока выбора экстремального значения 4. Начиная с исследуемой вершины (в данном случае с конечной), путем сравнения суммарных весов дуг, заходящих в M-ую вершину (т.е. дуг M-го столбца матрицы графа) с весом критического пути в M-ую вершину, определяются номера тех (KM)-ой дуг, вес которых приводит с минимальному (максимальному) значению суммарного веса M-ой вершины. Таким дугам будет соответствовать единичное значение (как, например, показано на фиг. 8г для случая определения путей с минимальным весом), записанное в (KM)-ый элемент памяти блока формирования маршрутов, выход которого является выходом признака принадлежности дуги критическому пути 15.

Таким образом, по окончании работы в блоке выбора экстремального значения 4 содержится информация о расстояниях a_m от начальной до любой вершины графа, вычисленных по формулам: a_m=min(a_k+a_km или a_m=max(a_k+a_km, где a_km вес KM-ой дуги, a_k минимальный или максимальный суммарный вес K-ой вершины, а в блоке формирования критических маршрутов задано дерево критических путей. При решении задач на сетях минимальный суммарный вес каждой вершины можно рассматривать как ранний момент начала соответствующего события.

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

Используемые источники информации
1. Авторское свидетельство N 1658171, кл. G 06 F 15/419, БИ N 23, 1991.

2. Авторское свидетельство N 1765832, кл. G 06 F 15/419, БИ N 36, 1992.

3. Зельдин Е.А. Цифровые интегральные микросхемы в информационно измерительной аппаратуре. Л. Энергоатомиздат. Ленингр. отд-ние, 1986, 280 с.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8