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

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

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

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

Устройство содержит блок 1 синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок 4 регистрации времени исполнения .вершин, сумматор 5, блок 6 сравнения, блок 7 памяти и разделительные диоды 8j, I 1, п (п - число вершин графа).

Блок 1 синхронизации обеспечивает формирование сигналов уровня логической единицы на элементы и блоки устройства в соответствии с алгоритмом определения р- медиан графа. Основу блока может составлять генератор сочетаний из п по р на базе известных устройств для перебора сочетаний. Цифровые обозначения на схеме имеют: вход пуска устройства 9, вход задания числа рЮ, тактовый вход 11, управляющие выходы 12j, i 1, n, 13, 14.

Блок 2 определения кратчайшего пути регистрирует моменты исполнения вершин графа и формирует сигнал признака исполнения всех вершин графа. На схеме обозначен): 15 - вход начальной установки, 16j, i 1, n - информационные входы; 17 - выход признака исполнения всех вершин графа.

Блок 3 задания матрицы смежности предназначен для задания топологии и весов дуг исследуемого графа, устанавливае- мых по входам 18i), Ij 1, п, а также для моделирования исполнения вершин графа и сигнализации об этом через выходы 19i, i 1, n.

Блок 4 регистрации времени исполнения вершин графа предназначен для записи сигналов, пропорциональных минимальному времени достижения i-той вершины графа (i 1, п) из всех р вершин, соответствующих данному шагу решения, и подачи этих сигналов на входы сумматора. Блок содержит интегратор 20п элементов памяти 21i, выходы признака записи 22i, вход 23 подготовки и вход 24 пуска бло информационные выходы блока 25i (i 1, п).

Блок 5 сумматор предназначен для определения результирующего сигнала, пропорционального сумме времени достижения

всех вершин графа из заданных на шаге решения вершин. Информационные входы блока 26i, I 1, п информационный выход 27. Блок 6 предназначен для сравнения, по

5 сигналу поступающему на управляющий вход 28, сигнала на информационном входе 29 с сигналом, хранящемся в памяти блока. Если сигнал, поступающий на информационный вход меньше, то появляется импуль10 сный сигнал на выходе 30 блока, а значение информационного сигнала записывается в память блока вместо сигнала, хранящегося там ранее. Вход 31 начальной установки, поступление импульса на него обеспечива15 етзапись в память блока предельно большого сигнала,

Блок 7 предназначен для фиксирования по сигналу на управляющем входе 32 комбинации сигналов, поступающих на информа20 ционные входы 33i, i 1, п.

Устройство работает следующим образом. Перед началом работы подачей соответ- ствующих сигналов по входам 18ij, ij 1, n блока 3 задается топология и веса дуг исс25 ледуемого графа, по входу 10 блока 1 Задается число р п и подачей сигнала на вход 31 устанавливается в исходное состояние блок 6.

Работа устройства начинается подачей

30 сигнала на вход пуска 9. При этом появляется сигнал уровня логической единицы на выходе 14, откуда он поступает на вход 15 блока 2 и осуществляет его начальную установку, а через вход 23 блока 4 на входы

35 возврата в исходное нулевое состояние преоб- разователя 20 и элементов памяти 21i, i 1, п. По завершению этих операций сигнал с выхода 14 снимается и появляется сигнал на управляющем выходе 13 и р выходах группы

40 выходов 12i, i 1, п в соответствии с первым сочетанием из п по р, сформированным в блоке 1. Сигнал с выхода 13 поступает через вход 24 на вход запуска времяинтегрирую- щего преобразователя 20, который при этом 45 начинает генерировать линейно-возрастающий сигнал (напряжение или код), поступающий на информационные входы элементов памяти 21i, i 1,п. Сигналы уровня логической единицы с р выходов 12i, i

50 1, п поступают на информационные входы 33i, i 1, п блока 7, а, через соответствующие разделительные диоды 8i, i 1, п на объединенные полюса 16i, 19i, 22i, i 1, п блоков 2, 3, 4 соответственно. При этом в блоке 2

55 моделируется достижение тех р вершин, которым соответствуют единичные сигналы на выходах 12i, I 1, п. В блоке 3 начинается моделирование достижения остальных п - р вершин графа. В блоке 4 по сигналам с соответствующих р входов 22i осуществится запись информационного нулевого сигнала в р элементах памяти . По мере завершения моделирования достижения вершин в блоке 3, появляются сигналы уровня логической единицы на соответствующих выходах 19 этого блока, откуда они поступают на входы 16i блока 2, где фиксируется достижения соответствующей вершины, и на входы 22i блока 4. С входов 22i сигналы поступают на входы элементов памяти 211 и в них фиксируется сигнал пропорциональный минимальному расстоянию от заданных на шаге решения р вершин до данной i-той.

Через время достаточное для моделирования достижения всех вершин графа, блок 2 формирует импульсный сигнал, поступающий на управляющий вход 28 блока 6 и тактовый вход 11 блока 1. В блоке 6 осуществляется сравнение сигнала, поступающего с выхода сумматора и пропорционального сумме кратчайших расстояний от заданных на шаге решения р вершин до остальных п - р вершин графа, со значением, хранящимся в памяти блока 6. Так как в исходном состоянии там хранится предельно большое число, что на выходе 30 блока б появляется импульсный сигнал, поступающий на вход 32 блока 7, в котором при этом фиксируется заданное на первом шаге решения сочетание из п по р. Через время достаточное для срабатывания блоков 6 и 7 снимаются сигналы уровня логической единицы с р выходов 12j и с выхода 13. Вновь формируется сигнал уровня логической единицы на выходе 14 и далее работа устройства повторяется аналогично выше рассмотренному первому шагу до полного перебора всех сочетаний из п по р.

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

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

блок сравнения и блок регистрации времени исполнения вершин, причем а-й выход группы блока синхронизации соединен с а- м выходом блока задания матрицы смежности с помощью элемента МОНТАЖНОЕ

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

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

времени исполнения вершин, вход установки в исходное состояние которого подключен к входу установки в О всех элементов памяти и к входу установки в исходное состояние интегратора, входы с первого по

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

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