УСТРОЙСТВО для ПОИСКА ПУТЕЙ НАПРАВЛЕННОГО ГРАФА Советский патент 1971 года по МПК G06G7/122 G06F15/173 

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

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

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

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

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

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

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

путей, п программирующих сдвоенных переключателей 9 задания конечной верщины искомых путей, разделительные диоды 10.

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

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

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

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

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

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

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

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

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

После этого нажимают кнопку 6 установки начального состояния. При этом триггеры 3,

4, 5, а также 11 всех ячеек устанавливаются в нерабочее состояние. Далее нажимают пусковую кнопку генератора 2. Образовавшийся на его выходе импульс переводит в рабочее состояние триггер 4. Импульс с выхода этого

триггера переводит в рабочее состояние триггер 3. Образовавшийся при этом импульс с выхода последнего триггера проходит через включенный при программировании переключатель 8 и попадает на сигнальный вход 15

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

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

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

«И 7 приложен единичный статический сигнал.

После записи элементов пути по загоревшимся индикаторам ячеек нажимают кнопку генератора 2. Импульс с его выхода снова песит индикатор «Путь. Образовавшийся импульс на динамическом выходе этого триггера уже не может изменить рабочего состояния триггера 3 и проходит только через включенный переключатель 9 на входы 17 всех ячеек столбца, подчиненного конечной вершине путей. В этом столбце в рабочем состоянии находится триггер только одной ячейки. Этот триггер переходит в нерабочее состояние, но при этом на выходе 16 ячейки образуется импульс, который переводит в рабочее состояние триггер очередной свободной в строке ячейки.

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

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

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

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

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

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

т

tU

N1