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

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

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

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

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

со VI со

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

Введение указанных элементов и соответствующих связей позволяет подсчитать вероятность Pik Nk/Ni перехода по дуге графа из 1-й вершины в К-ю, i, k TTBVUik Јo, где MI, Nk число различающихся путей из 1-й и k-й вершины графа в конечную соответственно; Uik - дуга, связывающая 1-ю и k-ю вершины графа.

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

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

Алгоритм расчета вероятностей перехода из 1-й вершины графа в К-ю при наличии дуги между ними состоит в следующем.

Алгоритм 1.

1.Начальные установки .

2.1:К-1. Просмотр вершин графа, связанных с вершиной К дугой Uik.

3. Если Uik0# то Pik Nk/Ni, иначе .

4..

5.Если I 1, то переход к п. 3, иначе - к п. 6.

6..

7. Если К 1, переход к п. 2, иначе - конец.

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

фиг. 2.

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

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

из каждой вершины графа в конечную, второй вход блока 1 синхронизации соединен с входом 10 пуска устройства для расчета вероятностей перехода по дуге из вершины графа в смежную, а также с входом модификации адресов блока 5 памяти, с первого по пятый выходы 1216 которого подключены к управляющему входу коммутатора 4, к входу признака записи блока памяти 5, к тактовому входу сумматора 6, к управляю

щему входу группы регистров 7 и к тактовому входу группы блоков деления 8 соответственно, выход значения (I, К)-га элемента блока 3 задания матрицы смежности ( , где В - количество вершин в графе) подключен к входу признака

наличия (J, К)-й дуги блока 2 определения

концевых вершин дуг 1-й выход 11 группы

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

подключен к К-му информационному входу иторой группы коммутатора 4, К-й информационный выход которого подключен к К-му дресному входу блока памяти 5, К-й информационный выход которого подключен к ходу К-го слагаемого сумматора 6, к К-му нформационному входу группы регистров и к К-му информационному входу второй руппы блока деления 8, К-й информацион- ый выход группы регистров 7 подключен к -му информационному входу первой груп- ы блока деления 8, выходы группы блока 1деления 8 и сумматора 6 подключены к груп- е информационных входов блока памяти 5.

Устройство работает следующим обра- ом. Перед началом работы номера вершин рафа упорядочиваются таким образом, что- ы конечная вершина графа имела макси- чальный номер (В), а номера остальных ершин графа убывали по мере того, как удут перенумерованы концевые вершины сех исходящих из них дуг. Топологию, пол- ченного таким образом графа заносят в лок 3 задания матрицы смежности. В блок памяти по адресу В заносят единицу, а стальные ячейки обнуляют, кроме того в локе памяти 5 сформирована матрица VBXB - вероятностей перехода по дугам, чейки которой обнуляют. На вход 9 пуска роцесса счета числа путей из каждой вер- jHHbi графа в конечную блока 1 синхрони- ации подают импульс уровня логической единицы. При этом блок 1 синхронизации юрмирует на своих выходах 11, 12, 13, 14 оследовательность сигналов уровня логи- еской единицы предусмотренную времен- ой диаграммой его работы. Поскольку абота устройства состоит из В однотипных актов, рассмотрим i-й. В i-м такте работы Елок 1 синхронизации формирует потенци- алы уровня логической единицы на i-м выхо- ре 11 группы и на первом уровне 12. При этом блок 2 формирует на своих выходах состав множества вершин, которые являются концевыми точками дуг исходящих из (В+1Ч)-й вершины графа. При этом коммутатор 4 подключает к своим информационным выходам информационные входы второй гэуппы (тем самым возбуждаются те входы блока 5 памяти, которые соответствуют со- сгаву указанных выше концевых точек), а блок 5 памяти выдает на свои информационные выходы значения, записанные в предыдущих тактах работы тем самым на вкод сумматора 6 подаются значения коли- чэств различающихся путей из каждой концевой точки текущего такта работы в кэнечную вершину графа). Через время, достаточное для окончания указанных выше процессов, блок 1 синхронизации формирует импульс уровня логической единицы на своем выходе 14, При этом сумматор 6 фиксирует на своем выходе значение суммы поступивших на его входы слагаемых (тем самым определяется число различающихся путей из текущей (В+1-1)-й вершины в конечную вершину графа). Через время, достаточное для операции сложения, блок 1 синхронизации снимает потенциал с выхода 12. При этом коммутатор 4 подключает свои информационные выходы к первой группе информационных входов (тем самым возбуждается (В+1-1)-й адресный вход блока памяти), Через время, достаточное для выбора ячейки в блоке 5 памяти, блок 1 синхронизации формирует импульс уровня логической единицы на своем выходе 13. При этом блок 5 памяти фиксирует значение, поступившее на его информационный вход в выбранную ячейку памяти (тем самым по адресу (В+1-1)-й вершины заносится число различающихся маршрутов из нее в конечную вершину графа). Через время, достаточное для записи, блок 1 синхронизации снимает потенциал уровня логической единицы с i-ro выхода 11 и формирует потенциалы уровня логической единицы на выходе 12 и (1+1)-м выходе 11 группы (тем самым происходит переход к определению количества маршрутов из (ВН)-й вершины), Работа устройства повторяется В раз.

В результате расчета числа путей из любой вершины графа в конечную в блоке 5 памяти по адресам с первого по В-й будут зафиксированы количества различающихся маршрутов из первой по В-ю вершин в В-ю (конечную) вершину графа. После этого на вход 10 пуска подают импульс уровня логической единицы, который инициализирует процесс формирования управляющих сигналов, обеспечивающих расчет вероятностей переходов Рв+1-i, в-н-к по дугам из (В+1-1)-й вершины графа в (В+1-К)-ю (см. временную диаграмму фиг. 2). Этот же импульс поступая на второй управляющий вход блока памяти 5 переключает адресные регистры данного блока для модификации адресов записи значений вероятностей Рв+нв+1-к. Поскольку работа устройства состоит из В однотипных тактов, рассмотрим i-й. В I-м такте работы блок 1 синхронизации формирует потенциалы уровня логической единицы на i-м выходе 11 группы, на первом выходе 12 и четвертом выходе 15. При этом коммутатор 4 подключает свои информационные выходы к первой группе информационных входов (тем самым возбуждается (В+1- |)-й адресный вход блока памяти, по которому записано количество различающихся маршрутов из (В+1-1)-й вершины графа в конечную). Это значение фиксируется в регистре 7 и подается на первый информационный вход блока 8 деления, после чего блок 1 синхронизации снимает потенциал уровня логической единицы с первого и четвертого выходов 12 и 15 (см. фиг. 2). При этом блок 2 определения концевых вершин формирует на своих выходах состав множества вершин, которые являются концевыми точками дуг, исходящих из (В+1-1)-й вершины графа. При этом коммутатор 4 подключает к своим информационным выходам информационные входы второй группы (тем самым возбуждаются те адресные входы блока 5 памяти, которые соответствуют составу указанных выше концевых вершин), а блок 5 памяти выдает на свои информационные выходы значения NB-M-K, записанные в предыдущих тактах работы (тем самым на второй информационный вход блока 8 деления подаются значения количеств различающихся путей из каждой (В+1-К)-й концевой вершины текущего такта работы в В-ю конечную вершину графа), после чего блок 1 синхронизации формирует импульс уровня логической единицы на пятом выходе 16 (см. фиг. 2). При этом блок 8 деления фиксирует на своем выходе значение (Рв+н,в+1-к NB-H-K/NB+H) отношения поступивших на его входы значений (тем самым определяется вероятность перехода из (В+1-1) вершины в смежную (В+1--К) вершину графа, при наличии между ними дуги). Через время, достаточное для операции деления, блок 1 синхронизации снимает потенциал с пятого выхода 16 и выдает импульс на втором выходе 13 (см. фиг. 2). При этом блок 5 памяти фиксирует значение вероятности перехода Pik, поступившее на его информационный вход в ячейку матрицы W по адресу (В+1- |)х(В+1-К), где B+1-i - номер строки матрицы, соответствующей вершине, из которой исходит дуга Uik, B+1-K - номер столбца матрицы, в которую заходит дуга Uik. Через время, достаточное для записи, блок 1 синхронизации снимает потенциал уровня логической единицы с i-ro выхода 11 и формирует потенциалы уровня логической единицы на (1+1)-м выходе 11 группы, на первом выходе 12 и на четвертом выходе 15 (см. фиг. 2) (тем самым происходит переход к следующему (1+1)-му такту работы. Работа устройства повторяется В раз.

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

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

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

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

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

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

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

5 группы и группой информационных входов соответствующего регистра группы, группа информационных выходов которого соединена соответственное группой входов делителя соответствующего блока деления j pynnbi, группа выходов частного которого

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

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