Устройство для поиска путей направленного графа

 

ОП И САНИ Е

ИЗОБРЕТЕНИЯ

3I3 297

СОюз CGBBTGKHx

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

Республик

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

Зависимое от авт. свидетельства №вЂ”

Заявлено 29.111.1969 (№ 1327559/18-24) МПК б 06f 15/32 с присоединением заявки №вЂ”

Приоритет

Опубликовано 31.YII 1.1971. Бюллетень № 26 УДК 621,398(088.8)

Дата опубликования описания 25.Х.1971

Комитет по делам изобретений и открытий при Совете Министров

СССР

Автор изобретения

Р. П. Базилевич

Заявитель

Львовский политехнический институт

УСТРОЙСТВО ДЛЯ ПОИСКА ПУТЕЙ НАПРАВЛЕННОГО ГРАФА

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

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

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

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

На фиг. 1 и 2 даны функциональные схемы 25 предложенного устройства и отдельной функциональной ячейки, соответственно; на фиг. 3 и 4 — принципиальные схемы отдельной функциональной ячейки и переключающей части устр ой ст в а. 30

Функциональная схема устройства содержит матрицу, состоящую из п строк по (n — l) функциональных ячеек 1 (n — наибольший возможный порядок графа), размещенных на пересечениях всех строк и столбцов, кроме соответствующих главной диагонали (слева вниз направо); генератор 2 одиночных импульсов с пусковой кнопкой, триггер 8 запуска, триггер 4 продолжения поиска, триггер

5 конца поиска, кнопку б установки начального состояния, логический элемент «И» 7 с индикатором выходного сигнала «Путь», п программирующих сдвоенных переключателей 8 задания начальной вершины искомых путей, и программирующих сдвоенных переключателей 9 задания конечной вершины искомых путей, разделительные диоды 10.

Каждая функциональная ячейка 1 содержит триггер 11 с индикатором состояния, управляемый переключатель 12, реализованный двумя логическими элементами <И» и логическим элементом <НЕ», программирующий выключатель ячейки 18, логический элемент

«ИЛИ» 14.

Сигнальный вход 15 управляемого переключателя 12 каждой, кроме первой в строке, функциональной ячейки 1 соединен с выходом

1б управляемого переключателя 12 предыдущей в строке функциональной ячейки и тем динамическим выходом триггера 11, на кото313207 ром образуется единичный сигнал при переходе триггера в нерабочее состояние. Сигнальный вход управляемого переключателя каждой первой в строке функциональной ячейки соединен через переключатель 8 одной строки во включенном положении с динамическим выходом триггера 8 запуска. Выход 1б каждой последней в строке функциональной ячейки соединен со входами 17 установки нерабочего состояния триггеров ячеек столбца одного номера с номером строки рассматриваемой ячейки и через переключатель 8 одной строки во включенном положении с триггером 5 конца поиска.

Динамический выход 18 каждой функциональной ячейки, на котором образуется единичный сигнал при переходе триггера ячейки в рабочее состояние, соединен через переключатель 9 одного столбца в выключенном положении с сигнальным входом 15 переключателя 12 первой ячейки той строки, номер которой совпадает с номером столбца рассматриваемой ячейки. Во включенном положении переключателя 9 этот выход ячейки соединен со входом установки нерабочего состояния триггера 4 остановки поиска.

Статический выход 19 триггера каждой ячейки, на котором имеется единичный сигнал в рабочем состоянии триггера, соединен с блокирующими входами 20 всех ячеек столбца одного номера с номером строки рассматриваемой ячейки. Вход 20 ячейки внутри ее соединен с одним входом элемента «ИЛИ» 14, Второй вход элемента «ИЛИ» 14 соединен через программирующий переключатель 18 во включенном положении с источником нулевого сигнала «О», а в выключенном положении— с источником единичного сигнала «1». Выход элемента «ИЛИ» 14 соединен с управляющим входом переключателя 12. Один выход переключателя 12, на котором имеется единичный сигнал при наличии такого же сигнала на сигнальном входе и нулевого сигнала на управляющем входе, соединен со входом установки рабочего состояния триггера П, Второй выход переключателя 12, на котором имеется единичный сигнал при наличии таких же сигналов на сигнальном и управляющем входах, соединен с динамическим выходом триггера

11, на котором образуется единичный сигнал при переходе триггера в нерабочее состояние, и с выходом 1б ячейки.

Кнопка б установки начального состояния соединена со входами установки нерабочего состояния триггеров 8, 4, 5 и через разделительные диоды 10 и входы 17 ячеек — со входами установки нерабочего состояния триггеров 11 всех ячеек.

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

65 переключатель 9 во включенном положении и входы 17 со входами установки нерабочего состояния триггера 11 ячеек того столбца, которому подчинен этот переключатель. Статический выход триггера 4, на котором имеется единичный сигнал в нерабочем состоянии, соединен с одним входом элемента «И» 7, второй вход которого соединен со статическим выходом триггера 8 запуска, на котором имеется единичный сигнал в его рабочем состоянии.

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

После этого нажимают кнопку б установки начального состояния. При этом триггеры 8, 4, 5, а также 11 всех ячеек устанавливаются в нерабочее состояние. Далее нажимают пусковую кнопку генератора 2, Образовавшийся на его выходе импульс переводит в рабочее состояние триггер 4. Импульс с выхода этого триггера переводит в рабочее состояние триггер 8. Образовавшийся при этом импульс с выхода последнего триггера проходит через включенный при программировании переключатель 8 и попадает на сигнальный вход 15 первой ячейки строки, номер которой совпадает с номером начальной вершины. В этой строке переходит в рабочее состояние триггер первой включенной ячейки. На выходе 18 этой ячейки образуется импульс, который через включенный переключатель 9 столбца, в котором находится рассматриваемая ячейка, попадает на сигнальный вход 15 первой ячейки той строки, номер которой совпадает с номером указанного столбца. В этой строке перейдет в рабочее состояние триггер первой свободной ячейки (т. е. включенной при программировании и не заблокированной еще статическим сигналом на входе 20, снимаемым с выхода 19 предыдущей ячейки пути) и т. д., до тех пор, пока не перейдет в рабочее состояние триггер произвольной из ячеек, находящихся в столбце, подчиненном конечной вершине искомых путей. Импульс с выхода 18 такой ячейки уже не может попасть на сигнальный вход первой ячейки очередной строки, а через включенный переключатель 9 попадает на триггер 4 и переводит его в нерабочее состояние. При этом загорается индикатор «Путь», так как к обоим входам элемента

«И» 7 приложен единичный статический сигнал, После записи элементов пути по загоревшимся индикаторам ячеек нажимают кнопку генератора 2. Импульс с его выхода снова переводит в рабочее состояние триггер 4 и ra313207 сит индикатор «Путь». Образовавшийся импульс на динамическом выходе этого триггера уже не может изменить рабочего состояния триггера 8 и проходит только через включенный переключатель 9 на входы 17 всех 5 ячеек столбца, подчиненного конечной вершине путей. В этом столбце в раоочем состоянии находится триггер только одной ячейки. Этот триггер переходит в нерабочее состояние, но при этом на выходе 1б ячейки образуется им- lo пульс, который переводит в рабочее состояние триггер очередной свободной в строке ячейки.

Если в строке не оказывается больше свободных ячеек, то импульс с выхода 16 последней строки ячейки попадает на вход 17 1s установки нерабочего состояния той ячейки, с которой раньше импульс пришел на рассматриваемую строку, и переводит соответствующий триггер в нерабочее состояние. Образовавшийся на выходе 1б ячейки импульс сно- 20 ва ищет ближайшую свободную ячейку и т. д., до момента фиксации второго пути. После его записи опять нажимают кнопку генератора 2 и т. д.

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

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

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

1-ro столбца.

313207

Составитель М. И. Аршавский

Редактор И. А. Орлова Техред А. А. Камышникова Корректор Е. В. Исакова

Заказ 2942,11 Изд. № 1209 Тираж 473 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

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

Типография, пр. Сапунова, 2