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

Оюз сОветскихОЦИАЛИСТИЧЕСКИХЕСПУБЛИК 18 11 А сти вы- испольршин и другой жду ни(2 ) 4767543/24 (2 ) 20.10,89 (4 ) 30,08.93. Бюп. Я 32 (7 ) А,В. Александров, Н.Б. Парамонов, А,Н. Р баков и Е.В. Фролов (5 Авторское свидетельство СССР М 158735, кл, 6 06 Г 15/20, 1990.Авторское свидетельство СССР В 1684795 кл. 6 06 Р 15/20, 1991. (5 УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ Н ГРАФАХ (5 Изобретение относится к вычислитель- но технике, может быть использовано при ис ледовании числовых характеристик графо . Целью изобретения является расширен и функциональных возможностей ус ройства за счет определения вероятноИзобретение относится к обл чи лительной техники и может быть зо ано для анализа связности в ве оятностей перехода от одной ве шине графа при наличии дуги м Целью изобретения является расшире ни функциональных возможностей устрой ства эа счет определения вероятностей пе ехода по дугам, связывающим смежные вершины графа при условии равновероят но ти реализации любого из различающихся арш рутов,Цель достигается тем, что в устройство для решения задач на графах по а.с. СССР 16 795, содержащее блок синхронизации бл к определения концевых вершин дуг блок задания матрицы смежности, сумма тор коммутатор и блок памяти. причем вход стеи перехода по дугам, связывающим смежные вершины графа. Устройство содержит блок синхронизации, блок определения концевых вершин дуг, блок задания матрицы смежности, коммутатор, блок памяти, сумматор, группу регистров, группу блока деления. Устройство по эвристическому алгоритму позволяет определять количество различающихся путей из любой вершины графа в конечную, в том числе и количество различающихся путей из начальной вершины в конечную, т,е. общее число различающихся путей в графе, а также вероятности перехода по дугам, связывающим смежные вершины графа при условии равновероятности реализации любого из путей, 2 ил. пуска устроиства подключен к входу пуска а блока синхронизации, первый и второй вы- (р ходы которого подключены к управляющему входу коммутатора и к входу признака записи блока памяти соответственно, выход значения (1, К)-го элемента блока задания матрицы смежности (1-1В) К=1,В, где В - количество вершин в графе, подключен к - ф входу признака наличия (1, К)-й дуги блока определения концевых вершин дуг, сумматор, 1-й выход группы блока синхронизации подключен к (В+1-1)-му информационному входу первой группы коммутатора и к входу (В+1-О-й начальной вершины блока определения концевых вершин дуг, выход признака принадлежности К-й вершины множеству концевых вершин дуг которого подключен к К-му информационному входу второй группы коммутатора, К-й информационный вы 1837311ход которого подключен к К-му адресному входу блока памяти, К-й информационный выход которого является выходом количества различающихся маршрутов из К-й в конечную вершину .графа устройства и подключен к входу К-го слагаемого сумматора, выход которого подключен к информационному входу блока памяти, третий выход блока синхронизации подключен к тактовому входу сумматора, дополнительно вводятся группа регистров и группа блоков деления, второй вход запуска блока синхронизации для расчета вероятностей перехода по дуге соединен с входом модификации адреса блока памяти, четвертый и пятый выходы которого подключены к управляющему входу регистров группы и тактовому входу блоков деления группы соответственно, информационный выход блока памяти, который является выходом количества различающихся маршрутов иэ К-й вершины графа в конечную, подключен также к входу К-го делителя регистра группы, выход которого подключен к первому информационному входу блока деления группы, и ко второму информационному входу блока деления группы, выходы группы блоков деления подключены к информационному входу блока памяти,Введение указанных элементов и соответствующих связей позволяет подсчитать вероятность Ра = М/М перехода по дуге графа из 1-й вершины в К-ю, 1, Е=ГВЮаф О, где 1 чМ - число различающихся путей из 1-й и К-й вершины графа в конечную соответ-. ственно, Оа - дуга, связывающая 1-ю и К-ю вершины графа.При этом граф 6 задается матрицей смежности (МС). Предварительно вершины графа 6 упорядочиваются таким образом, чтобы конечная вершина графа имела максимальный номер - В, а номера остальных вершин убывали по мере того, как будут перенумерованы концевые вершины всех исходящих иэ них дуг ВьВ других известных технических решениях отсутствуют подобные признаки в их общей совокупности, поэтому заявляемый обьект соответствует критерию "существенные отличия", Наличие существенных отличий приводит к положительному эффекту потому, что, исключая любой элемент или связь, введенные в устройство для решения задач на графах, нельзя рассчитать вероятность перехода из одной вершины графа в смежную при наличии между ними дуги. Алгоритм расчета вероятностей перехода из 1-й вершины графа в К-ю при наличии дуги между ними состоит в следующем. Алгоритм 1.1. Начальные установки К:=В,2. 1.К. Просмотр вершин графа, связанных с вершиной К дугой Оа.5 3, Если Оаф то Ра= М/1 чь иначе Ра:=О.4. 1:=1-1.5. Если 1, то переход к п.3, иначе - ки. 6.6. К:=К.10 7. Если К1, переход к и, 2, иначе -конец.Функциональная схема устройства длярешения задач на графах представлена нафиг. 1; временные диаграммы сигналов - на15 фиг.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 памяти, с первого попятый выходы 1216 которого подключены к управляющему входу коммутатора 4, квходу признака записи блока памяти 5, ктактовому входу сумматора 6, к управляю 45 щему входу группы регистров 7 и к тактовому входу группы блоков деления 8соответственно, выход значения (1, К)-га элемента блока 3 задания матрицы смежности(1-1,.,В; К=1В, где В - количество вер 50 шин в графе) подключен к входу признаканаличия (1, К)-й дуги блока 2 определенияконцевых вершин дугф 1-й выход 11 группыблока 1 синхронизации подключен к (В+1-1)-му информационному входу первой груп 55 пы входов коммутатора 4 и к входу опроса(В+1-1)-й начальной вершины блока 2 определения концевых вершин дуг, выход признака принадлежности К-й вершины множеству концевых вершин дуг которогоод сумматора 6 подаются значения колиств различающихся путей из каждой коневой точки текущего такта работы в нечную вершину графа), Через время, доточное для окончания указанных выше цессов, блок 1 синхронизации формируодключен к К-му информационному входу торой группы коммутатора 4, К-й информаионный выход которого подключен к К-му дресному входу блока памяти 5, К-й инфорационный выход которого подключен к ходу К-го слагаемого сумматора 6, к К-му нформационному входу группы регистрови к К-му информационному входу второй руппы блока деления 8, К-й информационый выход группы регистров 7 подключен к -му информационному входу первой групы блока деления 8, выходы группы блока еления 8 и сумматора 6 подключены к групе информационных входов блока памяти 5.Устройство работает следующим обраом; Перед началом работы номера вершин рафа упорядочиваются таким образом, чтоы конечная вершина графа имела максиальный номер (В), а номера остальных ершин графа убывали по мере того, как удут перенумерованы концевые вершины сех исходящих из них дуг. Топологию, полченного таким образом графа заносят в лок 3 задания матрицы смежности. В блокпамяти по адресу В заносят единицу, а стальные ячейки обнуляют, кроме того в локе памяти 5 сформирована матрицавхв - вероятностей перехода по дугам, чейки которой обнуляют, На вход 9 пуска роцесса счета числа путей из каждой верины графа в конечную блока 1 синхрониации подают импульс уровня логической диницы, При этом блок 1 синхронизации ормирует на своих выходах 11, 12, 13, 14 оследовательность сигналов уровня логиеской единицы предусмотренную временой диаграммой его работы. Поскольку абота устройства состоит из В однотипных актов, рассмотрим 1-й. В 1-м такте работы лок 1 синхронизации формирует потенцилы уровня логической единицы на 1-м выхое 11 группы и на первом уровне 12, При том блок 2 формирует на своих выходах остав множества вершин, которые являютя концевыми точками дуг исходящих из +1 Ч)-й вершины графа. При этом коммутар 4 подключает к своим информационным ыходам информационные входы второй уппы (тем самым возбуждаются те входы ока 5 памяти, которые соответствуют соаву указанных выше концевых точек), а ок 5 памяти выдает на свои информацинные выходы значения, записанные в редыдущих тактах работы тем самым на 10 15 20 25 30 35 40 45 50 ет импульс уровня логической единицы на своем выходе 14, При этом сумматор 6 фиксирует на своем выходе значение суммы поступивших на его входы слагаемых (тем самым определяется число различающихся путей из текущей (В+1+й вершины в конечную вершину графа). Через время, достаточное для операции сложения, блок синхронизации снимает потенциал с выхода 12. При этом коммутатор 4 подключает свои информационные выходы к первой группе информационных входов(тем самым возбуждается (В+1+й адресный вход блока памяти), Через время, достаточное для выбора ячейки в блоке 5 памяти, блок 1 синхронизации формирует импульс уровня логической единицы на своем выходе 13, При этом блок 5 памяти фиксирует значение, поступившее на его информационный вход в выбранную ячейку памяти(тем самым по адресу (В+1-)-й вершины заносится число различающихся маршрутов из нее в конечную вершину графа). Через время, достаточное для записи, блок 1 синхронизации снимает потенциал уровня логической единицы с 1-го выхода 11 и формирует потенциалы уровня логической единицы на выходе 12 и (1+1)-м выходе 11 группы (тем самым происходит переход к определению количества маршрутов из (В - 1)-й вершины Работа устройства повторяется В раэ,В результате расчета числа путей иэ любой вершины графа в конечную в блоке 5 памяти по адресам с первого по В-й будут зафиксированы количества различающихся маршрутов из первой по В-ю вершин в В-ю (конечную) вершину графа. После этого на вход 10 пуска подают импульс уровня логической единицы, который инициализирует процесс формирования управляющих сигналов, обеспечивающих расчет вероятностей переходов Рв+1-, в+1-к по дугам иэ (В+1-1)-й вершины графа в (В+1-К)-ю (см. временную диаграмму фиг. 2). Этот же импульс поступая на второй управляющий вход блока памяти 5 переключает адресные регистры данного блока для модификации адресов записи значений вероятностей Рв+н,в+я. Поскольку работа устройства состоит из В однотипных тактов, рассмотрим 1-й, В 1-м такте работы блок 1 синхронизации формирует потенциалы уровня логической единицы на 1-м выходе 11 группы, на первом выходе 12 и четвертом выходе 15. При этом коммутатор 4 подключает свои информационные выходы к первой группе информационных входов (тем самым возбуждается (В+1-1)-й адресный вход блока памяти, по которому записано количество различающихся маршрутов иэ (В+1-)й вершины гра 183731140 45 50 фа в конечную), Это значение фиксируется в регистре 7 и подается на первый информационный вход блока 8 деления, после чего блок 1 синхронизации снимает потенциал уровня логической единицы с первого и четвертого выходов 12 и 15 (см. фиг, 2), При этом блок 2 определения концевых вершин формирует на своих выходах состав множества вершин, которые являются концевыми точками дуг, исходящих из (В+1-)-й вершины графа. При этом коммутатор 4 подключает к своим информационным выходам информационные входы второй группы(тем самым возбуждаются те адресные входы блока 5 памяти, которые соответствуют составу указанных выше концевых вершин), а блок 5 памяти выдает на свои информационные выходы значения Ив+1-к, записанные в предыдущих тактах работы (тем самым на второй информационный вход блока 8 деления подаются значения количеств различающихся путей из каждой (В+1-К)-й концевой вершины текущего такта работы в В-ю конечную вершину графа), после чего блок 1 синхронизации формирует импульс уровня логической единицы на пятом выходе 1 б(см, фиг. 2), При этом блок 8 деления фиксирует на своем выходе значение (Рв+1-,в+1-к= =Ив+1-к/йв+1 ч) отношения поступивших на его входы значений(тем самым определяется вероятность перехода из (8+1-) вершины в смежную (В+1-К) вершину графа, при наличии между ними дуги). Через время, достаточное для операции деления, блок 1 синхронизации снимает потенциал с пятого выхода 16 и выдает импульс на втором выходе 13 (см, фиг. 2), При этом блок 5 памяти фиксирует значение вероятности перехода Ра, поступившее на его информационный вход в ячейку матрицы В/ по адресу (В+1- )х(В+1 - К), где В+1 -- номер строки матрицы, соответствующей вершине, из которой исходит дуга Оа, В+1-К - номер столбца матрицы, в которую заходит дуга Оа. Через время, достаточное для записи, блок 1 синхронизации снимает потенциал уровня логической единицы с -го выхода 11 и формирует потенциалы уровня логической единицы на (+1)-м выходе 11 группы, на первом выходе 12 и на четвертом выходе 15 (см, фиг, 2) (тем самым происходит переход к следующему(1+1)-му такту работы, Работа устройства повторяется В раз. В результате реализации атой процедуры в ячейках блока 5 памяти, соответствующих матрице Ю, будут храниться значения вероятностей Р перехода из (В+1 - )-й вершины графа в (В+1-К)-ю по дуге Оа, где К, с(1, 8),5 10 15 20 25 30 35 Таким образом введение блока регистров делителя и блока деления позволяет расширить функциональные возможности устройства за счет определения вероятностей перехода по дугам, связывающим смежные вершины при условии равновероятности реализации любого из путей графа.формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации, блок определения концевых вершин дуг, блок задания матрицы смежности, коммутатор, блок памяти и сумматор, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый и второй выходы которого подключены к управляющему входу коммутатора и к входу признака записи блока памяти соответственно, выход значения (К, М)-го элемента блока задания матрицы смежности (К=1,.,В; М=1 В, где В - количество вершин в графе) подключен к входу признака наличия (К, М)-й дуги блока определения концевых вершин дуг, К-й выход группы блока синхронизации подключен к (В+1-К)-му информационному входу первой группы коммутатора и к входу опроса (В+1- К)-й начальной вершины блока определения концевьх вершин дуг, выход признака принадлежности М-й вершины множеству концевых вершин дуг которого подключен к М-му информационному входу второй группы коммутатора, М-й информационный выход которого подключен к М-му адресному входу блока памяти, М-й информационный выход которого является выходом количества различающихся маршрутов из М-й в конечную вершину графа устройства и подключен к входу М-го слагаемого сумматора, выход которого подключен к информационному входу блока памяти, третий выход блока синхронизации подключен к тактовому входусумматора, отл ичаю щееся тем, что, с целью расширения функциональных возможностей за счет определения вероятности перехода по дугам, связывающим смежные вершины графа, в них введены группа регистров и группа блоков деления, вход запуска вероятностей перехода по дуге графа устройства соединен с входом повторного пуска блока синхронизации и входом адреса блока памяти, каждая группа информационных выходов которого соединена соответственно с группой входов делимого соответствующего блока деления группы и группой информационных входов соответствующего регистра группы, группа информационных выходов которого соединена соответственно с группой входов делителя соответствующего блока деления группы, группа выходов частного которого1837311 10 йр 0 113035, Москва, Ж аушская наб 4 оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 10 с единена соответственно с соответствуюей группой информационных входов блок памяти, четвертый и пятый выходы блока синхронизации соединены соответственнос входами записи регистров группы и тактовыми входами блоков деления группы.