Устройство для определения оптимального дерева связности графа Советский патент 1993 года по МПК G06F7/48 

LO

С

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

оо

а

VJ о

00 О

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

Целью изобретения является сокращение аппаратурных затрат.

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

Устройство содержит блок 1 моделирования графа, блок 2 выбора дуг, генератор тактовых импульсов 3, ключ 4 и элемент ИЛИ-НЕ5.

Блок 1 моделирования графа предназначен для задания топологии и весов дуг исследуемого графа и содержит верхнюю

наддиагональную матрицу из и п(п-1)

моделей дуг 6ij, i 1,n-1, j 1+1,n, элемент ИЛИ 7 и вход возврата устройства в исходное 8 (п - число вершин графа). Каждая модель дуги содержит триггер 9, регистр 10, сумматор по модулю два 11, вычитающий счетчик 12, элемент И 13, и ключ 14.

Блок 2 выбора дуг предназначен для определения дуги, включаемой в оптимальное дерево связности на каждом шаге работы алгоритма и содержит генератор одиночных импульсов 15, счетчик 16, первую группу и (т-1)-го элемента И 17ij, элемент ИЛИ 18, группу из (m-1)-ro элемента ИЛИ 19ij, вторую группу из m элементов И 20ij и полюс начальной установки веса дуг 21.

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

Перед решением, в регистры 10 моделей дуг вносятся значения KIJ, если ij-тая дуга есть в исследуемом графе и W, если lj-той дуги в моделируемом графе нет (Kij - вес lj-той дуги, - емкость регистра), а счетчик 16 блока 2 устанавливается в состояние п, Далее, подачей импульса на полюс 21 осуществляется перезапись содержимого регистров 10 е соответствующие счетчики 12 моделей дуг и перевод счетчика 16 в состояние п-1.

Решение начинается подачей напряжения на шину питания. При этом напряжение с нее через замкнутую информационную цепь ключа 4 поступает на вход запуска генератора импульсов 3. С выхода генератора 3 импульсы поступают на объединенные

входы моделей дуг, идидентных первой вер- шине моделируемого графа - 61,1.1 2,п.

В каждой из этих моделей дуг импульсы поступают на один из входов сумматоров по модулю два 11, а с их выходов - на вычитающий вход счетчика 12, При поступлении R

импульсов (R mln{Ki,i}) на выходе индика- i

ции нулевого состояния соответствующего

0 счетчика появляется сигнал уровня логической единицы. Пусть, например, на первом шаге решения R Ki,i Ki,n (т.е. устройство допускает поступление сигнала о достижении нулевого состояния от нескольких счет5 чиков одновременно), тогда сигналы с выходов счетчиков 12 моделей дуг 6i,rn 6i,n через соответствующие элементы И 13, на другом входе которых присутствует сигнал высокого уровня с нулевого выхода триггера

0 9, поступают на элемент ИЛИ 7 и входы элементов И 17i,i, 17i,n и элементов ИЛИ 19i,i, 19i,n блока 2 выбора. С выхода элемента ИЛИ 7 сигнал поступает на вход элемента ИЛИ-НЕ 5. При этом снимается сигнал с

5 управляющего входа ключа 4, его информационная с .цепь отсоединяет вход запуска генератора 3 от шины питания и генератор прекращает выработку импульсов. С выходов элементов ИЛИ 19i.i, 19i,n сигнал посту0 пает на входы всех схемно последующих элементов ИЛИ 19ij и инверсные входы элементов И 17ij, поэтому сигнал уровня логической единицы поступает с выхода элемента 17i,n на вход элемента ИЛИ 18 и

5 вход элемента И 20i,n. С выхода элемента 18 сигнал поступает на вход запуска генератора импульсов 16, который при этом выраба- ; тывает сигнал импульс, поступающий на вход счетчика 16, объединенные входы эле0 ментов И 20ij и считывающие входы регистров 10 всех моделей дуг. Содержимое счетчика 16 уменьшится на единицу, информация с регистров 10 вновь перезапишется в соответствующие счетчики 12 и снимутся

5 сигналы с выходов индикации нулевого состояния счетчиков 12 моделей дуг 6i,i, 6i,n. Одновременно сигнал с выхода элемента 20i,i поступает на единичный вход триггера 9 модели дуги 6i,i моделируя тем самым

0 включение 1.,1-й дуги в оптимальное решение. С единичного выхода триггера 9 сигнал поступает на управляющий вход ключа 14, информационная цепь которого соединяет при этом входы сумматора по модулю два

5 модели дуги 6{,i и соединяет с выходом генератора 3 соответствующие входы всех моделей дуг ицидентных 1-й вершине графа. Это исключает поступление импульсов на счетчик 12 модели дуги 6i,i на последующих шагах решения и выбор дуги для включения

в решение на втором шаге из множества дуг ицидентных первой и 1-й вершинам графа.

После снятия сигнала уровня логической единицы с входа элемента 5 вновь вход запуска генератора 3 соединяется инфор- мационной цепью ключа 4 с шиной питания и начинается второй шаг работы устройства, который, как и последующие, будет аналогичен выше рассмотренному.: Заметим только, если дуга из числа альтернативных на данном шаге решения может образовать цикл с уже включенными дугами на предшествующих шагах решения, то импульсы от генератора 3 будут поступать на оба входа ее сумматора по модулю два 11, что рав- позначно исключению этой дуги из дальнейшего рассмотрения.

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

Для возврата схемы в исходное необхо- димо подать сигнал уровня логической единицы на полюс 8. блока 1, с которого он поступает на объединенные у всех моделей дуг нулевые входы триггеров 9.

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

входы к-й группы блока моделирования графа подключены соответственно к выходам к-й группы блока выбора дуг, выход блока моделирования графа - к первому входу элемента ИЛИ-НЕ, выход которого подключен к управляющему входу ключа, выход которого подключен к входу запуска-останова генератора тактовых импульсов, выход которого подключён к входу синхронизации блока моделирования графа, выход блока выбора дуг подключен к второму входу элемента ИЛИ-НЕ, вход единичного потенциала устройства - к информационному входу ключа, при этом блок выбора дуг содержит 2Н групп элементов И, Н групп элементов ИЛИ.элемент ИЛИ, счетчик и генератор тактовых импульсов, при этом в блоке выбора дуг первый информационный вход объединен с выходом генератора тактовых импульсов с помощью схемы МОНТАЖНОЕ ИЛИ и подключен к входу декремента счетчика и к первым входам элементов И первой группы, выход признака нулевого результата счетчика подключен к выходу блока выбора дуг, второй информационный вход которого подключен к информационному входу счетчика, выходы элементов И к-й группы подключены соответственно к выходам к-й группы блока выбора дуг, первый информационный вход первой группы которого подключен к первому (инверсному) входу первого элемента И (Н+1)-й группы к первому входу первого элемента ИЛИ первой, группы, к второму входу первого элемента И первой группы и к первому входу элемента ИЛИ, выход которого подключен к входу запуска-останова генератора тактовых импульсов, в-й информационный вход первой группы блока выбора дуг (где ,...,Н) подключен к второму входу (в-1)-го элемента И (Н+1)-й группы и к первому входу (в-1)-го элемента ИЛИ группы, выход (в-1)-го элемента И (Н+1)-й группы подключен к в-му входу элемента ИЛИ и второму входу в-го элемента И первой группы, с-й информационный вход р-й группы блока выбора дуг(где ,...,Н, .-j H-p+l) подключен к первому входу с-го элемента ИЛИ р-й группы и к первому входу с-го элемента И (Н+р)-й группы, выход с-го элемента И (Н+р)-й группы подключен к второму входу с-го элемента И . р-й группы и к с-му входу (р-1)-й группы элемента ИЛИ, выход б-го элемента ИЛИ первой группы (где ..,Н-1) подключен ко второму входу (6+1 )-го элемента ИЛИ первой группы и к второму (инверсному) входу (б+1)-го элемента И (Н+1)-й группы, выход д-го элемента ИЛИ р-й группы (где ,...,Н- р+1) подключен к второму входу (д+1)-го элемента ИЛИ р-й группы, выход (Н-к)-го

элемента ИЛИ к-й группы подключен к второму входу первого элемента ИЛИ (к+fjh й группы и второму (инверсному) входу первого элемента И (Н+к+1}-й группы.

5

0 5 0 5

0

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