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

Данное устройство относится к вычислительной технике.

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

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

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

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

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

Устройство для поиска путей графа, нмеющего не более п вершин состоит из п групп вертикальных щин 1В, 2В, ЗВ,..., (п-) В, пВ, в каждую из которых входят четыре шины /-4; п групп горизонтальных шин JF, 2Г, ЗГ,. . . (п - 1) Г, пГ, в каждую из которых входят по две шины - 5 Л 6; п рядков по п-1 коммутирующих ячеек (КЯ);п буферных триггеров (БТ) по одному в каждом рядке; генератора тактовых импульсов (ГТИ); триггера прекращения поиска (ТПП) с инднкатором «конец ; триггера остановки поиска с индикатором «путь (ТОП); блока питания (БП); ключа /Ci устаиовки нуля; ключа Kz продолжения поиска: входных сдвоенных переключателей /(,1, вх2, КвхЗ,...., Хвх(«-1) п выходных сдвоепных переключателей.

/Свых 1, выхЗ, Лоых 3,... Лвых(п-)- Авых п

Число п принимается равным ао: можпому наибольшему количеству верппп графа. Элементы устройства соединены следуюгцим образом. Каждая шииа //-1 соединена накоротко с щиной iB- (( 1,2,3,... ,ii) и присоединена к ключу ./(вх i-я. Другие клеммы всех ключей /(вх i-a соединены между собой и подключены к выходу ГТИ. Все шины гТ-2 соединены с ключом /d установки нуля. Каждая шина jB-3 соединена с слючом /Свх i - б, Все другие клеммы ключей /(вх /-б соединены между собой и подключены к ТПП. Шины iB-2 и 7S-3 соединены соответственно с

ключами ./(вых - и ./(вых i-бВсе другие клеммы ключей /(«х г -а соединены между собой и нодключены к ТОП. Ключи /Свых i-б толсе имеют соединенные между собой другие клеммы, которые тоже подключены к ТОП. Каждый рядок устройства состоит из одного БТ и п-1 КЯ, причем в каледом t-ом рядке отсутствует одна КЯ, соответствующая /-МУ столбцу, т. е. в диагонали.

равляется триггером, ключа К2 - сигналом на входе 7 или постоянным напряжением ЯупрИсходное состояние триггера такое, что ключ К разомкнут. Исходиое состояние его устанавлишается и: 1пульсо.м со входа 8, соединенного для КЯ-рд, находящейся в р-ом рядке н -ом сшлбце, с шиной рГ-2, нли со входа 9, соединенного с шиной дВ-З. Изменить исходное состояние может только импульс со входа 10,

если ключ Кг в таком полол енип, что имиульс попадает на триггер, а не к выходу 11. Вход 10 соедипяется с выходом 10 предыдущей КЯ, или выходом 12 БТ, если КЯ является первой в рл;.{ке. После подачи на вход 1G импульса

прн указанном пологкенин ключа/( триггер переходит во второе (рабочее) устойчивое состояние. При этом управляемый им ключ Ki замыкается, соединяя непосредственно вход 13 с выходом 14, а также зажигается индикатор.

Вход 13 КЯ соединен с шиной рГ-1, выход 14 - с шиной qB-l. Повернуть триггер в исходное состояние может только импульс со входа 8 или 9. Ключ /(2 может принимать два положения. В одном вход 10 соединен с триггером, и появление импульса на этом входе выводит триггер из исходного состояния. Это положение ключ иринимает в том случае, если тумблер /(з находится в положении «включено и на входе 14 отсутствует управляющий сигнал. Если же тумблер Кз иаходится в положении «включено и на входе . приложен управляющий сигнал или этот тумблер находится в положении «выключено, при котором через тумблер подается постояниое управляющее напряжение fynp , то ключ иринимает второе возможное состояние, при котором вход 10 соединен непосредственно с выходом //и приходящий на этот вход управляюищй импульс не может вывести триггер из исходного состояния. Этот случай соответствует режнму блокирования рассматриваемой КЯ или же режнму, когда КЯ выключеиа при наборе п ;ограммы. С КЯ снимаются дза сигнала: с выхода 15 - унравляюн:1ий импульс, когда триггер переходит в рабочее состояние, а на выход 11 поступает имиульс при переходе триггера с рабочего в сходное сосшяние. Выход 15 КЯ-Р соединен с шиной (7Й-2, выход 11 -со входом 10 следующей в

рядке КЯ, если оиа не последняя ( для

к для р п) если КЯ последняя

в рядке, то ее выход // соединен с шиной

,сй-3 и входом 16 БТ-р.

Один из возмолсных вариантов вынолнения

КЯ представлен на фиг. 2, б.

Триггер построен на транзисторах Tj и Гг, для управления ключом /Ci использованы реле PI и усилительный каскад на транзисторе Гз, ключом KZ управляет реле Ра с усилителем на

транзнсторе Гл. Индикатором ламночка Л. включенная нагрузкой усилителя на транзнсторе Т.

ся импульсом со входа 17, соединенного для БТ-р с шиной рГ-2, или входа 16, соединенного, как уже говорилось нри рассмотрении КЯ, с выходом и последней в рядке КЯ. Изменить состояние триггера из исходного в рабочее может только импульс на входе 18, соединенном с шиной /3-1. j )абочем состоянии с выхода 19, сосдиноиного с шиной В-4, снимается ностоянный уиравляюш,ий сигнал. При нереходе из исходного в рабочее состояние на выход 12, соединеииый со входом 10 первой в рядке КЯ, поступает унравляющий имиульс. Прнициниальиая схема БТ иа двух транзисторах нриведена ка фиг. 3,6.

Генератор тактовых импульсов (ГТИ) является управляемым, генерируюш;им тактовые импульсы, снимаемые с выхода 20, соединенного с ключами /(их i - и (i 1,2,3, . . . п-1, п.) при отсутствии запираюш,его нанряжения на входах 21, 22, 23. Вход 21 соединен € ключом установки нуля, вход 22 - с выходом 24 ТПП, вход 23 - с выходом 25 ТОП.

Иа фиг. 4, б приведена принциинальная схема ГТИ на транзисторах. Иа транзисторах Гц, Т-, TS вынолнены автогенератор и уснлительно-ограиичительный каскад, на транзисторах Тд, Тю и Гц - занираюш.ие каскады, препятствующие ноявлению тактовых импульсов на выходе 20 при подаче на иронзвольный из входов 21, 22 или 23 запирающего напряже1П1я.

Триггер прекращения поиска (ТПП) может п-ри1нимать два устойчи-вых состояния - исходное (первое) и рабочее (второе). Исходное состояние устанавливается подачей имиульса на вход 26. Вход 26 соединен с ключом установки нуля. Вывести ТПП из исходного состояния может только импульс на входе 27, соединенном с ключами /Сих i - б (г 1,2,3,... п-1,п). Когда триггер находится во втором состоянии, горит индикатор «конец, и на входе 24 имеется сигнал, запирающий генератор тактовых импульсов. Приннипиальная схема ТПП, выполненная на транзисторах, приведена на фиг. 5, б.

Триггер остановки поиска (ТОП) отличается от ТПП тем, что для установки исходного состояния имеются два раздельных ндентнчных входа - 28 и 29, а также наличием выхода 30 для снятия уиравляющего импульса, который появляется при переходе с рабочего состояния в исходное. Вход 28 соединен с ключом установки нуля, вход 29 - с ключом продолжения поиска. Выход 30 соединен с ключами Лвы.х i-б (,2,3, ... п-1, п), вход 31, куда попадает импульс для перевода ТОП в рабочее состояние, с ключами /Свых i - и (i 1,2,3,... п-1, п).

Сигнал, снимаемый с выхода 25 для запирания ГТТ, несколько удлиняется звеном удлинения на время переходных процессов в устройстве, проходящих после нажатия кнопки продолжения поиска.

катор «путь горит, когда ТОП находится н рабочем состояиии.

Блок И1ггання (БП) интает необходимым напряжением все элементы устройства (па ф1;: I

для упрощения цени нитання не ириведены). Кроме этого с БП через ключ Л4 установки нуля и /Cs продолжения поиска на трнггеры устройства подается напряжение, необходимое, для установки их в исходпое состояппе.

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

необходимо набрать программу. Для набора программы нужно включить те КЯ, которые соответствуют наличным дугам графа. Для этого тумблеры /(з этих КЯ устанавлнвают в иоложение «включено. Дуге pq графа, исходящей из вершины р и заходяшей в вершину q, соответствует КЯ-р(, находящаяся в р-ом рядке и (J-OM столбце. Кроме этого, необходимо включить тот иереключатель /(DX «, который соответствует рядку, подчипеииому «-ой

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

Осталь}1ые переключатели Двх п выключены.

При нажатии кноики K установки нуля на все триггеры устройства нодается напряжение, устанавливающее их в нс.ходное состояние. При этом на ГТИ тоже подается напряжение, запирающее его и нренятствующее появлению на его выходе тактовых импульсов, Состояние БТ и КЯ при этом приведено на фиг. 7-0. Клетки первого столбца этой фигуры соответствуют БТ, остальные клетки - КЯ. Здесь, как и на следующие этим клеткам БТ или КЯ находятся в нсходном состояннн. Единицей обозначены БИ и КЯ, находящиеся в рабочем состоянии, крестиком - заблокированные КЯ. Попутно отмети.м, что заблокировать можно только КЯ, находящиеся в исходном состоянни. Имиульс же, поступающ1п 1 иа вход 14 КЯ, находящийся в рабочем состоянии, не может вывести ее из этого состояння, т. е.

заблокировать ее. После отпуска кнопки установки нуля запирающее напряжение снимается с ГТИ, и на его выходе появляются тактовые импульсы. Первый нмпульс с ГТИ через ключ /Свх 2 - а попадает на шину 2Г-1 п переводит в рабочее состояние БТ-2. При этом ia выходе 19 БТ-2 и соединенной с ннм шины 2В-4 появляется сигнал, блокирующий все КЯ второго столбца, а на выходе 12 - импульс, который, попадая на вход 10 КЯ-21, переводит

последней замыкается. Второй тактовый импульс через ключ Квх 2-а, шину 2Г-1, ключ/С, КЯ-21 попадает па шину 16-1 и тем самым шппу 1Г-1 и переводит БТ-1 в рабочее состояние. При этом, аналогично предыдуш,ему, блокируются все КЯ первого столбца, а импульс на выходе 12 БТ-1, пройдя через ключ /(2 заблокированпой КЯ-12 еепосредственно к ее выходу 11, попадает на вход 10 КЯ-13 и переводит ее в рабочее состояние (фиг. 7).

При этом замыкается ключ /d . Третий тактовый импульс проходит через ключ /Свх 2-а, шину УГЛ, ключ КЯ-21, шипу В-1, шину 1Г-1, ключ Ki КЯ-13, шину ЗВ-1, шину ЗЛ1 п, попав на вход 18 БТ-3, переводит его в рабочее состояние. При этом блокируются все КЯ третьего столбца, а импульс с выхода 12 БТ-3, пройдя неиосредствепио через ключи заблокированных КЯ-31 и КЯ-32, попадает на вход 10 КЯ-34 и переводит последнюю в рабочее состояние (фиг. 7-3). На выходе 15 КЯ-34 появляется импульс, который, пройдя по шине 45-2 и через ключ /(вых 4-а, иопадает на вход 31 ТОП и переводит его в рабочее состояние. Появившийся вследствие этого сигнал на выходе 25 ТОП занирает ГТТ, и подача тактовых импульсов прекрап ается. Индикатор «путь ТОП загорается. После записи первого найденного пути, включаюш,его дуги графа Д 21, Д 13, Д 34, соответствуюш,ие загоревшнмся индикаторам КЯ-21, КЯ-13, КЯ-34, находяш,пмся в рабочих состояних, нажимают кнопку /Са продолжения поиска. При этом попадаюш,ий на вход 29 ТОП сигнал переводит его в исходное состояние. На выходе 30 ТОП появляется импульс, который, пройдя через ключевых 4-б, шину45-3, попадает на вход9 КЯ-34 и переводит ее в исходное состояние. Па выходе 11 последней появляется импульс, который, нопав на вход W КЯ-35, переводит КЯ-35 Б рабочее состояние. Таким образом, после нажатия кнопки /(5 иродолл еиия поиска элементы устройства ерпнимают состояние, приведенное на фиг. 7-3. С переходом ТОП в ис.ходное состояние снимается с некоторой задержкой запираюш,ее напряжение со входа 23 ГТН, что приводит к появлению очередпых тактовых имиульсов на выходе ГТИ. С приходом четвертого тактового импульса переходит в рабочее состояние КЯ-54, вследствие чего опять загорается индикатор «путь ТОП и прекраш;ается подача тактовых импульсов. После записи второго найденного пути, состояшего из дуг Д 21, Д 13, Д 35, Д 54, которым соответствуют находящиеся в рабочем состоянии КЯ-21, КЯ-13, КЯ-35, КЯ-54, опять нажимают кнопку Дг, продолжеппя поиска. При этом пз состояния, прпведенпого па фиг. 7-4, соответствующего найденпому второму пути, ycTpoiiство переходит в состояние, приведенное па фиг. 7-4. Переход этот осу1пествляется следующим образов. Импульс с выхода 30 ТОП, ПОЯВИВПП-1ЙСЯ прп нажатпи кнопки Л-, продол жения поиска, проходит через ключ Лшлх 4-б шину 45-3 и попадает на вход 9 КЯ-54. Последняя возвращается в исходное состояние и на ее выходе 11 образуется импульс. Поскольку больше в рядке КЯ нет (имеются в виду включенные при программировании), этот импульс попадает на вход 16 БТ-5 и возвращает его в исходное состояние, что в свою очередь снимает блокнровку с КЯ пятого столбца. С другой стороны этот же импульс попадает на njHHy 55-3, с которой пеиосредствеино соединен выход // КЯ-54. С этой шины импульс подадает иа вход 9 КЯ-35 и возвращает в исходное состоянне. Это вызывает появленне импульса на выходе // КЯ-35, который возвраш,ает в исходное состояние БТ-3, попав на его вход 16.

Этот же импульс, попав на шппу 35-3, непосредственно соединенную с выходом 11 КЯ-35, переводит в исходное состояние соединенную с этой шиной входом 9 КЯ-13. Образованный па выходе // последней импульс переводит в рабочее состояние КЯ-14 (фиг. 7- 4). После этого опять переходнт в рабочее состояние ТОП, и загорается индикатор «путь. Третий пайдеппый путь включает дуги Д 21, Д 14, соответствующие паходящимся в рабочем состоянии КЯ-21 и КЯ-И. После записи результата и нажатия кнопки /(г, поиск продолжается. Следующие состояния приведены па фиг. 7, где числа в левых верхппх углах указывают на порядковый помер трактового имиульса, после которого рассматриваемое состояние установилось. Фигуры, соответствующие числам со штрихами, устанавливалась после нажатия кнопки K.s продолжения поиска. Все найденные пути сведены на ф(Нг. 7 в отдельную таблицу.

Па фиг. 8 ириведен пример поиска путей неполного графа.

Черточками обозначены места, соответствующие ячейкам, тумблеры Kz которых при программировании етавятся в положение «включено.

Замети.м еще, что после перебора всех возможных путей на выходе // последней во втором (для рассмотренных примеров) рядке КЯ-25 образуется пмнульс, который через ключ /Cix 2-б попадает на вход 27 ТПП и переводит его в рабочее еостояние. При этом загорается индикатор «конец, и еигналом с выхода 24 ТПП запирается ГТР1.

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

Устройство для поиска путей направленного графа, содер/Knniee генератор тактовых имиульсов, триггер прекращения понска, триггер остановки понска с ключом продолжения поиска, матрицу коммутирующих ячеек, состоящих пз триггера г управляемым пм ключом, отличаюи ееся тем, что, с целью упрощения авто.матического поиска всех возможных путей между двумя произвольными вершинам направленного графа, оно дополнительно содержит управляемый и программируюндий переключатели, а также столбец буферных триггеров, столбец сдвоенных входных ключей заДания начального узла искомых путей и строку сдвоенных выходных ключей задания начального узла искомых путей пстроку сдвоенных выходных ключей задания конечного узла искомых путей, нричем одна клемма управляемого ключа ячейки соединена через горизонтальную шину с аналогичными клеммами управляемых ключей всех коммутирующих ячеек одной строки, а также со входом установки рабочего состояния буферного триггера одной строки и через короткозамкнутую вертикальную шину - с другими клемлшмп уиравляемых ключей всех коммутирующих ячеек столбца одного номера с номером строки рассматриваемой ячейки, а также через первый входной ключ одного номера - с генератором тактовых имнульсов, один динамический выход триггера коммутирующей MMeiiKH соединен через вертикальную шину одного и первый выходной ключ однот-о столона с триггером остановки поиска, сташческий РЫХОД которого соединен с генератором тактов.мх плшульсов. а динамический выход - через второй выходной ключ одного столбца и вертикальную шину со входами установки исходного состояния триггеров коммутируклиих ячеек одного столбца, один выход управляемого переключателя ячейки соединен со входом установки рабочего состояния триггера ячейки, второй - со вторым динамическим выходом этого триггера и сигнальным входом управляемого переключателя следуюшей в строке коммутирующей ячейки или же. для иоследней в строке ячейки, - с вертикальной шиной, соединенной со входами установки исходного состояния триггеров коммутирующих ячеек одного номера с номером

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

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

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

70

13

/f

I 2. 3

b- o+f«

и1

конец

Щ

2 3

Ь-Е

,

23 и 5