Устройство для решения задачи об оптимальных

О П И С А Н И Е 296128ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик.т 1.1969 (Рй 1339244/18-24) аявл исоединением заявкиПриоритет Комитет по делам зобретений и открытий при Совете Министров СССРбликовано 12,1,1971, Бюллетеньа опубликования описания 2 Л 1.1971 УДК 681.333 088,8 Авторызоб ретения. Н,Лив енинградский горный институт им. Г. В. Плеханова Заявител ТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОБ ОПТИМАЛЬНЫХ ПУТЯХ НА СЕТЯХменного запоминания, блок 7 вления и блок 8 индикации.Рассмотрим работу устройствфрагмента сети (см. фиг, 2),5где а, Ь, с, д, е - узлы сети,аЬ, ас, Ьд, сЬ - ребра.Стоимость ребра сфункция Чт(1), определ10 Я а и упра а примере ети 6= М, А 1 естяемая выражением,1 ф, пРи Р. ( при 1 Чту --де тножество уз ство ре мн ребро ц из соединяющииару узлов Ч(1 ражающая в множецательн тонно убыгонотонном ргумента то еотри моно при х ии а На фиг. 1 иства; на фиг, Устройство ную матрицунальный.блок ема устрои редставлена блок 2 - фрагмент сет содержит куб пам 2, матрицу узлов 4, блок 5 выбор яти 1, адрес, функциоблок б вре для каждого редо Предложение относится к области вычислительной техники и предназначено для решения задачи об оптимальных путях на сетях.Известны устройства для решения сетевых графиков и для поиска электромальных путей на сетях, содержащие модели узлов и ветвей, соединенные согласно топологии сети.Предложенное устройство отличается тем, что куб памяти своим первым входом соединен с адресной матрицей, которая по одному каналу связана через блок ввода и управления с матрицей узлов для вызова кодов стоимостей по временному признаку, а по другому каналу - с блоком временного запоминания, который своим первым входом соединен с функциональным блоком, а вторым входом - с блоком выбора, также связанным с функциональным блоком, вход которого соединен с адресной матрицей, связанной своим выходом с блоком индикации, а блок индикации соединен по входу с матрицей узлов.Это позволяет расширить функциональные возможности устройства и повысить оперативность решения.- конечноелов,- конечноебер,- вектор,любуюиз Ж,- функция,множествствочисел ивающаявозраста1 - аргумент, монотонно возрастающий на интервале О, Т) и принимающий значение 11 и 1", соответственно в начале и в конце каждого ребра Ц, Т - значение аргумента при достижении конечного узла на сети,5 - величина стоимости всего ребра ц.Топология сети реализуется на блоке 7, При этом соединяются произвольно выбранные ячейки в матрице узлов 3 и в адресной матрице 2. Для определенности индексы ячеек в памяти 1, матрице 2 и в матрице узлов 3 совпадают с индексикацией на фиг. 2.Ячейка аЬ и в матрице 2 через блок 7 соединяется с ячейками а и Ь в матрице узлов 3. При этом в ячейку АВ куба памяти 1, имеющую адресный признак, определяемый ячейкой аЬ, из матрицы 2 записывается код стоимости ребра аЬ, вводимый через блок 7.Аналогично вводятся в устройство все остальные ребра, сети и их метрические характеристики, После этого в памяти 1 записаны коды стоимостей всех ребер сети, и каждая кодовая числовая ячейка куба памяти 1 имеет соответствующие связи по адресному признаку с матрицей 2, а ячейки матрицы 2 связаны с ячейками матрицы узлов 3 по временному признаку.Устройство работает следующим образом.Пусковой импульс поступает в ячейку а матрицы узлов 3, после чего ячейка а разрешает вызов ячеек аЬ и ас матрицы 2, которые выдают импульс считывания ячеек АВ и АС куба памяти 1. При вызове любой ячейки ц 1 матрицы 2 в блок б поступает импульс, по которому в блоке 4 выбираются свободные ячейки а и Р и в них записываются коды АВ и АС. После выбора ячейки в блоке 4 устанавливается временная связь через блок б между ячейкой аЬ матрицы 2 и ячейкой а блока 4, а также ячейкой ае матрицы 2 и ячейкой блока 4,Итак, в выбранных ячейках а и Р оказываются записанными значения функций стоимостей Чь(1) и Ч,(1), соответственно равные 5 и и 5, при этом значение аргумента 1 функции равняется агав и пгпричем ав 1 асИ пока аргумент 1 возрастает от 1 до 1" в блоке б сохраняется связь между адресной ячейкой аЬ матрицы 2 и ячейкой а блока 4, в которую был записан код стоимости ребра аЬ.Аналогичным образом сохраняется связь между ячейкой р блока 4 и ячейкой ае матрицы 2 до тех пор, пока аргумент 1 возрастает от 1, до 1", . При значении аргумента 1=1", по определению Чь(1) =О и через связь блока б в ячейку аЬ матрицы 2 из ячейки а блока 4 поступает импульс. Одновременно связь сс - аЬ разрушается. Затем следует импульс из ячейки аЬ матрицы 2 в ячейку Ь матрицы узлов 3.10 В зависимости от условия задачи, каждыйузелразрешает движение дальше по сети, либо по прохождению первого входящего ребра, либо по прохождению части входящих в него ребер, либо по прохождению всех входя щих в этот узел ребер.В случае, когда имеется критический путь,т. е. до прихода импульса из ячейки аЬ в ячейку Ь ранее пришел импульс из ячейки еЬ, то ячейка Ь матрицы узла 3 разрешает считывание ячейки Ы матрицы 2 и через него - ячейки Вй куба памяти 1. В противном случае, ячейка Ь матрицы узлов 3 срабатывает после импульса из ячейки еЬ. Блок 8 должевыдавать индикацию решения задачи. Поэтому одновременно с разрешением считывания ячейки вд матрицы 2 из ячейки Ь узла 3 поступает импульс через ячейку аЬ матрицы 2 в ячейку блока 8, соответствующую ребру аЬ по топологии сети, в результате чего ребро аЬ отмечается индикацией,Аналогично проходятся все остальные ребра сети до конечного узла и те ребра из всего множества отмеченных, которые образуют непрерывную последовательность из начального 35 узла в конечный, являются оптимальными. Предмет изобретенияУстройство для решения задачи об опти мальных путях на сетях, содержащее куб памяти, адресную матрицу, матрицу узлов, функциональный блок, блок выбора, блок временного запоминания, блоки ввода, управления и индикации, отличающееся тем, что, с 45 целью расширения функциональных возможностей устройства и повышения оперативности решения, куб памяти своим первым входом соединен с адресной матрицей, которая по одному каналу связана через блок ввода и 50 управления с матрицей узлов для вызова кодов стоимостей по временному признаку, а по другому каналу - с блоком временного запоминания, который своим первым входом соединен с функциональным блоком, а вторым 55 входом - с блоком выбора, также связаннымс функциональным блоком, вход которого соединен с адресной матрицей, связанной своим выходом с блоком индикации, а блок индикации соединен по входу с матрицей узлов.296128 фиг У иг 2 Составитель А. В, Вейц Техред 3. Н. Тараненко Корректор Г, С. Мухина Редактор Е. В. Семанова Типография, пр. Сапунова, 2 Заказ 137/4 Изд. Ха 580 Тираж 473 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий прп Совете Министров СССР Москва, Ж, Раушская наб., д. 45