Устройство для решения задач на графах Советский патент 1992 года по МПК G06F15/419 

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

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

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

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

Предлагаемое устройство работает следующим образом.

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

О

ел

Сл5 00

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

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

6и зафиксированная сигналом на его соответствующем признаковом выходе 10, однозначно покажет вершину (или вершины), являющиеся центром графа со взвешенными дугами и вершинами.

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

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

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

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

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

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

блока умножения, выход К-го канала которого подключен к К-му информационному входу блока выбора минимума.

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