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

6О П И С А Н И Е (11) 48275ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(23) ПриоритетОпубликовано 30.08,75. Бюллетень32Дата опубликования описания 03.11.5 Государственный комитет Совета Министров СССР по делам изобретенийн открытий. М, Курейч Г. Соколец, В. В. Лисяи радиотехнический инс 1) Заявитель Таган рогск титут им. В. Д, Калмыкова(54) УСТРОЙСТОМБИ НАТОРНОДЛЯ РЕШЕНИЯ ГИЧЕСКИХ ЗАД оки в ть бло Изобретение относится к области вычислительной техники и может быть использовано при решении комбинаторно-логических задач на графах, связанных с выделением из графа частей с экстремальными свойствами,Известны устройства, содержащие блоки ввода и вывода информации, управляющие входы которых подключены к выходам блока управления, соединенного с решающем полем.Известные устройства не позволяют эффективно решать задачи выделения экстремальных частей в графе, которыми могут быть семейства максимальных внутреннеустойчивых независимых, несвязанных множеств и максимальных полных, связанных множеств графа. Отличительной особенностью при решении таких задач является выбор максимальных (к примеру, независимых) подмножеств из всего множества (независимых подмножеств),Известные алгоритмы работы устройств при решении таких задач имеют два этапа: выделение всех (независимых) подмножеств; выделение из всех (независимых) подмножеств максимальных (независимых).Таким образом, известные алгоритмы не допускают распараллелизования решения таких задач и делают применение известных устройств не эффективным, так как требуются значительные затраты времени.Цель изобретения - повышение быстродействия устроиства при вмальных частей в графе.Это достигается тем, что в устройство введены блок моделирования матрицы смежно 5 сти графа и блок анализа матрицы, выходыкоторого соединены соответственно с входамиблока вывода информации, блока управленияи первым входом блока моделирования матрицы смежности графа. Второй вход последнегоподключен к выходу блока ввода информации,третий вход - к выходу блока управления, авыход - к первому входу блока анализа матрицы, второй вход которого соединен с соответствующим выходом блока управления,5 Введение указанных блоков позволяет реализовать оператор выделения экстремальныхчастей в графе,На чертеже представлена структурная схемаустройства.20 В состав схемы входят; блок 1 управления,блок 2 ввода информации, блок 3 моделирования матрицы смежности грифа, блок 4 анализа матрицы, блок 5 вывода информации,Блок 1 управления позволяет записать матрицу смежности графа в блок 3, выполненныйна основе однородной сети. Кроме того, он служит для управления работой устройства и выработки управляющих сигналов выбора следующей стр блок анализа матрицы, Однородная се ка 3 предназначена для хра3нения матрицы смежности графа, а также для параллельного считывания и записи строк матрицы смежности. Считывание строк из однородной сети может происходить от схем приоритета блока анализа матрицы либо от дешифратора и счетчика блока управления.Блок 4 анализа матрицы представляет собой параллельный логический процессор, позволяющий проводить запись, хранение, считывание определенной строки, приоритетный выбор элементов в этой строке, логическое сложение строк, вырабатывать сигнал окончания выделения экстремальной части в графе и сигнал окончания выделения всех экстремальных частей в строке. Для решения этих задач блок анализа матрицы содержит схему логического сложения строк, две схемы синхронного контроля логического сложения строк для проверки пазов в каждом такте работы устройства, схему приоритетной выборки элементов в строке, предназначенной для выделения крайней слева единицы (нуля) из кода строки, и схему модификации, исключающую повторное выделение одних и тех же и неэкстремальных частей в графе. Блок 5 вывода информации служит для регистрации и вывода элементов экстремальных частей графа.Пусть, например, в однородной сети блока 3 хранится матрица смежности графа. По сигналу из блока управления первая строка в параллельном прямом коде заносится в блок 4 анализа матрицы, блок 4 выделяет все экстремальные части из первой строки и синхронно выводит их в блок 5, вырабатывает управляющий сигнал перехода к следующей строке, который поступает в счетчик строк блока 1 управления и увеличивает его состояние на единицу, Дешифратор блока управления расшифровывает новое состояние счетчика и вырабатывает сигнал на выборку второй строки из однородной сети в блок анализа матрицы и все повторяется аналогично описанному до тех пор, пока не будет выделены все экстремальные части в графе, После этого блок анализа матрицы вырабатывает управляющий сигнал 4827514перехода к следующей строке, который увеличивает состояние счетчика строк на единицу, а дешифратор расшифровывает этот сигнал как останов устройства и приводит устройство5 в исходное положение, т. е, сбрасывает счетчик строк в блоке управления в нулевое состояние и устанавливает в исходное положение однородную сеть блока 3, подготавливая тем самым устройство для решения комбинаторно логических задач к вводу следующих начальных данных.Значительное число задач технической кибернетики может быть удобно формализовано на языке теории графов. К ним относятся 15 задачи размещения, компоновки и трассировки при техническом проектировании дискретных устройств, задачи минимизации числа внутренне устойчивых состояний конечных автоматов в логическом проектировании и 20 т. д, Такие задачи, как правило, сводятся квыделению и последующему анализу экстремальных частей графа, которыми могут быть клики графа или максимальные независимые подмножества множества вершин.25Предмет изобретенияУстройство для решения комбинаторно-логических задач, содержащее блоки ввода и ЗО вывода информации, управляющие входы которых подключены к выходам блока управления, отличающееся тем, что, с целью повышения быстродействия устройства при выделении экстремальных частей в графе, в него 35 введены блок моделирования матрицы смежности графа и блок анализа матрицы, выходы которого соединены соответственно с входами блока вывода информации, блока управления и первым входом блока моделиро вания матрицы смежности графа, второй входкоторого подключен к выходу блока ввода информации, третий вход - к выходу блока управления, выход соединен с первым входом блока анализа матрицы, второй вход которо го подключен к соответствующему выходублока управления,