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

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

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

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

Предлагаемое устройство содержит: 1 - б ток задания списков заходящих дуг; 2 - бюк проверки параметров списка; 3 - блок пзмяти меток свершения вершин; 4 - блок задания списков исходящих дуг; 5 - многоканальный таймер;6 - блок синхронизации;

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

Кроме того на фиг. 1 цифровые обозначения имеют: 8 - вход/выход исполненной вершины; 9 - вход начальной установки; 10- вход пуска; 11 -тактовый выход; 12 - выход номера исполненной дуги.

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

со

со

ч| СО

Ј

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

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

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

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

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

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

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

Работу устройства рассмотрим на примере моделирования сетевой задачи со сложной логической структурой в вершинах. В практических задачах в сетях могут

встречаться различные логические функции, описывающие взаимосвязь дуг, входящих в одну вершину (см. Васильев В.В., Ралдугин Е.А. Электронные модели задач на графах.- Киев: Наук. Думка, 1987 г. с. 94-101). Так,

например, в одной и той же сети могут существовать узлы с различными логическими функциями типа: И (коньюнкция), ИЛИ (дизьюнкция)и др.

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

. Sr Ф| (Хи, X2i...XkO Si«S0)

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

Рассмотрим произвольную 1-ю вершину сети. Пусть логические соотношения для дуг, входящих в эту вершину, имеют вид: 0 i ABVAC(2)

Одну такую сложную вершину можно

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

ЕСЛИ длиннейший путь в сети

1дп max 2 PI. I«D,

(3)

где: Pi - вес дуги i, включенной в длинней- 45 ший путь сети; D - множество путей в сети, связывающих ее начало и конец, кратчайший путь

50

Un min 2 Pi. taD,

(4)

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

Ф mln max ()(5) Реализация такой функции сети возможна, если каждой вершине поставить в соответствие множество информационных

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

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

Таким образом, на входе каждой из вершин от дуг поступает переменный набор значений выходов дуг.

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

Предлагаемое вычислительное устройство (фиг. 1) работает следующим образом.

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

В блоке памяти свершения вершин 3 обнуляются вершины памяти для хранения NBTOK о свершении вершин.

В многоканальном таймере 5 в вершины памяти заносится информация о длительностях моделируемых дуг сети.

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

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

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

отсутствия прерываний (переполнений). При этом блок синхронизации 6 приостанавливает выдачу тактовых импульсов. Кроме того, таймер 5 выдает на свой выход (выход номера исполненной дуги 12) номер

исполненной дуги (номер переполнившегося канала).

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

несвершенной вершины (метка нулевая) единичный сигнал появится на инверсном выходе блока 3.

В нашем случае вершина не выполнена, и единичный сигнал с выхода блока 3 поступит на входы разрешения выдачи списка блока задания списков заходящих дуг 1 и опроса блока проверки параметров списка 2. По сигналу разрешения выдачи списка блок задания списков заходящих дуг 1 выдает на свой выход метки свершения дуг, входящих в заданный список. Метки свершения дуг для рассматриваемой вершины передаются на вход приема записей списка блока проверки параметра списка 2.

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

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

входящих в нее.

При совпадении комбинации меток от дуг с одним из информационных слов функция вершины принимает единичное значение. В противном случае вершина не

выполнена, функция вершины имеет нулевое значение.

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

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

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

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

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

На этом работа устройства заканчивается. В устройстве обеспечивается

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

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

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

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

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

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