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

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

Иллюстрации

Показать все

Реферат

 

О П И С А Н И Е (ii) 48275!

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 22.04.74 (21) 2019454/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 30.08.75. Бюллетень № 32

Дата опубликования описания 03.11.75 (51) М. Кл. G 06г 15(20

Государственный комитет

Совета Министров СССР по делам изобретений н открытий (53) УДК 681.325(088.8) (72) Авторы изобретения

М. Г. Соколец, В. В. Лисяк и В. М. Курейчик

Таганрогский радиотехнический институт им. В. Д. Калмыкова (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

КОМБИ НАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ

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

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

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

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

Известные алгоритмы работы устройств при решении таких задач имеют два этапа: выделение всех (независимых) подмножеств; выделение из всех (независимых) подмножеств максимальных (независимых).

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

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

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

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

В состав схемы входят: блок 1 управления, блок 2 ввода информации, блок 3 моделирования матрицы смежности грифа, блок 4 анализа матрицы, блок 5 вывода информации.

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

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

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

482751

4 перехода к следующей строке, который увеличивает состояние счетчика строк на единицу, а дешифратор расшифровывает этот сигнал как останов устройства и приводит устройство

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

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

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

Предмет изобретения

Устройство для решения комбинаторно-логических задач, содержащее блоки ввода и

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

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