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

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

Иллюстрации

Показать все

Реферат

 

1) 4844779/24

2) 27.06.90

6) 30.08.93. Бюл. М 32 (6) Авторское свидетельство СССР

1626256, кл. 06 15/419, 1991, 4) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

А ГРАФАХ

7) Изобретение относится к области выслительной техники, в частности к специ( (2) А.Г.Додонов, В.П.Приймачук, А.В, Самов, B.À. Чадюк и А,М.Щетинин ализированным вычислительным устройствам для решения задач организационного ..управления и теории графов. Целью изобретения является расширение функциональных возможностей устройства эа счет моделирования сетей с различной логической структурой узлов. Поставленная цель достигается тем, что устройство содержит блок задания списков заходящих дуг, блок проверки параметров списка, блок памяти меток свершения вершин, блок задания списков исходящих дуг, многоканальный таймер, блок синхронизации, блок памяти логической функции узлов. 1 ил.!

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

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

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

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

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

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

1837314

10

20

40 дп = max,, Рь l O, (3) 45

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

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

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

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

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

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

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

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

В практических задачах в сетях могут встречаться различные логические функции, описывающие вэаимоСвязь дуг, входящих в одну вершину (см. Васильев В.В„Ралдугин

Е.А. Электронные модели задач на графах.—

Киев: Наук, Думка, 1987 г. с, 94 — 101). Так, например, в одной и той же сети могут существовать узлы с различными логическими функциями типа: "И" (коньюнкция), "ИЛИ" (дизьюнкция) и др.

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

Sl= Ф (Хп, X2I...Õö) SI

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

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

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

Ф = АВ АС (2)

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

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

1кп = min Г Рь ieD, (4) а вершины реализуют соответственно элементарные логические функции "И" (для длиннейшего) и "ИЛИ" (для кратчайшего), то вершина на фиг. 3 моделируют сложную функцию выбора минимального из максимумов функций, Ф= т!и max (ASVAC) (5)

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

1837314

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

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

При совпадении комбинаций от дуг с

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

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

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

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

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

У азанных процессов, на вход 10 пуска стройства подается импульс уровня логиеской единицы. При этом блок синхронизаии 6 вырабатывает на своем выходе оследовательность тактовых импульсов измерительную серию).

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

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

В блоке задания списков заходящих дуг

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

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

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

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

1837314

10

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

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

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

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

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

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

Формула изобретения

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

1837314 ударственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

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

5 списка блока задания списка заходящих дуг