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

 

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

сОюз советских

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„5U„„1837311 А1 (2 ) 4767543/24 (2 ) 20.10,89 (4 ) 30.08.93. Бюп. hh 32 (7 ) А.В. Александров, Н.Б. Парамонов, А,Н.

Р баков и Е.В. Фролов (5 Авторское свидетельство СССР

М 1587535, кл. 6 06 F 15/20, 1990.

Авторское свидетельство СССР

f4 1684795„кл. 6 06 F 15/20, 1991. (5 УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

Н ГРАФАХ (5 Изобретение относится к вычислительно технике, может быть использовано при ис ледовании числовых характеристик графо . Целью изобретения является расширен и функциональных возможностей ус ройства за счет определения вероятно1 ! ( (|Изобретение относится к области вычи лительной техники и может быть использо ано для анализа связности вершин и ве оятностей перехода от одной к другой ве шине графа при наличии дуги между ниЦелью иэобРетения является расширени функциональных возможностей устройства эа счет определения вероятностей пе ехода по дугам, связывающим смежные вершины графа при условии равновероятно ти реализации любого из различающихся арш рутов.

Цель достигается тем, что в устройство для решения задач на графах по а.с. СССР

16 795, содержащее блок синхронизации, бл к определения концевых вершин дуг, блок задания матрицы смежности, сумматор коммутатор и блок памяти. причем вход стей перехода по дугам, связывающим смежные вершины графа. Устройство содержит блок синхронизации, блок определения концевых вершин дуг, блок задания матрицы смежности, коммутатор, блок памяти, сумматор, группу регистров, группу блока деления. Устройство по эвристическому ал го ритму позволяет определять количество различающихся путей из любой вершины графа в конечную, в том числе и количество различающихся путей из начальной вершины вконечную,,т.е. общее число различающихся путей в графе, а также вероятности перехода по дугам, связывающим смежные вершины графа при условии равновероятности реализации любого из путей, 2 ил. пуска устройства подключен к входу пуска блока синхронизации, первый и второй выходы которого подключены к управляющему входу коммутатора и к входу признака записи блока памяти соответственно, выход значения (1, К)-ro элемента блока задания матрицы смежности (1-1,...,В) К=1,...В, где  — количество вершин в графе, подключен к входу признака наличия (k, К)-й дуги блока определения концевых вершин дуг, сумматор, 1-й выход группы блока синхронизации подключен к (В+1-l)-му информационному входу первой группы коммутатора и к входу (В+1-О-й начальной вершины блока определения концевых вершин дуг, выход признака принадлежности К-й вершины множеству концевых вершин дуг которого подключен к

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

К-го делителя регистра группы, выход которого подключен к первому информационному входу блока деления группы, и.ко второму информационному входу блока деления группы, выходы группы блоков деления подключены к информационному входу блока памяти, Введение указанных элементов и соответствующих связей позволяет подсчитать вероятность Pik = Nk/Ni перехода по дуге графа из I-й вершины в К-ю, I, k-1, ВЙ1ц<ф0, где si„Nk — число различающихся путей из

i-й и k-й вершины графа в конечную соответ-. ственно, Uik — дуга, связывающая I-ю и k-ю вершины графа.

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

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

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

Алгоритм 1.

1. Начальные установки К:=В, 2. I.Ê-1. Просмотр вершин графа, связанных с вершиной К дугой Uik.

5 3. Если Ulkgi то Plk= Nk/NI иначе Plk О.

4. I:=1-1.

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

6. К:=K-1.

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

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

"5 фиг.2.

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

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

9 пуска устройства для расчета числа путей

35 иэ каждой вершины графа в конечную, второй вход блока 1 синхронизации соединен с . входом 10 пуска устройства для расчета вероятностей перехода по дуге из вершины графа в смежную, а также с входом модифи40 кации адресов блока 5 памяти, с первого по пятый выходы 12,...,16 которого подключены к управляющему входу коммутатора 4, к входу признака записи блока памяти 5, к тактовому входу сумматора 6, к управляю45 щему входу группы регистров 7 и к тактовому входу группы блоков деления 8 соответственно, выход значения (l, К)-га элемента блока 3 задания матрицы смежности (1-1,.„,В: К=1....,В, где  — количество вер50 шин в графе) подключен к входу признака наличия (i, К)-й дуги блока 2 определения концевых вершин дуг 1-й выход 11 группы блока 1 синхронизации подключен к (В+1-1)-му информационному входу первой груп55 пы входов коммутатора 4 и к входу опроса (В+1-1)-й начальной вершины блока 2 определения концевых вершин дуг, выход признака принадлежности К-й вершины множеству концевых вершин дуг которого

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

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

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

+1Ч)-й вершины графа. При этом коммутар 4 подключает к своим информационным

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

5 самым определяется число различающихся путей из текущей (В+1+й вершины в конечную вершину графа). Через время, достаточное для операции сложения, блок синхронизации снимает потенциал с выхо10 да 12. При этом коммутатор 4 подключает свои информационные выходы к первой группе информационных входов (тем самым возбуждается (В+1+й адресный вход блока памяти), Через время, достаточное для вы15 бора ячейки в блоке 5 памяти, блок 1 синхронизации формирует импульс уровня логической единицы на своем выходе 13.

При этом блок 5 памяти фиксирует значение, поступившее на его информационный

20 вход в выбранную ячейку памяти(тем самым по адресу (В+1+й вершины заносится число различающихся маршрутов из нее в конечную вершину графа). Через время, достаточное для записи, блок 1 синхрониэа25 ции снимает потенциал уровня логической единицы с i-ro выхода 11 и формирует потенциалы уровня логической единицы на выходе 12 и (1+1)-м выходе 11 группы (тем самым происходит переход к определению

30 количества маршрутов из ( — 1)-й вершины).

Работа устройства повторяется В раэ, В результате расчета числа путей иэ любой вершины графа в конечную в блоке 5 памяти по адресам с первого по В-й будут

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

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

Рв+н,в+я. Поскольку работа устройства со50 стоит из В однотипных тактов, рассмотрим

i-й, В I ì такте работы блок 1 синхронизации формирует потенциалы уровня логической единицы на i-м выходе 11 группы, на первом выходе 12 и четвертом выходе 15. При этом

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

55 фа в конечную), Это значение фиксируется в регистре 7 и подается на первый информационный вход блока 8 деления, после чего блок 1 синхронизации снимает потенциал уровня логической единицы с первого и четвертого выходов 12 и 15 (см. фиг, 2), При этом блок 2 определения концевых вершин формирует на своих выходах состав множества вершин, которые являются концевыми точками дуг, исходящих из (В+1-I)-й вершины графа. При этом коммутатор 4 подключает к своим информационным выходам информационные входы второй группы (тем самым возбуждаются те адресные входы блока 5 памяти, которые соответствуют составу указанных выше концевых вершин), а блок 5 памяти выдает на свои информационные выходы значения Na+<-ê, записанные в предыдущих тактах работы (тем самым на второй информационный вход блока 8деления подаются значения количеств различающихся путей из каждой (В+1-К)-й концевой вершины текущего такта работы в В-ю конечную вершину графа), после чего блок 1 синхронизации формирует импульс уровня логической единицы на пятом выходе 1б (cM, фиг. 2). При этом блок 8 деления фиксирует на своем выходе значение (РБ+н,в+н=

=Ив+ -к/йв+н) отношения поступивших на

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

Pik, поступившее íà его информационный вход в ячейку матрицы W по адресу (В+1.1)х(В+1 — К), где В+1 — I — номер строки матрицы, соответствующей вершине, из которой исходит дуга Ug, В+1-К вЂ” номер столбца матрицы, в которую заходит дуга U>k. Через время, достаточное для записи, блок 1 синхронизации снимает потенциал уровня логической единицы с i-ro выхода 11 и формирует потенциалы уровня логической единицы на (I+1)-м выходе 11 группы, на первом выходе 12 и на четвертом выходе 15 (см. фиг. 2) (тем самым происходит переход к следующему (1+1)-му такту работы, Работа устройства повторяется В раз.

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

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

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

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

М-му информационному входу второй группы коммутатора, М-й информационный выход которого подключен к М-му адресному входу блока памяти, М-й информационный выход которого является выходом количества различающихся маршрутов из М-й в конечную вершину графа устройства и подключен к входу М-го слагаемого сумматора, выход которого подключен к информационному входу блока памяти, третий выход блока синхронизации подключен к тактовому входу сумматора, отл и чаю ще еся тем, что, с целью расширения функциональных возможностей за счет определения вероятности перехода по дугам, связывающим смежные вершины графа, в них введены группа регистров и группа блоков деления, вход запуска вероятностей перехода по дуге графа устройства соединен с входом повторного пуска блока синхронизации и входом адреса блока памяти, каждая группа информационных выходов которого соединена соответственно с группой входов делимого соответствующего блока деления группы и группой информационных входов соответствующего регистра группы, группа информационных выходов которого соединена соответственно с группой входов делителя cooTâåòcòàóþùårо блока деления группы, группа выходов частного которого

1837311

Улр/г

Зпрк м при

113035, Москва, Ж-35, Раушская наб., 4/5

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