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

ОП И САНИ Е ИЗОБРЕТЕНИЯ 3132 ОУ СОюз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ висимое от авт, свидетельства-ПК б 061 15/32 Заявлено 29,111,1969 ( 1327559/1с присоединением заявки-митет по пел иорит обретений и открытиири Совете МинистровСССР публиковано 31.7111,1971. Бюллетеньата опубликования описания 25.Х.1971 УДК 621,398(088.8 Автор изобретения Заявитель. Базилев Львовский политехнический институ АфА СТРОЙ ЕЙ НАПРАВЛЕННО ЛЯ ПО Предлагаемое устройство относится к области цифровой вычислительной техники и мо.жет быть использовано как составная часть вычислительных систем.Известны устройства для поиска путей направленного графа, содержащие матрицу функциональных ячеек, переключатели зада.ния начальной и конечной вершин, триггеры и генератор одиночных импульсов. Недостатком известных устройств является относительно низкое быстродействие.Цель изобретения - увеличить быстродействие устройства за счет уменьшения ручных переключений и упростить его конструкцию. Цель достигается тем, что выход каждой функциональной ячейки соединен через программирующий переключатель данного столбца с входом управляемого переключателя первой функциональной ячейки той строки, номер которой совпадает с номером столбца, выход триггера функциональной ячейки соединен с блокирующими входами всех ячеек столбца, номер которого совпадает с номером строки, содержащей функциональную ячейку.На фиг. 1 и 2 даны функциональные схемы предложенного устройства и отдельной функциональной ячейки, соответственно; на фиг. 3 и 4 - принципиальные схемы отдельной функциональной ячейки и переключающей части устройства,Функциональная схема устроиства содержит матрицу, состоящую из и строк по (и - 1) функциональных ячеек 1 (а - наибольший возможный порядок графа), размещенных на пересечениях всех строк и столбцов, кроме соответствующих главной диагонали (слева вниз направо); генератор 2 одиночных импульсов с пусковой кнопкой, триггер 3 запуска, триггер 4 продолжения поиска, триггер 10 5 конца поиска, кнопку б установки начального состояния, логический элемент И 7 с индикатором выходного сигнала Путь, а программирующих сдвоенных переключателей 8 задания начальной вершины искомых 15 путей, и программирующих сдвоенных переключателей 9 задания конечной вершины искомых путей, разделительные диоды 10,Каждая функциональная ячейка 1 содержит триггер 11 с индикатором состояния, уп равляемый переключатель 12, реализованныйдвумя логическими элементами И и логическим элементом НЕ, программирующий выключатель ячейки 13, логический элемент ИЛИ 14.25 Сигнальный вход 15 управляемого переключателя 12 каждой, кроме первой в строке, функциональной ячейки 1 соединен с выходом 1 б управляемого переключателя 12 предыдущей в строке функциональной ячейки и тем 30 динамическим выходом триггера 11, на котором образуется единичный сигнал при переходе триггера в нерабочее состояние. Сигнальный вход управляемого переключателя каждой первой в строке функциональной ячейки соединен через переключатель 8 одной строки во включенном положении с динамическим выходом триггера 3 запуска. Выход 1 б каждой последней в строке функциональной ячейки соединен со входами 17 установки нерабочего состояния триггеров ячеек столбца одного номера с номером строки рассматриваемой ячейки и через переключатель 8 одной строки во включенном положении с триггером 5 конца поиска.Динамический выход 18 каждой функциональной ячейки, на котором образуется единичный сигнал при переходе триггера ячейки в рабочее состояние, соединен через переключатель 9 одного столбца в выключенном положении с сигнальным входом 15 переключателя 12 первой ячейки той строки, номер которой совпадает с номером столбца рассматриваемой ячейки. Во включенном положении переключателя 9 этот выход ячейки соединен со входом установки нерабочего состояния триггера 4 остановки поиска.Статический выход 19 триггера каждой ячейки, на котором имеется единичный сигнал в рабочем состоянии триггера, соединен с блокирующими входами 20 всех ячеек столбца одного номера с номером строки рассматриваемой ячейки. Вход 20 ячейки внутри ее соединен с одним входом элемента ИЛИ 14, Второй вход элемента ИЛИ 14 соединен через программирующий переключатель 13 во включенном положении с источником нулевого сигнала 0, а в выключенном положении - с источником единичного сигнала 1. Выход элемента ИЛИ 14 соединен с управляющим входом переключателя 12. Один выход переключателя 12, на котором имеется единичный сигнал при наличии такого же сигнала на сигнальном входе и нулевого сигнала на управляющем входе, соединен со входом установки рабочего состояния триггера П, Второй выход переключателя 12, на котором имеется единичный сигнал при наличии таких же сигналов на сигнальном и управляющем входах, соединен с динамическим выходом триггера 11, на котором образуется единичный сигнал при переходе триггера в нерабочее состояние, и с выходом 1 б ячейки.Кнопка б установки начального состояния соединена со входами установки нерабочего состояния триггеров 3, 4, 5 и через разделительные диоды 10 и входы 17 ячеек - со входами установки нерабочего состояния триггеров 11 всех ячеек,Выход генератора 2 одиночных импульсов соединен со входом установки рабочего состояния триггера 4 остановки поиска. Выход триггера 4, на котором образуется динамический сигнал при переходе триггера в рабочее состояние, соединен со входом установки рабочего состояния триггера 3 запуска и через 5 10 15 20 25 30 35 40 45 50 55 60 65 переключатель 9 во включенном положении и входы 17 со входами установки нерабочего состояния триггера 11 ячеек того столбца, которому подчинен этот переключатель. Статический выход триггера 4, на котором имеется единичный сигнал в нерабочем состоянии, соединен с одним входом элемента И 7, второй вход которого соединен со статическим выходом триггера 3 запуска, на котором имеется единичный сигнал в его рабочем состоянии.Для программирования задачи необходимо программирующие переключатели 13 всех ячеек, подчиненных наличным дугам графа, перевести во включенное положение; перевести во включенное положение программирующий переключатель 8 строки, номер которой совпадает с номером начальной вершины искомых путей; перевести во включенное положение программирующий переключатель 9 столбца, номер которого совпадает с номером конечной вершины искомых путей.После этого нажимают кнопку б установки начального состояния. При этом триггеры 3, 4, 5, а также 11 всех ячеек устанавливаются в нерабочее состояние. Далее нажимают пусковую кнопку генератора 2, Образовавшийся на его выходе импульс переводит в рабочее состояние триггер 4. Импульс с выхода этого триггера переводит в рабочее состояние триггер 3. Образовавшийся при этом импульс с выхода последнего триггера проходит через включенный при программировании переключатель 8 и попадает на сигнальный вход 15 первой ячейки строки, номер которой совпадает с номером начальной вершины. В этой строке переходит в рабочее состояние триггер первой включенной ячейки. На выходе 18 этой ячейки образуется импульс, который через включенный переключатель 9 столбца, в котором находится рассматриваемая ячейка, попадает на сигнальный вход 15 первой ячейки той строки, номер которой совпадает с номером указанного столбца. В этой строке перейдет в рабочее состояние триггер первой свободной ячейки (т. е, включенной при программировании и не заблокированной еще статическим сигналом на входе 20, снимаемым с выхода 19 предыдущей ячейки пути) и т, д., до тех пор, пока не перейдет в рабочее состояние триггер произвольной из ячеек, находящихся в столбце, подчиненном конечной вершине искомых путей, Импульс с выхода 18 такой ячейки уже не может попасть на сиг. нальный вход первой ячейки очередной строки, а через включенный переключатель 9 попадает на триггер 4 и переводит его в нерабочее состояние. При этом загорается индикатор Путь, так как к обоим входам элемента И 7 приложен единичный статический сигнал,После записи элементов пути по загоревшимся индикаторам ячеек нажимают кнопку генератора 2, Импульс с его выхода снова переводит в рабочее состояние триггер 4 и га313207 4,сит индикатор Путь, Образовавшийся импульс на динамическом выходе этого триггера уже не может изменить рабочего состояния триггера 3 и проходит только через включенный переключатель 9 на входы 17 всех 5 ячеек столбца, подчиненного конечной вершине путей. В этом столбце в раоочем состоянии находится триггер только одной ячейки. Этот триггер переходит в нерабочее состояние, но при этом на выходе 1 б ячейки образуется им пульс, который переводит в рабочее состояние триггер очередной свободной в строке ячейки.Если в строке не оказывается больше свободных ячеек, то импульс с выхода 16 последней строки ячейки попадает на вход 17 15 установки нерабочего состояния той ячейки, с которой раньше импульс пришел на рассматриваемую строку, и переводит соответствующий триггер в нерабочее состояние. Образовавшийся на выходе 1 б ячейки импульс сно ва ищет ближайшую свободную ячейку и т. д., до момента фиксации второго пути. После его записи опять нажимают кнопку генератора 2 и т, д.После определения всех искомых путей на 25 выходе 1 б последней строки ячейки, подчиненной вершине начала путей, образуется сигнал,который проходит через включенный переключатель 8 этой строки и переводит в рабочее состояние триггер б конца поиска. В результате загорается индикатор Конец, В данном случае алгоритм работы устройства обеспечивает определение пути после каждого импульса генератора, чем существенно увеличивается быстродействие устройства по сравнению с прототипом. Предмет изобретенияУстройство для поиска путей направленного графа, содержащее матрицу функциональных ячеек, переключатели задания начальной и конечной вершин, триггеры и генератор одиночных импульсов, отличающееся тем, что, с целью увеличения быстродействия и упрощения устройства, первый выход каждой функциональной ячейки, находящейся в -м столбце матрицы, соединен через программирующий переключатель задания конечной вершины -го столбца с сигнальным входом управляемого переключателя первой ячейки -Й строки, второй выход каждой функциональной ячейки, находящейся в 1-й строке, соединен с блокирующими входами всех ячеек 1-го столбца.313207 Орлова Исаков актор Заказ 2942(1 Изд.1209 Тираж 473 П ЦНИИПИ Комитета по делам изобретений и открытий при Совете МинистрМосква, Ж, Раушская наб., д. 4/5 пи Типография пупов авитель Мд А. А. р шанскийникова