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

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

Известна модель узла для исследования графа, содержащая сдвиговые регистры, триггеры, элементы И, ИЛИ. Модель может использоваться в устройствах для исследования неориентированных графов.

Недостатком устройства является руч- ная коммутация связей в исследуемом графе,

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

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

VI

00 О

ю ю ся

сдвига, входы реверса и сдвига второго регистра сдвига являются соответственно входами реверса и сдвига модели, первый вход четвертого элемента И подключен к выходу триггера, второй выход сигнала сдвига блока управления перебором вершин подключен ко второй группе входов сдвига моделей вершин группы, группы входов задания начальной 1ершйны и задания кода номера вершины которой являются соответственно пер войли второй группами входов задания устройства, а выход сигнала опроса последней модели вершины группы является выходом устройства, причем дополнительно введены в каждую модель вершины первый и второй элементы НЕ, блок элементов И, выход которого является информационным выходом модели, первый вход- Входом задания кода номера вершины, а второй вход подключен к выходу младшего разряда второго регистра сдвига, вход записи которого подключен ко второму входу элемента ИЛИ и является входом задания начальной вершины модели, а вход управления Записью подключен к выходу четвертого элемента И, второй вход которого подключен к выходу третьего элемента И, выход элемента ИЛИ подключён к установочному вхбду триггера, выход котбрбго Подключён ко второму входу первого элемента И, выход которого подключен к входам соответственно первого и второго элементов НЕ, выход первого из которых является осведомительным выходом модели, а выход второго подключен ко второму входу второго элемента И, выход которого является выходом сигнала опроса модели, вторым входом сдвига которой является вход первого регистра сдвига, а блок управления перебором вершин содержит блок формирования сигналов управления, первый и второй элементы И, элемент ИЛИ, первый и второй счётчики импульсов,; триггер, генераторi ймТГульЬов, которого подключен соответственно к первым входам первого и второго элементов И, вторые входы которых подключены соответственно к прямому и обратному выходам триггера, выход второго элемента И подключен к входу запуска блока формирования сигналов управления, а выход первого элемента и является вторым выходом сигнала сдвига блока и подключен к входу вычитания первогоf сч1ётчМа ймТ 19лъсов и ко входу второго счетчика импульсов, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к установочному входу триггера, второй вход является входом управления пуском блока, а третий вход подключен к выходу первого счетчика импульсов, установочный вход которого под0

5

0

5

0

5

0

5

5

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

Недостаток устройства - отсутствие возможности осуществления поиска в ширину.

Цель изобретения - расширение класса решаемых задач за счет осуществления процедуры поиска в ширину.

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

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

-которого подключен к выходу сброса блока формирования сигналов управления, прямой и обратный выходы соответственно к второму входу первого элемента И и к пер- 20 вому входу второго элемента И, а установочный вход - к выходу первого элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам первого и второго счетчиков импульсов, выход второго 25 элемента И подключен к тактовому входу блока формирования сигналов, дополнительно введены в блок управления перебором второй, третий, четвертый и пятый элементы ИЛИ, блок элементов ИЛИ, вход 30 которого является информационным входом блока, а выход - информационным вы- блока и подключен к установочному входу первого счетчика импульсов, вход стробирования которого подключен к выхо- 35 ду стробирования блока и к выходу пятого элемента ИЛИ, группа входов которого является группой входов стробирующих сигналов блока, группы входов первых, вторых и третьих осведомительных сигналов кото- 40 рого являются соответственно группами входов второго, третьего и четвертого элементов ИЛИ, выходы которых подключены соответственно к первому, второу и третьему осведомительным входам блока форми- 45 рования сигналов управления, выход продолжения поиска которого является выходом продолжения поиска блока управления перебором вершин, а выход останова подключен к входу останова генератора им- 50 пульсов, вход запуска которого подключен к первому входу первого элемента ИЛИ, причем каждая предыдущая модель верши- ны группы выходом второго сигнала опроса подключена к входу второго сигнала опроса 55 каждой последующей модели вершины группы, выход второго сигнала опроса последней из которых является вторым выходом подключения устройства, выход стробирования и информационный выход

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

На фиг. 1 представлена функциональная схема устройства для исследования графа; на фиг. 2 - пример исследуемого графа; на фиг. 3 - блок-схема алгоритма функционирования устройства.

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

стоящими после номеров позиций на чертеже, обозначены пор ядковые номера совершенно одинаковых по своему функциональному назначению и техническому исполнению блоков, узлов и элементов, а просто цифрами в скобках возле контуров блоков и узлов - порядковые номера входов и выходов данного блока или узла. В каждую модель 2 вершины входят регистр 3 сдвига, триггеры 4-7, элементы 8-13 И, блок 14 элементов И, элементы 15, 16 ИЛИ. Элементы И блока 14 моделей 2 вершин образуют матрицу из В х М элементов, остальные элементы этих моделей образуют группы из В элементов.

Блок 1 управления перебором вершин включает генератор 17 импульсов, блок формирования сигналов управления 18, счетчики 19, 20 импульсов, триггер 21, элементы И 22, 23, элементы 24-28 ИЛИ, блок 29 элементов ИЛИ. Кроме этого, на фиг. 1 цифровые обозначения имеют вход 30 пуска устройства, В групп входов 31 задания кода номера вершины графа (В - число вершин в графе, МНодаВ), выходы 32, 33 соответственно первого и второго сигналов опроса моделей 2 вершины, входы 34,35 соответственно Первого и второго сигналов опроса моделей 2 вершины, вход 36 начала поиска, группа из В входов 37 начальной выборки модели, с которой начинается.процедура поиска в ширину, вход 40 продолжения поиска, группа из В выходов 38, 39, 41 осведомительных сигналов, группа из В выходов 43 стробирующих сигналов, вход 42 сдвига устройства. В групп из М информационных выходов 44 моделей вершин, передающих M-разрядные коды вершин в блок 1, группа из М информационных выходов 45 устройства, выход 46 стробирования.

Блок 1 и В моделей 2 вершин образуют однородную моделирующую структуру. Полюсы 36. 40, 42 являются общими для всех В моделей 2 вершин. Полюсы 32(В) и 33(В) используются при добавлении новых моделей 2 вершин (расширении устройства).

Регистр 3 сд вйГа является кольцевым с числом разрядов (В+1) и предназначен для хранения информации о связях данной вершины с другими вершинами графа. Блок 14 элементов И используется для выдачи в блок 1 кода (номера) вершины, установленного на входах 31 задания кода номера вершины. Установка кода осуществляется однократно предварительной подачей на соответствующие входы блока 14 логического нуля или единицы.

Счетчик 19 иМпульсов предназначен для формирования временного интервала с момента Начала отсчета импульсов и до момента обнуления (работает на вычитание) в зависимости от кода, занесенного в него через информационные входы до начала счета. Счетчик 2.0 импульсов используется

для восстановления исходного состояния информации, записанной в регистры 3 сдвига.

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

0 Пусть необходимо сформировать список вершин графа, начиная с заданной, в порядке, определяемом процедурой поиска в ширину (ППШ) на графе, структура которого представлена на фиг. 2. Зададим в каче5 стве начальной вершину с номером 1.

Перед начало работы в регистры 3 сдвига заносится информация о структуре связей в графе (матрица смежности). Триггеры 4-7устанавливаются в исходное нулевое со0 стояние. Блок формирования сигналов управления 18 в исходном состоянии не вырабатывает никаких сигналов на своих выходах (1)-(б),

Сигналом Пуск на полюсе 30 запуска5 ется генератор 17 импульсов, а через элемент 28 ИЛИ блока 1 устанавливается в единицу триггер 21 блока 1, который своим единичным выходом открывает элемент 23 И, Одновременно с этим сигнал Пуск по0 ступает на полюс 37(1) модели 2(1) вершины, который выбран в качестве начального и через элемент 16(1) ИЛИ поступает на вход 43(1), а также открывает блок 14 элементов И, с выходов которых на первые входы блока

5 29 элементов ИЛИ передается двоичный код номера выбранной модели. С выходов блока 29 элементов ИЛИ код номера узла поступает на информационные входы счетчика 19 импульсов. Под действием сигнала

0 на стробирующем входе, поступающем с выхода элемента 27 ИЛИ, в счетчик 19 заносится двоичный код номера узла 1. Тактовые импульсы генератора 17 через элемент 23 И поступают на вход (4) блока формирования

5 сигналов управления 18, под действием которых блок 18 начинает формировать сигналы управления. По сигналу на выходе (2) этого блока триггер 21 перейдет в нулевое состояние, при этом элемент 23 И закроет0 ся, а элемент 22 И откроется. Отсчитав один импульс, счетчик 19 сформирует сигнал обнуления, который через элемент 28 ИЛИ блока 1 переведет триггер 21 в единицу, На полюс 42 (вход сдвига) устройства поступит

5 один импульс, который одновременно сдвинет все регистры 3 на один разряд. В регистрах 3 моделей (2), (3) и (4) на выходе сформируется сигнал единицы. Переключение триггера 21 в единицу продолжит работу блока 18: на выходе (5) формируется

сигнал выделения, подаваемый на полюс 36 устройства. Этот сигнал пройдет через элемент 10 И (дешифратор адреса) в моделях 2 вершины с номерами (2), (3) и (4), так как только в этих моделях в данный момент на выходе регистров 3 сформирован сигнал единицы. В тех же моделях триггеры 4, 5 и 6 переходят в единичное состояние, причем нулевой выход триггера 5 блокирует элемент 10 И, и они из дальнейшего процесса поиска исключаются.

Затем формируется сигнал Поиск на выходе (4) блока 18, который поступает на полюс 35(1). Путь прохождения этого сигнала через модели 2 вершин зависит от состояния триггера 4: если триггер 4 в О, то сигнал Поиск проходит через элементы 8 И, 15 ИЛИ на полюс 32 и далее на полюс 35 следующей в цепи модели вершины; если триггер4 в 1 -черезэлементы 9 И, 15 ИЛИ на полюс 32; устанавливает в 1 триггер 7, а также подается на вход элементы 16 ИЛИ, с выхода которого поступает на нулевой вход триггера 6 и на входы блока 14 элементов И, разрешая передачу в блок 1 и на полюсы 45 кода номера данной вершины, установленного на полюсах 31, а также через полюс 43 и элемент 27 ИЛИ блока 1 нэ стробирующий вход счетчика 19 импульсов.

В исследуемом иллюстративном графе по сигналу Поиск на информационные выходы 45 устройства будут переданы коды номеров вершин первого уровня (2), (3) и (4), и в этих моделях 2 вершин триггеры 7 будут переведены в 1.

Затем триггер 21 снова переводится в нулевое состояние и импульсы генератора 17 вновь поступают на входы счетчиков 19, 20 и на полюс 42 сдвига устройства с целью восстановления исходного состояния регистров 3. Одновременно сигнал Поиск распространяется по цепи, образованной последовательным соединением полюсов 32 и 35. Сигнал переполнения счетчика 20 переводит триггер 21 в 1, и работа блока 18 продолжается,

Анализируется уровень сигнала на входе (2) блока 18. Нулевой сигнал на этом входе означает, что передача кодов номеров вершин первого уровня (2), (3), (4) в блок 1 закончена.Блок 18 опрашивает свой вход (2) до появления на.нем сигнала нулевого уровня, что произойдет тогда, когда все триггеры будут переведены в О, т.е. все вершины первого уровня просмотрены. Затем анализируется сигнал на входе (1) блока 18: если О, то все вершины графа просмотрены (все триггеры 5 уже установлены в 1 и их О выходы сформируют на выходе элемента 24 ИЛИ нулевой сигнал) и процесс поиска завершен. Если на входе (1) сигнал равен Г, то на выходе (3) блока 18 устанавливается единичный потенциал, который поступает на полюс 34(1).

5С помощью этого сигнала отыскивается первая (с наименьшим номером) вершина из множества вершин (2), (3), (4) от которых теперь продолжается поиск вершин второго уровня. Путь прохождения потенциала с по-,

0 люса 34(1) через модели 2 вершин зависит от состояния триггера 7: если триггер 7 в О, то сигнал через элемент 12 И поступает на полюс 33 и далее к следующей модели, если триггер 7 в 1, то сигнал к следующей мо5 дели не проходит, а через элементы 13 И. 16 ИЛИ поступает в блок 14 и передает в блок 1 код номера вершины первого уровня (в нашем примере вершина (2)), от которой продолжается поиск вершин следующего

0 (второго) уровня.

Затем начинается новый цикл сдвига регистров 3. Через два импульса выходным сигналом счетчика 19 будет восстановлено 1 состояние триггера 21 и блок 18 сформи5 рует сигнал выделения на своем выходе (5). Вершина (3) уже просматривалась ранее и ее элемент 10 И закрыт О выходом триггера 5. После этого сигнал на выходе (6) блока 18 через общий полюс 40 поступит на все

0 модели 2 вершин на вход элементов 11. В модели 2 вершины (1) он подтвердит О состояние триггера 7(1), пройдя через элемент 11(1). С выхода элемента 11(2) сигнал, поданный на общий полюс 40 устройства,

5 переведет в О триггер 7(2). Это откроет элемент 12(2) и единичный потенциал с полюса 33(2) перейдет к элементам И 11(3) и 12(3) следующей в цепи модели 2(3) вершины, где будет остовлен, так как и его триггер

0 7(3) стоит в 1 (вершина (3) входит в подмножество вершин первого уровня). Через элемент 13(3) И и 16(3) ИЛИ пришедший единичный потенциал передаст в счетчик 19 импульсов блока 1 управления код номера вершины (3).

5

0

5

Затем блок 18 переводит триггер 21 в О и организует как и ранее регенерацию регистров 3. Выходной сигнал счетчика 20 восстанавливает 1 состояние триггера 21 и опрашивается на входе (3) блока 18. Так как триггер 7(3) вершины (3) еще сохраняет состояние 1. то сигнал на входе (3) блока 18 равен 1. Начинается сдвиг регистров 3. Через три импульса сдвига выходной сигнал счетчика 19 переводит триггер 21 в 1. Затем вырабатывается сигнал выделения на полюсе 36, который выделит в подмножество второго уровня вершину (6), связанную с вершиной (3) первого уровня. После этого

цепочка действий: подача сигнала на полюс 40 и сброс триггера 7/3 в О, регенерация регистров 3, выявление единичного сигнала на входе (3) блока 18; запись кода номера вершины (4) в счетчик 19, сдвиг регистров 3 на четыре разряда и подача сигнала на полюс 36 - приведет к выделению в подмножество второго уровня вершины (5), связанной с вершиной (4). Вершина (6), тоже связанная с вершиной (4), не выделяется, т.к. она уже была выделена в процессе поиска от вершины (3). После этого блок 18 формирует сигнал на выходе (6), который переведет в О триггер 7(4). Анализ сигнала на входе (3) блока 18 покажет, что триггеров 7, имеющих состояние 1, больше нет. Теперь устройство выдаёт коды номеров вершин второго уровня. Для этого блок 1 переводит в О сигнал на полюсе 34(1) и подает импульсный сигнал на полюс 35(1). Под его действием на информационные выходы 45 устройства будут переданы коды номеров вершин, у которых триггеры 4 находятся в 1, т.е. (5), (6), (8), (9). После перевода в О триггера 6(9) сигнал на входе (2) блока 18 станет нулевым, что свидетельствует об окончании выдачи кодов номеров вершин второго уровня на выходы 45 устройства. Так как еще есть непросмотренные вершины (7), (10), то сигнал на входе (1) бло- ка 18 равен 1. Поэтому процедура поиска продолжается. При этом в качестве исходных для продолжения поиска выступают вершины второго уровня (5), (6), (8), (9). Поиск вершин третьего уровня (7) и (10) начинается с формирования на полюсе 34(1) единичного потенциала. Дальнейшие действия аналогичны. После выдачи номеров кодов вершин (7) и (10) все триггеры 5 окажутся в 1. Эту ситуацию характеризует сигнал О на входе (1) блока 18, после выявления которого на одном из этапов алгоритма устройство остановит решение. Таким образом, в ходе описанной процедуры для иллюстративного графа на выходы 45 будет выданы коды но- меров вершин в такой последовательности: (1), (2). (3). (4), (5), (6), (8), (9), (10), причем пояШШйе койа1 Номера вёри/ины на полюсах 45 Й прббЪ ЯЩается имНульсом синхронизации на полюсе 46.

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

Начало - инициализация устройства и формирование сигнала пуска.

Блок 47-запись кода номера начальной вершины в счетчик 19 блока 1 управления.

Блок 48 - сдвиг информации в кольцевых регистрах 3,

Блок 49 - подача сигнала, выделения вершин 1-го уровня на полюс 36.

Блок 50 - подача сигнала на полюс 35(1) и формирования кодов номеров вершин 1-го уровня на выходных полюсах 45,

. Блок 51-восстановление (регенерация) информации в регистрах 3.

Блок 52 - проверка состояния триггеров 6 (сигнал на входе (2) блока 18.

Блок 53 - проверка состояния триггеров 5 (сигнал на входе (1) блока 18).

Блок 54 - подача потенциала 1 на полюс 34(1) для записи в счетчик 19 блока 1 управления кода номера текущей вершины 1-го уровня, с которой продолжается поиск вершин (1+1) уровня.

Блок 55 - сдвиг информации в кольцевых регистрах 3.

Блок 56 - подача сигнала выделения вершин (1+1) уровня, связанных с текущей вершиной i-ro уровня (полюс 36).

Блок 57 - подзча сигнала (полюс 40 записи в счетчик 19 блока 1 управления кода номера следующей (текущей) вершины 1-го уровня м регенерация регистров 3.

Блок 58 - проверка наличия еще на использованных вершин 1-го уровня для отыскания вершин (1 + 1) уровня: анализ состояния триггеров Т.

Блок 59 - снять сигналы с полюса 34(1) - установить потенциал О.

Блок 60 - подача сигнала на полюс 35(1) и формирование кодов номеров веришь (1+1) уровня.

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

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

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

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

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

гЬхЩЬщг)

миЬ ЩЩ,а)

К«

Ww®

Фиг. /

t(t) (4

4в

+M{S)

-°м

10 3 8 7 Sf4 3 I Y

Patyfffo/; 4 6 789-ft«

f a/r ft/qa с/ъгжхег-тс//

if

(#avajv

&

лЈ