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

(5 ч) УС НЛ ГРАФ (57) Иэ Ной ВЬИ НОСТИ К РЕШЕНИЯ 2) 22.0 6) 15,0 1) Инст нин в зне 88. Екиг,Чт пробле к цифров частработкн значения. вадел ке АН У.УшОВ ьев, ,В.Фед 88.8) информаЦель иэ стройства я задач х-решетБлок моаит регистр льет7/12 е свиде ге а не ах с тв свиде 1969,ИРО судАРстВенный нОуитет сссРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ,БО 142403 А ТРОИСТВО ДЛЯАХобретение относитсяислительной техникеУстройствам для обции специального наобретения - расширеньньгх воэмогггностей уобеспечения решенниентированных графанформацией в узлах.аггия графа 1 содер171гистр 13 памяти записывается идентификатор списка,После увеличения на единицу величины и; младших разрядов кратчайшего пути (согласно условию В 9,фиг.4) проверяется переполнениестаршег разряда этой величины. Ес"ли переполнение существует (условиеВ 9 вьа 1 олнено), то единица переноса прибавляется к величину и младших разрядов величины кратчайшего пути, находящейся в узле 7 оперативной памяти, и вновь записывается н него (оператор А 13, фиг,4)При отсутствии переполнения величины п младших .разрядов кратчайшего пути (условие В 9 не выполнено, проверка выполняется аналогично условию В 2) проверяется метка "Исходящий адрес" (условие В 10, фиг4),Если метка "Исходящий адрес" отсутстнует (условие В 10 не выполнено)то (оператор А 14, фиг,4) указатель количества просмотренных идентификаторов, находящийся в соответствующей ячейке памяти узла 7 оперативной памяти, передается через управляемый формирователь 8 инверсногокода на вход АЛУ 9, где увеличивается на единицу и вновь записывается в узел 2 оперативной памяти, В АЛУ 9 указатель количества просмотреиВных идентификаторов сравнивается с максимальным адресом узла 16 памяти идентификаторов, Максимальная величина адреса идентификаторов образуется на выходах управляемогоФормирователя 8 инверсного кода приотсутствии сигнала управления яаего входе, Эта величина передаетсячерез шинный формирователь 14,входной регистр 15 на первый информационный вход АЛУ 9.Указатель количества просмотренных идентификаторов иэ узла 7 оператинной памятиподается на второй информационныйнхдц АЛУ 9, На входе кода выполняемой функции АЛУ 9 подается кодФункции сравнения,Результат сравнения (условие В 11) проверяется аналогично услонию В 5. Равенство чисел (условие 811 выполнено) соответствует тому, что идентификаторы списков просмотрены по всей совокупности относительной величины веса, от утстнуют узлы. для загрузки в проь . е временнссо моделирования их вес в,В этом случае мо 424031 жет индицироваться ошибка в заданииисходных данных или сбой работы устройстна.Неравенство чисел поэноляет продолжить процесс временного моделирования, Блок 2 выполняет операции с вершины 2 алгоритма, повторно выполняет действия начиная с операторон А 2.Если метка "Исходящий адрес" по относительной величине веса присутстнует (услоние В 10, фиг.4) тогда (согласно оператору А 15, фиг.5) ад 5 10 15 20 25 30 35 40 45 50 55 рес узла, являющийся идентификатором списка узлов с ранной относительной величиной веса, из регистра 13 памяти записывается регистр 3 адреса ив ячейку памяти узла-предка узла 7оперативной памяти, Узел по этомуадресу считается свершенным, Припередаче информация через АЛУ 9 навход кода выполняемой функции АЛУ 9подается код логической Функции передачи прямого кода с первого информационного входа на выход, При эаписи информации н ячейку памяти узлапредка узла 7 оперативной памятиподается адрес цанной ячейки памяти. Влоком 2 счетчик 18 направлений устанавливается н нулевое состояние.Указатель количества просмотренныхидентификаторов, находящийся в соотнетстнующей ячейке памяти узла 7оператиннои памяти, также устанавливается в "0". Для этого по,сигналусброса н "0" с блока 2 выходной регистр 10 устанавливается в нулевоесостояние, Нчлевые данные иэ выходку памяти указателя количества просмотренных идентификаторов узла 7 оперативной памяти. По адресу щентификатора списка, находящегося и регистре 3 адреса,из ячеек памяти меток конечных узлов считывается и запоминается триггером 6 метки метка Конечный узел",Когда свершившийся узел не является конечным (условие В 12 не выполнено, проверка выполняется аналогично условию В 2), блок 2среходит квыполнейию этапа топологиеского моделирования, По напрд 11 еням входаиз узла графа-решеткичяя с нулевого определяются адреса идичдентных узлов и аналнэирух 1:ся х м 1 гхи, Ьтносительная велиия я 1, формируются списки чздояр оч; и отноного регистра 10 записываются в ячей 142 011 20ситепьной лепи пцг 1 й веса. Апресл нццинис цтных учпов опредепннтсн суммированием гдресл учла с соатнетстну- ЮЩИМ ЦЛПРЛНПЕНИЮ ВЫХОДЛ ЦЗ УЗПЛ КОР 5 ректирующим числом. Колы коааектярующих чисел опретепяютсд размером графа-решетки, ега типам ц лрцфме" тич;скимн Операция,1 и сложения ипн вычитания прн определении адреса уз 1 О ла. Если размер графа-решетки принять равным ЬхЬ, адрес свершившегося узтл - Л, то адрес инццндентных узлов д я графа-решетки прямаугопь- ноГО с дилГОнллями (фиГ,7 л) - апре деляются так, как показана иа Фиг,76. Для треугольного Графа-решетки (Фиг.8 а) адреса узлов, инциндецтцых свершившемуся узлу н четной строке, определяются,клк показано нл 1 и .8 б, в нечетной строке - как пакаэлко на фиг,8 в. Дпя каждого направления корректируюп 1 ие числа разпичньгх, +Ь; (Ь); +(Ь+1); 1. Операция вычитания эдменяетсЯ н ЛЛУ 9 ОпОРэцией сложения числа в дополнительном коде, Поэтом; па каждому направлению в узп" 19 постоянной памяти записаны прямые илн дополнительные коды корректирующих чисел и выбираются по30 адресу, который содержит при:цлк типа решетки задаваемый вце устройства, признак направления, поступающий с выхода счетчика 18 направлений, признак строки, поступающий с первого разряда регцстрл 3 адр са 35 признак реверса направления вь;лодл из уэ 1 тл поступающего с блока 2.При апределе иц лдресл ицциндецт - ного узла (опе 1 лтар Л 16,фиг,5) из ячейки памяти узла-предка узла 7 оператицной памяти на второй информаци.- онный вход ЛЛУ 9 поступает адрес свершившегося узпл.Пл первый информационный вход ЛЛУ 9 подается корректирующее число, Результат сложеннн 4 нл 5 записывается в выходной регистр 10. Кодовая комбинация первого н второго сигналов перепспнсния (Ри Рч соответственно) разрядов результата сложения поступает ца второй адрес иый нхад учла 19 постоянной памяти, Перенос Р является переносом со стзршего разряда максимального адреса у 1 па, Перенос Р выбирается иэ стлршега рлзрнпа числа, определяемо га рлзмсрам Ь граФа-решетки Так, ппя примера,приьеденцаго на фиг,7 а Гр Ф-решетка имеет размер 8 х 8, Дпя этого размера Графа-решетки перенос Рляпнется переносом с о-горлэрнпл плоичцаго чпреса, л перенос Р, цз 3-го разряда этого числа,В учпе 9 постоянной плмнтн плн клжпога направления и каждой камбццлцциколов переносов Р, и Р, записанпризнак принадлежности области ппцвыхода зл Границу, Тлк например,для переноса Графа-решетки (Фиг.7 л)по нуеваму направлению определяетсяадрес узла, инциндецтнаго узлу 15,Согласно фиг,76 нэ днончцога адресаузла 15 вычитается корректирующеечисло, равное размеру графа-решеткиЬ, т,е, 8, Операция вычитания злменяетсн операцией сложения двоичногочисла 15 с дополнительным кодом двоичного числа 8, В результате сложенияв АЛУ 9 образуются переносы Р = 1,Р1, По этому комбинации кодон переносон в узле 19 постоянной памятизаписывается признак принадлежностиобласти. Если аналогично определяется адрес узла, инциндентного по нуле.наму направлению узлу 7, то возникают переносы Р 1, Р О. Полученн результате адрес узла, который несвязан с узлам 7, т.е. лежит за границей области. Для данной кодовойкомбинации переносов в узле 19 постоянной памяти будет записан признак выхода за границу области, Посовокупности сигналов, присутствующпх ца всех пяти адресных вхаплх исц.цллу считывания, из узла 19 постоянной памяти считывается признакгрлцицы области,Анапэ признака грацицы области(усповиг В 13, Фиг,5), выполняетсяблгКОМ ПО СИГНаЛу КОда ГраНИцЫ Обплгти с третьего выхода узла 19 по"гонцнсй памяти, па которому или опр;пепнстсянаходится полученный новыйадрес учла в результате сложения чисел в пределах области графа-решетки илн сц выходит эа границу областипо косрдинлтам х или у,Если узел находится в пределахграфа-решетки (условие В 13 не выполнено), то полученный в реэультгтесложения новьЮ адрес узла (операторА 17, Фиг,5) записывается из выходного регистра 10 в ячейку текущегоадреса узла 7 оперативной памяти, лзатем считывается из нее и эапнсывается в регистр 3 адреса, По данному адресу иэ узла 4 памяти метоксчитывается метка "Запрет" узла изапоминается триггером 6 меток.510 25 30 35 55 Последовательно иэ узла 4 памятиметок считываются и записываются втриггер 6 меток метки "Свершение"(оператор А 19, фиг.5), т.е. проверяется был ли узел свершен на предыдущих этапах временного моделирования (условие В 15, фиг.5) илн включенв процесс временного моделирования(условие В 16, фиг.5, проверка выполняется аналогично условию В 2).Отсутствие меток "Свершение" н"фронт" по адресу узла, инциндент.яого свершившемуся направлению,сви-детельствует о том, что этот. узелдолкен быть включен в процесс временного моделирования н по ортогонвльноиу направлению в узел 21 памяти дерева направлений записывается 20метка "Направление", Метки "Направление" е квшдои узле составляютдерево кратчайших путей, Ортогональ. ное направление (оператор А 20,фиг.5)по сигналам реверса направлений исчиФыввиия подается нэ узла 19 постоянной памяти через дешифратор 20направлений на вход выбора кристалла узла 21 памяти дерева направлений.По адресу узла, поступающему с регистра Э адреса, и по сигналам признака метки направления и записив узел 21 памяти дерева направленийзаписывается метка. По этому ае адресу из. узла 4 памяти меток считывается метка "Загрузка" и запоминается триггером. 6 метки.Отсутствие метки "Загрузка" (условие В 17, фиг.5, не выполнено) иранее проанализированных меток "За- ,прет, "Свершение", "фронт", а такие условие невыхода полученного адреса узла за границу графа-решеткипозволяет блоку 2 перейти к этапуподготовки веса узла к временномуиоделированию. Блок 2 возвращаетсяк выполнению последовательностидействий начиная с оператора А 4 ввершине 1 алгоритма (фиг,4),После подготовки к временномумоделированию веса узла, инцнндентного свершившемуся, по нулевому направлению блок 2 определяет адресузла, инцнндентного свершившемуся,но следующему (перному) направлениювыхода иэ узла, Это ие действие выполняется после анализа меток ннциндентного узла по предыдущему(нулевоиу) направлению лрн ныполненик хотя бы одного иэ последовательности условий В 13-В 11 (инииндентный свершившемуся узел выходит эа границу области графа-решетки, завершен, свершен, принадлежит фронту или эагрухсен). Следующее направление выхода иэ свершившегося узла об. раэуется н результате увеличения содержимого счетчика 18 направлений на единицу (оператор А 21 фиг.5).После увеличения направления в:- хода иэ узла на единицу по сигналупеРеполнения пРоверяется перевыполнение счетчика 18 направлений(условие В 18, фиг,5),Отсутствие сигнала переполнениясчетчика 18 направлений свидетельствует о том, что не по всем направлениям ныхода иэ узла определеныадреса инцнндентных узлов, и позволяет продолжить топологическое моделирование. фБлок 2 повторяет последовательность операций, рассмотренную ранее,начиная с оператора А 16 алгоритма(фиг.5).Наличн сигнала перелойнения счетчика 18 направлений свидетельствуето том, что для данного снершившегося узла толологическое моделирование окончено. Блок 2 переходит ктопологическому моделированию следующего свершенного узла иэ списка узлов по данной относительной величинеМвеса, который эллисон по адресу свершенного узла в узле 11 памяти списков, Если свершенный уэел являетсяединственным в списке узлов, то яузле 17 памяти списков по его адресуинформация отсутствует, а я узле 4памяти меток записана метка Конецсписка"Адрес снершениого узла считывается иэ ячеек памяти уэна-предка узла7 олератинной памяти в регистр 3адреса, по нему из узла 11 памятисписков считывается слецуюший адресузла н списке узлов с равной отиоснтельной величиной веса и эаписывается я регистр 13 памяти а иэ узла 4 памяти меток считывается меткаКонец списка и запоминается триггером 6 меток (оператор А 23,фиг.5).Отсутствие меткиКонец списка"в триггере 6 меток (условие В 19не вылслнено фиг.5, пров рка выполняется аналогично ус алию И 2) свидетельствует о тсч тс в регистр3 памяти был считан следующий адрес узла иэ списка адресов узлов сравной относительной величиной веса,Тогда для данного адреса узла повторяется этап топологического моде"пирования аналогично рассмотренномувыше. Блок 2 возвращается к вершинеЭ алгоритма (Фиг.5) и повторяетсявыполнение операций, начиная с оператора А 15.После проведения этапа топологического моделирования для всех узлов списка с относительной величиной веса, равной величине п, младших разрядов кратчайшего пути, привыполнении условия В 20 алгоритма блок2 выполняет заключительную процедуру топологического моделирования.замыкание списка узлов, окончившего временное моделирование, н кольцо,которое предполагает гашение меток"Фронт" н узлах, закончивших временное моделирование, и запись им меток "Свершение", а в узлах, подготонленных к временному моделированию,гашение меток "Загрузка" и запись имметок "фронт".Из узла 7 оперативной памяти (оператор А 24, Фиг.5) считынается ииформация иэ ячейки памяти величины и;младших разрядов кратчайшего пути,передается через управляемый формирователь инверсного кода 8 и шинныйФормирователь 14 в регистр 3 адреса,из узла 1 б памяти идентификаторовсчитывается в регистр 13 памяти иден.тификатор, а н ячейках памяти меток"Исходящий адрес" узла 4 памяти меток по относительной величине весагасится метка "Исходящий адрес", таккак погашен признак начала списка,По адресу последнего узла в списке в узел 17 памяти спискон записывается идентиФикатор (таким образом, 45список замыкается), Для выполненияэтой операции (оператор А 25,фиг.5)последний адрес счиска из ячейкипамяти узла-предка узла 7 оператинной памяти записывается н регистр Эадреса и по этому адресу в узел 17,памяти списков записывается идентификатор из регистра 13 памяти,Кроме того, идентификатор списказаписывается в регистр 3 адреса и55ячейку памяти текущего адреса узла7 оперативной памяти (оператор А 26,фиг,5), По адргсу идентификатораиэ узла 17 памяти списков считывается послелуюпщй адрес с данного списка и записывается н регистр 13 памяти, По этому же адресу иэ узла 4 памяти меток считывается метка пКонец списка" и записывается в триггер 6 меток. Счетчик 18 направлений устанавливается в состояние 0,По первому адресу списка узлов в узле 4 памяти меток гасится метка "Фронт" и записывается метка "Снершение" узла (оператор А 27, фиг.5). Проверяется метка "Конец списка" (услоние В 20, фиг.5), Проверка выполняется по состоянию триггера б метки.Если метка "Конец списка" отсутствует, тогда (согласно оператору А 28, Фиг.5) определяется адрес инциндентного узла по нулевому направлению. Для этого из ячейки памяти текущего адреса узла 7 оперативной памяти считывается адрес узла на второй информационный вход АЛУ 9, на первый вход его из узла 10 постоянной памяти считывается корректирующее число по нулевому направлению. Результат сложения записывается снС ва н ячейку памяти текущего адреса узла 7 оперативной памяти, Направление выхода из узла в счетчике 18 на" правлений увеличивается на единицу.Проверяется переполнение счетчика 18 направлений (условие В 21, проверка выполняется аналогично условию В 18).Отсутствие импульса переполнения (условие В 21 не выполнено, Фиг,5), указывает на то, что не по всем направлениям определены инциндентные узлы. Адрес инциндентного узла записывается иэ ячейки памяти текущего адреса узла 7 оперативной памяти в регистр 3 адреса, из узла 4 памяти меток считывается метка ЯЗагруэка" и запоминается триггером б ме-, ток (оператор А 29, фиг.5)Проверяется наличие в триггере 6 меток метки "Загрузка" (условие В 22) .Если метка "Загрузка отсутствуе 1 (услоние В 22 не выполнено, фиг.5), узел не подготавливается к временному моделированию веса на данном этапе топологнческого моделирования, Тогда блок 2 возвращается к выполнению операций, задаваемых операторами А 28, 29 алгоритма; определяет адрес узда, инциндентного по следую 1424031 26щему (в данком слу чае по первому)направлению, к по этому адресу изузла 4 меток считывается метка "Загрузка".При наличии метки "Загрузка"(условие В 22 выполнено) в ячейкахпамяти меток загрузки узла 4 памятиметок по данному адресу инциндентного узла метка стираФтся, а в ячейках 1 Опамяти меток фронта записывается(оператор АЗО, фиг.5). Затем опре"деляется адрес инцинденткого узлапо следующему направлению (оператор А 28, фиг.5). Процесс повторяется для всех узлов списка пока не будет считана метка "Конец списка"(условие В 20 выполнено).Блок 2 по сигналу признака конечного узла анализирует состояние регис,ра 11 признака узла (условиеВ 23, фиг,5),Если в регистре 11 признака отсутствует признак конечного узла, топроцесс временного моделирования 25весов узлов графа-решетки продолжается, повторяя последовательностьопераций, начиная с вершины 2 и оператора А 12 (фиг.4),Процессы временного и топологического моделирования поочередно повторяются до тех пор, пока на некотором эт ч 1 е топологического мсделирования в списке узлов с данной относительной величиной веса, равнойтекущей величине и. младших раэря 1дов кратчайшего пути, не обнаружится,конечный узел (т.е. условие В 12 алгоритма выполнено, фиг.5),Тогда (в соответствии с оператором А 22 алгоритма) в регистр 11 признака записывается признак конечного узла и блок 2, минуя процедурупоиска инциндентных узлов конечногоузла, анализа их меток и подготовкик временному моделированию иэ весов,переходит к выполнению .последовательности действий, заданных операторомА 23, Из узла 17 памяти списков поадресу конечного узла считываетсяследующий адрес узла в списке узловпосле конечного, а иэ узла 4 памятиметок по адресу конечного узла считывается метка "Конец списка",Если метка "Конец списка" отсутствует (условие В 19 не выполнено),то блок 2 возвращается к последовательности операций, заданных оператором А 15 алгоритма (фиг,5), соглас ко которому в регистр 3 адрес крегистра 13 памяти считывается адрес узла, пах о 1 яиойся следующим после конечного в списке узлов с данкойотносительной величиной веса, Поэтому адресу считывается метка вКокечкый узел" иэ узла 4 памяти меток,Кроме того адрес этого узла записывается в ячейку памяти узла предка-уэла 7 оперативной памяти.Если узел не является кокечным(условие В 12 не выполнено, фиг.5),то процесс топологического моделирования для этого узла повторяетсяаналогично описанному, начиная соператора А 16, т,е. определяются адреса узлов, инциндентных данному,анализируются их метки и, если позволяют условия В 13-17 алгоритма(фнг,5), подготавливаются их весак временному моделированию,Если узел является конечным (условие В 12 выполнено, фиг,5), тосогласно оператору А 23 из списка узлов с данной относительной величинойвеса узла, находящегося в уэле 17памяти списков, выбирается следующий адрес,После достижения конца списка(условие В 19 выполнено) блок 2 переходит к замыканию списка узлов сданной относительной величиной весан кольцо (операторы А 24, 25), к замене меток "Фронт" метками "Сверше-ниек в узлах, составляющиХ данныйспиСок (операторы А 26, 27), к определению инциндентных узлов и заменеметок "Загрузка 1 метками "Фронт" вузлах, подготовленных к временномумоделированию веса (операторы А 2830), После замены меток в свершенныхи инциндектных им узлах,т.е. при достижении конца списка, условия В 20,В 23 алгоритма являются выполненнымии блок 2 прекращает выполнение этаповвременного и топологического моделирования и переходит к заключительномуэтапу выделения кратчайшего путиипи множества равных кратчайших путейиэ полученного на предыдущих этапахдерева кратчайших путей находящихсяв узле 21 памяти направлений блока 1(фиг.2).После окончания этапа топологкческого моделирования в регистре 13памяти (согласно оператору Л 26,фкг,6),находится адрес первого учла кз слис -ка узлов с равной величиной веса,Процесс выделения кра гчайщего пути (или множества кратчайпих путей)иэ полученного дерева кратчайших путей осуществляется с поиска конечно 5го угла из данного списка узлов, Дляэтого (согласно оператору А 31,фиг.б)адрес первого в списке уэлд, которыйнаходится в регистре,13 памяти, записывается в регистр 3 адреса и через,шинный формирователь 14, входной регистр 15, второй вход АЛУ 9, выходной регистр 10 и ячейку текущего адреса узла 7 оперативной памяти,По адресу узла в регистре 3 адреса (первому из списка) из узла 17памяти списков считывается адресследующего узла в списке узлов и записывается в регистр 13 памяти (оператор А 32, фиг.б). По этому ае адресу иэ узла 4 памятр меток считывается метка "Конечный узел и записывается в триггер 6 метки, Счетчик направлений 18 устанавливается в состояние "О" по сигналу сброса в "О"По состоянию триггера б метки проверяется наличие метки Конечныйузел" (условие В 24, фиг.б).Если метка "Конечный узел" отсутствует, из узла 4 памяти меток счи30тывается метка Конец списка и записывается в триггер 6 меток (операторА 40, фиг.б).Если метка "Конец списка" отсутствует (условне ВЗО не выполнено,фиг.б), блок 2 возвращается к последовательности операций,заданных опе"ратором А 31, Следующий адрес узла изсписка узлов записывается в ячейкутекущего адреса узла 7 оперативнойпамяти и регистр 3 адреса (оператор40А 31, фиг.б) и по этому адресу считывается метка "Конечный узел из уз "ла 4 памяти меток, а из узла 17 памяти списков - продолжение списка(оператор А 32, фиг.б).45Если в списке узлов определен адрес конечного узла (условие В 24 выполнено, фиг,б), блок 2 (операторАЗЗ) иэ ячейки текущего адреса считывает адрес конечного узла и передается через управляемый формирователь 8 инверсного кода на второйинформационный вход АЛУ 9, По направлению в счетчике 18 направлений (в данном случае нулевому) на 55первый информационный вход АЛУ 9 иэузла 19 постоянной памяти считывается корректирующее число, АЛУ 9задается функциям сложения чисел, Реэультат сложения записывается в вы"ходной регистр 1 О, Из узла 2 памягти дерева направлений по адресу врегистр 3 адреса (н данном случаеадресу конечного узла) и по направ"лению (в данном случае нулевому) считывается направление и записываетсяв триггер 22 направлениЯ,По сигналу с прямого выхода триггера 22 направлений блок 2 проверяет метку "Направление" (условие В 25,фнг.б). Если метка "Направление"отсутствует (условие В 25 не выполнено), содержимое счетчика 18 направления увеличивается на единицу (оператор А 34, фиг,б), После увеличенияинформации в счетчике 18 направленийна единицу блок 2 проверяет его пе"реполнение (условие В 26, фиг.б).Если переполнение счетчика 18 направлений отсутствует (условие В 26 невыполнено), блок 2 возвращается к выполнению последовательности операций, задаваемых оператором АЗЗ, т.е,определяется адрес инциндентного узла по следующему направлению и поэтому направлению считывается изузла 2 1 памяти дерева направлений изапоминается триггером 22 направлений метка "Направление", Если метка"Направление" присутствует (условиеВ 25 выполнено), то (согласно оператору А 25 фиг.б) адрес инциидентногоузла, находящийся в выходном регистре 1 О, записывается в ячейку анализа у-.ла 7 оперативной пдяти азатем считьеается иэ нее и через управляемый формирователь 8 инверсного хола, шинный формирователь 14 записывается п регистр 3 адреса. Поадресу в регистре 3 адреса из ячеекпамяти меток анализа узла 4 памятиметок считывается метка "Анализ." изапоминается триггером 6 меток, приэтом на вход выбора ячеек памяти узла 4 памяти меток подается код выбора ячеек памяти меток АнализЕсли метка "Анализ" отсутствует (условие В 27 не выполнено, фиг.б), то(согласно оператору А 36, фиг.б) иэвыходного регистра 10 адрес инциндентного узла записывается в ячейкупамяти текущего апрсз узла 7 оперативной памяти, по адресу инциндентного узла, находящемуся в регистре 3адреса, в узел 24 памяти анализа за"писывается. код направления (ортого"нальный по отношению к заданному уз-лу), по которому приходит путь вэтот узел, По этому же адресу н. узла 4 памяти меток считывается метка"Кратчайший путь" и записывается втриггер 6 меток, Счетчик 18 направлений устанавливается в состояниеиО4Операции, выполняемые в конечномузле согласно операторам АЭЗ-А 36 иусловиям В 25-В 28 аналогичны для10всех узлов, выделяемых метками "Анализ" при движении по кратчайшему пути иэ конечного в начальный узел.При достижении начального узла(т.е. При выполнении условия В 26, 15фиг.б) осуществляется разворот и движение по только что выделенному пути.По адресу начального узла в узел4 памяти меток записывается метка зО"Анализ" и считывается метка "Конечный узел" и запоминается триггером6 меток (оператор А 37, фиг,б). Привыполнении этой последовательности . 25операций блок 2 в зависимости отвыбора ячеек памяти меток вьщаетсоответствующий код выбора ячеек памяти, сигнал записи или считыванияи признак четки, равный нулю при га- ЭОшенин или равный единице при ее эаписк.Далее проверяегся метка "Конечный узел", т.е. достижение конечногоузла при движении ко кратчайшему пу.ти иэ начального узла в конечный(условие В 29, фиг.б),Если условие В 29 не выполнено,блок 2 определяет адрес узла, инциндентного начальному, по вьщелеиномукратчайшему т 1 ути и записывается вячейку текущего адреса узла 7 оперативной памяти (оператор АЭ 8,фиг.б).Направление, по которому связаны накратчайшем пути начальный и инциндентный узлы, хранится в узле 24 памяти анализа, но для начального узланаправление будет ортогональным. Иэузла 24 памяти анализа считывается,а в счетчик 18 направлений записывается ортогональный код направлений,По этому направлению и по сигналуреверса направления, поступающему сблока 2, иэ узла 19 постоянной памяти иа первый информационный вход АЛУ9 считывается корректирующев число55прямого направления выхода из узла.Иэ ячейки памяти текущего адресе узла7 оперативной памяти через управляемый Формирянгель В иквер.лого о,л на второй инф 1 рмационньй вхол ЛЛУ 9 считывается адрес начального узла, АЛУ 9 задается функция сложения чисел, результат сложения записывается в ячейку текущего адреса узла 1 оперативной памяти.Адрес узла, инциндектный начальному по кратчайшему пути, из ячейки текущего адреса узла 1 оперативной памяти (оператор АЭ 9, фиг,б) записывается в регистр Э адреса, а содержимое счетчика 18 направлений увеличивается на единицу, Продолжается просмотр меток Направление" для данного узла, т.е, поиск равных кратчайших путей в узелПовторяется последовательность операций, определенная операторами АЭЭ-АЭ 6 и условиями В 25-В 28. Если других кратчайших путей В данный узел нет, после переполнения счетчика 18 направлений (условие В 26 вья 1 олненофиг.б) данному узлу присваивается метка "Кратчайший путь", гасится метка "Анализ" и считывается метка "Конечный узел" (оператор АЭ 7, фиг,б),Если сущестует еще один кратчайший путь в данцый узел, то из данного узла по этому пути проходят в начальный узел, отмечая узлы метками "Анализ", а затем осуществляется возврат по отмеченному пути. Таким образом, при движении пократчайшему пути из начального узла в конечный вьщеляются кратчайшиепути в каждый узел этого пути.При достижении Конечного узла(выполнение условия В 29, фиг.б) блоком 2 (оператор А 40, фиг,б) из узла 4 памяти меток считывается меткаКонец списка и запоминается триггером 6 меток,Если метка "Конец списка" отсутствует (условие ВЭО ие выполнено),т,е. в списке узлов, окзцчц 1 ших временное моделирование, были проанализированы метки "Конечный узел не вовсех узлах списка, дка 1 испискаузлов продолжается, выполняется последовательность операций в еоогветствии с операторами АЭ, ЛЭ 2 ц условием В 24,Если в списке узлов бкаруж;лается еще один конечный уя, то процесс выделения кратл г цуги изданного узла цорч 1 т я,Если проведен анализ всех узлов списка (условие В 30 выполнено), ра - бота устройства прекраша тся,В результате решения задачи о кратчайшем пути ка предложенном устроЯстве в узле 21 памяти дерева на- правлениЯ присутствует дерево кратчайших путей в виде направлений выхода из узла; в узле 11 памяти списков"фронты кратчайших путей, замкнутых в кольцо; в узле 4 памяти меток в области меток "Кратчайший путь" кратчайший путь (или множество крат ,чайших путей), отмеченный метками ,по узлам, через которые он проходит; в ячейках памяти и младших и и1старших разрядов кратчайшего пути узла 7 оперативной памяти - величина кратчаЯшего пути между задан ными начальнымк и конечными узлами.Решение задачи на неориентировакных графах-решетках с информацией в узлах в устройстве достигается эа счет использования основных узлов: 25 АЛУ 9 совместно со счетчиком 18 направлений и узлами 7 и 19 постоянной памяти,эффективной организации хранения инФормационных и оперативных меток в узле 4 памяти меток, 3 О органиэации вычислительного процесса в соответствии с приведенным алгоритмом, а также реализации связей узлами блока 1 моделирования графа и блока 2 микропрограммного управ 35пения,Формула изобретенияУстройство для решения задач на графах, содержащее блок микропрограммного управления и блок моделирования графа, содержащий узел памяти весов, узел памяти идентификаторов, узел памяти списков, регистр памяти, регистр адреса, входной и выходной регистры, выход узла памяти идентификаторов соединен с информационным нходом регистра памяти, выход которого соединен с информационным входом узла памяти списков, входы записи узлов памяти весов, идентификаторов и списков соединены соответственно с первым, вторым и третьим вцходамп блока микропрограммного управления, о т л и ч а ю ш е е с я 55 тем, что, с целью расширения функцкокалыюх возмо 1 з 1 остей за счет обеспечения решения задач не кеоркентированных графах, в блок моделированияграфа введены узел памяти мосток,узел памяти дерева направлений, узелпамяти направлений анализа, узелоперативной памятк, узел постояннойпамяти, арифметико"логический узел,дешифратор меток, дешифратор направлений, управляемый формирователь инверсного кода, шинный формирователь,счетчик направлений, триггер меток,регистр признака, триггер направлений, триггер конца ввода, адресныевходы узлов памяти весов идентификаторов, списков, меток, дерева напраЫений к направлений анализа ипервый адресный вход узла постоянной памяти соединены с выходом регистра адреса, информационный входкоторого соединен с информационнымивходами узлов памяти весов и идентификаторов и списков, выходом регистра памяти и информационным входомвыходом шинного формирователя, выход которого соединен с инфориацион"ным входом входного регистра, выходкоторого соединенс первым выходомузла постоянной памяти и первым кнформациокньпч входом арифметико-логического узла, информационный выход которого соединен с информационным входом узла оперативноЯ памяти,выход которого соединен с информационным входом выходного регистра,выход которого соединен с информа"циояным входом управляющего Формирователя инверсного кода, выход которого соединен с икформационньявходом шинного формирователя и свторым инФормационным входом аркфметико-логкческого узла, первый ивторой выходы переполнения разрядов ко; орого соединены с разрядамивторого адресного входа узла постоянной памяти, вход "Выбор кристалла" узла памяти меток соединен с выходом дещифратора меток, а выходсоедикен с информационным входомтриггера меток, выход которого соединен с инФормационным вхоцом регистра признака, информационный вход,1триггера направлений соединен с выхсдом узла памяти дерева направлениЯ,выход "Выбор кристалла" которого соединен с выходом дещпФратора направлений, вход которого соединен с вторч выходом узла постоянной памяти,трет й адресный вход которого соединен с выходом счетчика каправлений иинформационным входом узла памяти направлений анализа, выход которого соединен с информационным входом счетчика направлений, выход признака. переноса арифметико-логического узла соединен с информационным входом триггера конца ввода, вход записи регистра адреса, входы записи и признака метки узла памяти меток, информационный вход дешифратора меток, синхронизирующие входы регистра признака, триггеров меток, направлений, конца ввода, входы записи, "Выбор кристалла" и адресный вход узла , оперативной памяти, управляющий вход управляемого формирователя инверсного кода, вход кода выполняемой функции арифметико-логического узла, вход установки в нулевое состояние ьыходыого регистра, входы "Выбор кристалла" узлов памяти весов, идентификаторов и списков, входы выбора реаима и записи входного регистра и регистра памяти, входы выбора реаима и "Выбор кристалла" шинного формирова теля, счетный вход, входы установки в нулевое состояние и записи счетчи"ка направлений, четвертый адресный вход и вход считывания узла постоянной памяти, входы признака метки и записи узла памяти дерева направлений, входы записи и выбора кристалла узла памяти направлений, анализа соединены соответственно с четвертого по тридцать шестой выходамиблока микропрограммного управления,пятый адресныЛ вход узла постояннойпамяти является входом признакатипа решетки блока моделирования графа, а первый и второй выходы регистра признака, прямые выходы триггеров метки, направлений, конца ввода, выходы переполнения разрядов ирезультата сравнения чисел арифметищо ко-логического узла, выход переполнения счетчика направлений, информационный выход узла постоянной памяти соединены соответственно с первого по девятый входами логическихзя условий блока микропрограммного управления,1424031 3 адреса, узел 4 памяти меток, дешифратор 5 меток, триггер 6 меток,узел7 оперативной памяти, управляемыйформирователь 8 инверсного кода,арнфметико-логический узел 9, выходной регистр 10, регистр 11 призна"ка, узел 12 памяти весов, регистр13 памяти, шинный формирователь 14,входной регистр 15, узел 6 памятиидентификаторов, узел 17 памяти списков, счетчик 18 направлений, узел19 гостоянной памяти, дешифратор 20направлений, узел 21 памяти дереванаправлений, триггер 22 направлений,20 Блок 1 моделирования графа содержит регистр 3 адреса, узел 4 памятиметок, дешифратор 5 меток, триггер6 меток, узел 7 оперативной памяти,управляемый формирователь 8 инверсного кода, арифметико-логический уэел(АЛУ) 9, выходной регистр 10 и регистр 11 признака, узел 12 памятивесов, регистр 13 памяти, шинный фон мирователь 14, входной регистр 15, З 0 узел 16 памяти идентификаторов, узел17 памяти списков, счетчик 18 направлений, узел 19 постоянной памяти,дешифратор 20 направлений, узел 21памяти дерева направлений, триггер 22,направлений, триггер 23 конца ввода,узел 24 памяти направлений аналиэа. 1,Изобретение относится к цифровойвычислительной технике, в частностик устройствам для обработки информации специального назначения, и можетбыть использовано при построении спе- циализированных вычислительных устройств для решения вариационных и игорных задач при сведении их к задаче о кратчайшем пути на графе типанеориентированкэй решетки.Цель изобретения - расширение функциональных возможностей за счет дяеспечеиия решения задач на неориентированных графах решетках с информацией в узлах.На фиг.1 приведена блок-схема устройства; на фиг.2 - функциональная схема блока моделирования графа;на ф фиг.З - одна нэ возможных функциональных схем реалиэацни блока микро" программного управления; на фиг.4-6- алгоритмы функционирования блока микропрограммного управления на этапе поиска множества начальных узлов и подготовки их веса к временному моделированию, на этапах временного н топологического моделирования, на этапе выделения кратчайшего илн множества кратчайших путей иэ полученного дерева кратчайших путей соответственно; на фиг.7 а - четйрехугольный с диагоналями граф-решетка с запрещенными областями; на фиг.7 б - определение адресов инцин .дентных узлов в четырехугольном с диагоналями графе-решетке;на фиг.8 а -триггер 23 конца ввода, узел 24 ламяти направлений анализа, Решение задачи на неориентированных графах-рещетках с информацией в узлах в устройстве достигается эа счет использования арифметнко-логического узла 9 совместно со счетчиком 18 и узлами 7 и 19, эффективной органиэации хранения информационных и оперативных меток в узле 4 памяти меток, органиэации вычислительного процесса в соответствии с приведенным алгоритмом. 8 ил. 2треугольный граф-решетка;на Фиг,8 бопределение адресов узлов, инциндентных узлам в четной строке графарешеткн; на фиг.8 в - то же, в нечет 5 ной строке,Устройство содержит блок 1 моделирования графа, соединенный с блоком 2 микропрограммного управления.Блок 1 моделирования графа пред 10. назначен для выполнения арифметико,логических операций и функций хранения исходной промежуточной информации и результатов решения, блЬк 2микропрограммного управления - для15 определения взаимодействия междууэламн блока 1 моделирования графапри моделировании графа-решетки иорганизации вычислительного процесса, 142403Редактор Л каз 4689/5 н та ыт сква пигрдфическое предприятие, г, Ужгород, ул. Проектная,роизводственн 81 1 Б 1 ПИпо113035, М аж 704дарственного коми изобретений и от Ж"35, Раушская ю ВщвПодпиСССР д, 4Регитрадр а иецназиен П хранения адресов текущих улов н преп ставляет собой регистр с параллельным приемом и выдачей информации. Узел 4 памяти меток служит иля хранения признаков узлов: "Начальньй узел", Конечный узел", "Запрещег ный узел", и операционных меток: Загрузка узла", "Свершение узла", фронт, "Исходный адрес (первый адрес узла в списке адресов узлов), "Конец списка" (последний адрес в списке адресов узлов), "Кратчайший гуть", "Анализ кратчайшего пути". Дешифратор 5 меток применяется для дешифрации кода метки и сигналы выборки кристалла соответствующих ячеек памяти узла 4 памяти меток. Триггер 6 метки фиксирует метку гри считьнанни ее из узла 4 памяти меток, Узел 7 оперативной памяти хранит в процессе решения оперативную информацию, а именно текущий адрес узла, младшие и. разряды величины кратчайшего пути, старшие и разряды величины кратчайшего пути, относительню величину веса узла, адрес узла предка, указатель количества просмотренных идентификаторов, адрес анализируемого узла. Управляемый фор миронатель 8 инверсного кода предназначен для передачи прямого или инверсного кода данных.АЛУ 9 служит для выполнения арифметических и логических оиараций на этапах топологического моделирования при вычислении адресов узлов, инциндентных свершившимся узлам, и времен ного моделирования ири вычислении неличины кратчайшего пути. Выходной регистр 10 используется для промежуточного хранения результата арифметико-логических операций и представляет собой регистр с параллельным приемом и выдачей информации. Регист 11 признака предназначен для фиксирования признаков начального и конеч ного узла, узел 12 памяти весов - для хранения информации о весах узлов графа-решетки. Регистр 13 памяти является многорежимным буферным регистром с тремя состояниями на выходах и иреднаэнз ен для параллельного приема, хранения и параллельной выдачи инФормации. 61 инный формировател 14 управляет шинами данных по трем напранлениям. Входной регистр 15 является многорежимиым буферным регис ром тремя состояииями на выхолах ииредназначе пля параллалиго приема, хранения н параллельной выдачиинформации. Учел 16 памяти идентификаторов хранит адреса узлов, являюшихся идентификаторами списков с равной относительной величиной веса,узел 17 памяти списков - списки адре 10 сон узлов с равной относительной величиной веса. Счетчик 18 направленийпредназначен для задания кода направления выхода иэ узла, по которому вычисляется адрес инциндентного узл15 на этапах тоиологичаского моделиронан 41 и ныделения кратчайшего путиили множества равных кратчайших путей из полученного в процессе решения дерева кратчайших путей. Узел20 19 постоянной памяти служит для хра,нения корректируюппх чисел по прямым и ортогональньм направлениям выхода из узла, прямых и преобразованныхкодов направлений выхода иэ узла,25 признаков границы области. Дешифра"тор 20 направлений дешифрирует коднаправлений в сигналы выбора кристалла соответствующих ячеек памяти. Узел21 памяти дерева направлений пред 30 назначен для хранения дерева кратчайших путей по направлениям вьхода нз узла графа-решетки. Триггер 22иапрангений служит для фиксированияметки ири считывании ее из узла 21амяти дерева направлений, Триггер23 конца ввода предназначен для фиксиронания момента превышения максимальной величины адреса на этапе ввода начальных узлов в процессе времен 40 ного моделирования. Узел 24 памятианализа хранит код направления ньхода из узла, на котором прерываетсяанализ дерева кратчайших путей.Блок 2 микропрограммного управ 4 В ления содержит генератор 25 импуль"Р сон, счетчик 26 имгульсов, дешифратор 27, коммутатор 28, узел 29памяти переходов, перный 30, второй31 регистры и узел 32 памяти управляющих сигналов.Генератор 25 импульсов предназначен для формирования синхронизирующих импульсов, счетчик 26 импульсовдля образования циклов работы блока2, дешифратор 27 - для дешифрации ь кода счетчика 26 импульсов и выдачиразнесенных по времени синхрониэи"рующнх импульсов на входы записи т рег.гстров 30 и 31. Коммутатор 28 пе 142403150 реключает сигналы, поступающие с первого по девятый входов на выход.Входные сигналы являются условиями,по которым блок 2 микропрограммногоуправления должен переходить согласно алгоритму его работы к выполнениюсоответствующих управляющих операций. Узел 29 памяти переходов хранитматрицу переходов блока 2 иэ одногосостояния в последующее в зависимости от аНализируемых условий согласно алгоритму его работы. Регистры30 и 3 1 предназначены для хранениясостояния блока 2 на промежуточномэтапе функционирования. Использование двух регистров обусловлено исключением в работе блока 2 гонок, Узел32 памяти управляющих сигналов служит для хранения матрицы управляющих сиг налов.Устройс гво содержит вход 33 задания тица конфигурации моделирующего граФа-решетки, попарно соединяемые выходы 34-105 блока 2 микропрограммного управления и блока 1 моделирования графа соответственно, попарно соединяемые выходы и входы 106 123 логических условий блоков 1 и 2 соответственно и вход 124 пуска устройства.Решение задачи о кратчайшем пути на графе-решетке показано на фиг.4 Ь, где изображена совокупность и взаимосвязь операторов и условий.Алгоритм работы устройства содержит А 1-А 4 1 операторов и В 1-ВЗО условий:А 1 - передача содержимого ячейки памяти текущего адреса узла 7 опе п ративной памяти в регистр 3 адреса,ю считывание из узла 4 памяти метки Начальный узел" и запоминание ее на триггере 6 меток;А 2 - передача содержимого ячейки5 памяти текущего адреса узла 7 оперативной памяти в АЛУ 9, увеличение величины содержимого ячейки памяти текущего адреса на единицу, передача результата сложения в регистр 3 адреса, считывание метки "Начальный узел" иэ узла 4 памяти меток и запоминание ее на триггере 6 меток;ЛЗ - установка "1" триггера 23 конца ввода55А 4 - считывание веса узла иэ узла 12 памяти весов, запись веса узла во вхоцн й регистр 15, запись метки "За рузка" я учел памяти меток, запис ь признака 11 ачал ный у чл я регистр 11 признака, считынание информации из вхопного реги.тра 15 ипередача этой информации на первыйинформационный вход АЛУ 9, передачаинверсного кода с выходов управляемого формирователя инверсного кола 8на второй информационный вход АЛУ 9;Л 5 - считывание п 1 младших разрядов кратчайшего пути иэ соответствующей ячейки памяти узла 1 оперативной памяти, передача этой величинына второй информациэнный вход АЛУ9; суммирование величины, поступающей на входы АЛУ 9 и запись результата в выходной регистр 1 О;АЬ - запись информации из выходного регистра 10 в ячейку памяти относительной величины веса мала 7 оперативной памяти, считывание относительной величины веса из узла 7 оперативной памяти и запись ее в регистр3 адреса, считывание идентификаторовиз узла 16 памяти идентификаторов изапись в регистр 13 памяти, считывание метки "Исходящий адрес" иэ узла4 памяти меток и фиксирование еетриггером Ь меток;А 7 - считывание ячейки памяти текущего адреса узла 7 оперативной памяти и запись этой информации в узел16 памяти идентификаторов, записьметки "Исходящий адрес" в узел 4 памяти меток, запись в регистр 3 адреса информации из ячейки памяти текущего адреса узла 7 оперативной памяти;А 8 - считывание информации из ячейки памяти узла-предка узла 7 оперативной памяти и запись ее в регистр 3 адреса, считывание информации йэ узла 17 памяти списков и запись ее в регистр 13 памяти, считывание метки "Конец списка" иэ узла 4 памяти меток и запоминание ее триггером 6 меток;А 9 - считывание информации из ячейки памяти текущего адреса узла 7 оперативной памяти, запись этой информации в узел 17 памяти списков, гашение меткиКонец списка" в узле 4 памяти меток, запись считываемой информации иэ ячейки памяти текущего адреса узла 7 оперативной памяти в регистр 3 адреса;А 10 - запись метки "К.неп списка" в узел 4 памяти ме 1 ок;А 11 - считываяг Фрмации из регистра 13 памяти и ., ппсь этой ин.031рой информлционный вход АЛУ 9, считывание корректирующего числа нз узла19 постоянной памяти на первый информационный вход АЛУ 9, сложениекорректирующего числа с адресом узла-предка и запись результата в выходной регистр 10 (т.е. определениеадреса узла, инциндентного свершившемуся), считывание по направлениювыхода нэ узла и кодовой комбинациисигналов переполнения разрядов АЛУ9 н узла 19 постоянной памяти признака границы области;А 17 - запись информации нэ выходного регистра 10 в ячейку памяти текущего узла 7 оперативноЯ памяти,а затем в регистр 3 адреса считывание метки "Запрет" иэ узла 4 памятиметок и запоминание ее триггером 6метки;А 18 - считывание метки "Свершение" из узла 4 памяти меток и запоминание ее триггером 6 меток;5 А 19 - считывание метки "Фронт"иэ узла 4 памяти метой и запоминаниеее триггером 6 меток;А 20 - запись метки "Направление"в узел 21 памяти дерева направлений,0 считывание метки "Загрузка" из узла4 памяти меток и запоминание ее триггером 6 меток;А 21 - увеличение содержимого счетчика 18 направлений на единицу;А 22 - запись в регистр 11 призна 35ка конечного узла;А 23 - считывание информации иэячейки памяти узда-предка узла 7 оперативной памяти и запись ее в ре 40 гистр 3 адреса, считывание метки, "Конец списка" иэ узла 4 памяти меток, считывание по этому же адресуинформации из узла 17 памяти спискови запись ее в регистр 13 памяти;45А 24 - считывание информации изячейки памяти п. мпадших разрядовкратчайшего пути узла 7 оперативнойпамяти н зались ее в регистр 3 адреса, считывание информации иэ узла 16памяти идентификаторов и запись этой50,ичформации в регистр 13 памяти, сти"рание метки "Исходящий адрес" в узле4 памяти меток;А 25 - считывание информации иэячейки памяти узла-предка узла 7 опе 55ративной памяти и запись ее в регистр3 адреса, считывание информации иэрегистров 13 памяти и запись ее вузел 17 памяти списков;о 14 24 формалин вуэеп 17 памяти списков;А 12 - считывание информации пэ ячейки памяти и, младших разрядов величины кратчайшего пути уэла 7 оперативной памяти и передача этой информации в АЛУ 9, увеличение величины п младших разрядов кратчайшего1пути на единицу и запись в ячейку памяти величины и, младших раэря дов кратчайшего гути узла 7 оператив- ноЯ памяти, считывание этой величины из узла 7 оперативной памяти н передача ее в регистр 3 адреса, считывание информации иэ узла 16 памяти 1 идентификаторов и запись ее в регистр13 памяти, считывание метки вИсходящий адрес" иэ узла 4 пакяти меток и запоминание ее триггером 6 меток;А 13 - считывание информации из 2 ячейки памяти величины п старших разрядов кратчаЯшего путй узла 7 оперативной памяти и передача ее в АЛУ 9; суммирование этоЯ величины с единицей переноса из и; мпадших раэ рядов величины кратчайшего пути и запись результата в ячейки памяти величины п 1 старших разрядов кратчайшего пути узла 7 оперативной памяти;А 14 - считывание информации иэ 3 ячейки памяти указателя количества просмотренных идентификаторов узла 7 оперативной памяти и передача ее в АЛУ 9, увеличение этой информации на единицу, запись результата сложения в ячейки памяти указателя количества просмотренных идентификаторов узла 7 оперативной памяти, запись максимальной величины адреса идентификаторов во входной регистр 15 и подключение его выходов к первому .ияформационноку входу АЛУ 9; передача на второй информационный вход АЛУ 9 указателя количества просмотренных идентификаторов, сравнение чисел, поступающих на входы АЛУ 9;А 15 - считывание информации иэ регистра 13 памяти и запись ее в регистр 3 адреса и ячейку памяти узла- предка узла 7 оперативной памяти, установка счетчика 18 направлений в нулевое состояние, установка в нулевое состояние счетчика памяти указателя количества просмотренных иденвюг тификаторов, считывание метКи Конечный узел" из узла 4 памяти меток;А 16 - считывание информации иэ ячейки памяти узла-предка узла 7 оперативной памяти, передача ее на вто 1424031 О20 А 26 - считывание информации иэ регистра 13 памяти и запись ее в регистр Э адреса и в ячейки памяти текущего адреса узла 7 оперативной рамяти, сброс в "О" счетчика 18 напрввленкя, считывание инфориации иэ узла 17 памяти списков и запись ее в регистр 13 памяти, считывание метки"Конец списка" иэ узла 4 памяти ме ток и запоминание ее треггерои 6 метки;А 27 - запись метки "Свершения" в узел 4 памяти меток и гашение метки "фронта" 5А 28 - считыванке инФормации иэ ячейки памяти текущего адреса узла 7 оперативной памяти на второй информационный вход АЛУ 9, считывание корректирующего числа из узла 19 постояннор памяти и передача его на первый информационный вход АЛУ 9, выполнение функции сложения чисел в АЛУ 9 и зались результата сложения в ячейку памяти текущего адреса узла 25 7 оперативной памяти, увелччение содерзимого счетчика 18 направлений на единицу;А 29 - считывание информации иэ ячейки паияти текущего адреса узла 30 7 оперативной памяти и апись ее в регистр 3 адреса; считывание метки "Загрузка" иэ узла 4 памяти и запоминание ее триггером 6 памяти;АЗО - запись метки "фронт" в35 узел 4 памяти меток и гашение метки "Загрузка";. АЗ 1 - считывание информации нз регистра 13 памяти, передача ее в регистр 3 адреса и ячейку текущего 40 адреса узла 7 оперативной памяти;А 32 ". чктывание информации из узла 17 памяти списков и запись ее в регистр 13 памяти,установка счетчика 18 направлений в нулевое состояние, считывание иеткк "Конечный узел" иэ узла 4 памяти меток и запоминание ее триггером 6 меток;А 33 - считывание ячейки памяти текущего адреса узла 7 оперативкой памяти и передача информации на второй информационный вход АЛУ 9, считывание корректирующего числа из узла 19 постоянной памяти на первый информационный вход АЛУ 9, сложение чисел в ЛЛУ 9 н запись результата сложения в выходной регистр 10, зались метки "Анализ" в ячейки памяти меток энэ изэ узла 4 памяти меток по прямому направлению, т,е, по направлению в счетчике 18 направлений, считывание метки. направления кз узла 21 памяти дерева направлений и запоминание ее триггером 22 направлений;А 34 - увеличение содержимого счетчика 18 направлений нв едкницу;А 35 - запись информации из выходного регистра 10 в ячейку памяти анализа узла 7 оперативной памяти, в затем считывание иэ нее информации и передача в регистр 3 адреса, считывание метки "Анализ" из узла 4 памяти меток к запоминание ее триггерои 6 меток;А 36 - запись информации из выходного регистра 10 в ячейку памяти текущего адреса узла 7 оперативной памяти, запись содержимого счетчика 18 направлений в узел 24 памяти анализа, считывание метки "Кратчайший путь" из узла 4 памяти меток н запоминание ее триггером 6 меток, установка счетчика 18 направлений в нулевое состояние;А 37 - запись мвткк "Кратчайший путь" в узел 4 памяти меток, гашение метки "Анализ" и считывание метки "Конечный узел" кз узла 4 памяти меток и запоминание ее триггером 6 меток;А 38 - считывание направления из узла 24 памяти анализа и запись его в счетчик 18 направленийсчитывание корректирующего числа кэ узла 19 постоянной памяти по ортогональному направлению на первый информационный вход АЛУ 9, считывание информации нэ ячейки памяти текущего адреса узла 7 оперативной памяти к передача на второй информационный вход АЛУ 9, сложение числа в АЛУ 9 к запись результата в ячейку памяти текущего адреса узла 7 оперативной памяти;А 39 - увеличение содержимого счетчика 18 направлений на единицу, счи,тывание информации из ячейки памяти текущего адреса уэа 7 оперативной памяти к запись ее в регистр 3 адреса;А 40 - считывание метки "Конец списка" из узла 4 памяти меток к запоминание ее триггером 6 меток;А 41 - конец,В - проверка у ии иугка устройства;В 2 - ироверкл ."Н,чльн11узели и,проверка метки Анализпроверка метки пКратчайшийи р, в ер ка метки Конеч ный В 3 - пролерк,ч перепмлнения и 1мплдших разрядов Ы 1 У 9;В 4 - проверка признлкл начальногоузла в ре 1 истре 11 признака,5В 5 - проверка условия равенствачисел, поступающих на первый и второй ннформациснпые входы ЛЛУ 9;В 6 - проверка метки "Исходящийадрес"; 10В 7 - проверка состояния триггера, 23 конца ввода;В 8 - проверка метки "Конец списка";В 9 - проверка переполнения и; 15младших разрядов величины кратчлйше 1го пути;В 10 - проверка метки "ИсходящийиадресВ 11 - проверка условия равенства 2 Оуказателя количества просмотренныхидентификаторов максимальной величине. адреса узла 16 памяти идентификаторов;ф 12 - проверка признака конечного 25узла;В 13 - гроверка выхода адреса узлаза границу области графа-решетки;В 14 - проверка метки "Запрет узла"; 30В 15 - проверка метки "СвершениеиузлаВ 16 - проверка метки "Фронт";В 7 - проверка метки "Загрузкаузла";35В 18 - проверка переполнения счетчика 18 направлений;В 19 - проверка метки "Конец списка".,.В 20 - проверка метки пКонец списка";В 21 - проверка переполнения счет,чика 18 направлений;В 22 - проверка метки "Загрузка узла"; 45В 23 - проверка признака конечного узла;В 24. - проверка признака конечногоузла;В 25 - проверка метки "Направл е,ниеВ 26 - проверка переполнения счетчика 18 направлений; ИЗО - проверка метки Конец спискаУстропство рлбстает следующим образом,В Узел 12 памяти весов блока 1 записана информация о весах узлов,л узел 4 памяти меток - метки начальных, конечных и запрещенных узлов, Вспомогательные шины для вводаинформации на фиг.2 не показаны. Вузел 29 памяти переходов блока 2 записана последовательность выполненияоператоров алгоритма работы в зависимости от входных условий. В узел32 памяти управляющих сигналов записана совокупность управляющих сигналов при выполнении соответствующихопераций.По сигналу Пуск, т.е. при выполнении условия В 1 алгоритма(фиг,4) блок 2 приступает к поискуначальных узлов и подготовке их весов к временному моделированию.Поиск начальных узлов осуществляется с адреса, находящегося в ячейке памяти текущего адреса (например,нулевого) узла 7 оперативной памяти.Последовательно для каждого адресаузла считываются метки "Начальныйузел", находящиеся в узле 4 памятиметок (оператор А 1, фиг,4). Начальный адрес узла из ячейки памяти те"кушего адреса узла 7 оперативкой памяти передается через управлчемыйформирователь 8 инверсного кода,шинный формирователь 14 и записывается в регистр 3 адреса. Осуществляется чтение метки Начальный узелпо данному адресу иэ узла 4 памятиметок и запоминание ее триггером 6меток. Если узел не является начальным то триггер 6 метки остается всостоянии 0, в противном случаеи 11он устанавливается в состояние 1Проверка состояния триггера 6меток выполняется (условие В 2 алгоритма, фиг,4) по сигналу признакаметки с единичного выхода триггераЬ метки. Когда триггер 6 метки находится в нулевом состоянии, блок2 организует вычисление адреса слепдующего узла и считывание метки Начальный узел" из узла 4 памяти меток(оператор А 2, фиг.4).Для вычисленияадреса информация иэ ячейки памятитекущего адреса узла 7 оперативнойпамяти через управляемый формирова"тель инверсного кода 8 передается нв,второй вход АЛУ 9, в котором увеличивается на единицу и вновь записывается в ячейку памяти текущего адреса узла 7 оперативной памяти. Данный адрес вновь передается в регистр 3 адреса, по нему считываетсяметка "Начальный узел и запоминается триггером 6 меток.После увеличения адреса узла 1 рна единицу в АЛУ 9 блоком 2 контролируется переполнение п младшихразрядов результата сложения (условие ВЗ, фиг,4) по сигналу с выходапереноса АЛУ 9, Перевыполнение свидетельствует о том, что зо всех узлах графа-решетки проанализированаметка начального узла.При отсутствии переполнения и;младших разрядов данных АЛУ 9 (т.е. 2 русловие ВЗ не выполнено) проверяетсяметка "Начальный узел" (выполнениеусловия 82, фиг.4).Переполнение пмладших разрядовданных АЛУ 9 (условие ВЗ выполнено,Фиг.4), свидетельствуето просмотре меток Начальный узел" по всемадресам узлов графа-решетки. При переполнении триггер 23 конца вводаустанавливается в состояние "1" (оператор АЗ, фиг.4).Далее блок 2 проверяет состояниерегистра 11 признака (условие 34,Фиг.4),Единичное состояние первого разряда регистра 11 признака свидетельствует о том, что в графе-решеткесуществует начальный узел (или спи- .сок начальных узлов) и он подготовлен к временному моделированию, анулевое состояние - о том, что припросмотре всех узлов граФа-решеткиблок 2 не обнаружил начальный узел,с которого можно зачать процесс. решения задачи. Во втором случае устройство возвращается в исходное состояние (к выполнению, условия В 1,фиг.4). Для дальнейшей работы оператору нужно вести начальный узел(или множество начальных узлов) инажать повторно кнопку "Пуск". 0 Если триггер 6 метки находится в состоянии " 1" (условие В 2 выполнено), т.е. узел является начальным, то блок 2 осуществляет подготовку веса этого узла к временному моделированию. Осуществляется (опе-ратор А 4, фиг.4) фиксирование момента подготовки к временному моделирозалию начального узла - запись признака начального узла в регистр 11 признака и чтепне веса узла из узла 12 памяти веса н регистр 13 па" мяти. Одновременно записывается в узел 4 памяти меток метка "Загрузяка , а все узлы из регистра 13 памяти через винный формирователь 14 записывается во входной регистр 15. Для определения признака Фиктивно" стн узла его вес сравнивается с нулем, Так как сигнал управления, уп - равляемый формирователем инверсного кода 8, отсутствует, то на вторгм информационном входе АЛУ 9 присутствуют потенциалы лоигческой "1АЛУ 9 выполняет сравнение инверсного числа, присутствующего на вторсм информационном входе, с числом, поступающим иэ входного регистра 15.Проверяется условие равенства веса узла нулю (условие В 5,фиг,4) по сигналу с,выхода результата сравнения АЛУ 9При неравенстве веса узла нулю (условие В 5 не выполнено) АЛУ 9 определяется относительнан величина веса узла (оператор А 5, фиг.4) путем суммирования веса узла, находящегося во входном регистре 15, с величиной и; мпадшик разрядов кратчайшего пути, которая 11 одается на второй информационный вход из ячейкн памяти и 1 младших разрядов кратчайшего пути, узла 7 оперативной памяти через управляемый Формирователь 8 инверсногокода. Результат сложения записывается в выходном регистре 10. Относительная величина веса из выходного регистра 10 (оператор А 6, Фиг,4) записывается в ячейку памяти относительной величины веса узла 7 оперативной памяти, затем зта величина передается в регистр 3 адреса через управляемый формирователь 8 инверсного кода и шинный Формирователь 14. По относительной величине веса параллельно считывается метка "Исходящий адрес" из уэна 4 памяти меток и фиксируется триггером 6 меток, причем информационный вход дешифратора 5 меток годается код ячейки памяти меток "Исходящий адрес", а из узла 16 памяти идентификатора считывает.я идеч; ификатор списка и записывается в регистр 13 памяти.По относительной величин веса.в узел 16 памяти идентификаторов изячейки памяти текущего адреса узла7 оперативной памяти загружаетсяУадрес узла, п одгот а вл ива е мог о к временному моделированию, а в узел 4памяти меток записывается метка"Исходящий адрес" (оператор А 7,фиг.4), В регистр 3 адреса записывается адрес узла, подготавливаемогок временному моделированию, иэ ячейки памяти текущего адреса узла 7 оперативной памяти.Если метка Исходящий адрес отсутствует (условие В 6 не выполнено),т.е. список узлов с данной относительной величиной веса отсутствует(проверка выполняется аналогично условию В 2), тогда в узел 4 памяти меток записывается метка Конец списка" (оператор А 10, фиг.4). Если метка "Исходящий адрес" присутствует в триггере 6 меток (усло вие В 6 выполнено), т.е, список узлов с данной относительной величиной веса бып ранее сформирован. тогда по адресу нового идентификатора списка (адресу узла подготавливаемого к вре менному моделированию, находящемуся в регистре 3 адреса) в узел 17 списков записывается предыдущий идентиФикатор, который находится в регистре 13 памяти (оператор А 11, фиг.4).35Рассмотрим последовательность операций при подготовке к временному моделированию Фиктивных (вес равен нулю) узлов (условие В 5 выполнено)Адрес узла из ячейки памяти узла- предка узла 7 оперативной памяти записывается в регистр 3 адреса и по нему осуществляется чтение узла 17 1памяти списков и запись в регистр 13 памяти, По этому же адРесУ из Узла 45 4 памяти меток считывается метка "Конец списка" и запоминается триггером 6 меток (оператор А 8,фиг,4).Таким образом, в узле-предке список узлов с данной относительной величиной веса разрывается. По адресу узла-предка в узел 17 памяти списков записывается адрес Фиктивного узла из ячейки памяти текущего адреса узла 7 оперативной памяти, в узлен 55 4 памяти метки гасится метка Конец списка" (оператор А 9, фиг.4). Затем адрес Фиктивного узла записывается в Рею тр 3 адреса. Если метка "Конец списка" присутствует (условие В 8 выполнено,фиг,4, проверка выполняется аналогично условию В 2), тогда выполняетсяпоследовательность операций, задаваемых операторами А 10 (фиг.4), в противном случае - в соответствий с оператором А 11, описанным выше при подготовке к временному моделированиювесов начальных узлов, не равных нулю,Далее проверяется состояние триггера 23 конца ввода (условие В 7,фиг.4) по сигналу с его прямого вы.ходаНулевое состояние означает, йчто не во всех узлах графа-решеткипроверено наличие метки "Начальныйузел" и по этому условию блок 2 возвращается к определению следующихадресов узлов графа-решетки и поиску среди них начальных (согласнооператору А 2, фиг.4) .Последовательность действий, задаваемых операторами А 4-А 11 и условиями В 5-В 8, является общей как приподготовке к временному моделированию начальных узлов, так и другихузлов графа-решетки на этапе топологического моделирования. После просмотра всех узлов графа(решетки и подготовки к временному моделированию начального или множества начальных узлов (выполнение услопия В 4 алгоритма, Фнг,4), блок 2 переходит к временному моделированию весов узлов.Осуществляется чтение ячейки памяти величины п, младших разрядов кратчайшего пути узла 7 оперативной памяти, передача полученной информации на второй информационный вход АДУ 9 через управляемый формирователь 8 инверсного кода, увеличение этой величины на единицу, а затем передача полученного результата через выходной регистр 10, ячейку памяти п 1 младших разрядов величины кратчайшего пути, управляемый формирователь 8 инверсного кода и шинный,формирователь в регистр 3 адреса (операторА 12, Фиг.4) . По величине п младших разрядов кратчайшего пути, являющейся относительной величиной веса, иэ узла 4 памяти меток считывается и запоминается триггером 6 меток метка "Исходящий адрес", а иэ узла 16 памяти идентификаторов в ре