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

 

О П И С А Н И Е 296I28

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства ¹

МПК G 06g 7/48

Заявлено 20. т/1.1969 (¹ 1339244/18-24) с присоединением заявки №

Приоритет

Опубликовано 12.11.1971, Бюллетень № 8

Дата опубликования описания 2Л 1.1971

Комитет по делам изобретений и открытий при Совете Министров

СССР

УДК 681.333(088,8) Авторы изобретения

А. Д. Школьников и А. Н. Лившиц

Ленинградский горный институт им. Г. В. Плеханова

Заявитель

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОБ ОПТИМАЛЬНЫХ

ПУТЯХ НА СЕТЯХ

15 где

25

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

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

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

Это позволяет расширить функциональные возможности устройства и повысить оперативность решения.

На фиг. 1 представлена блок-схема устройства; на фиг. 2 — фрагмент сети.

Устройство содержит куб памяти 1, адресную матрицу 2, матрицу узлов 3, функциональный.блок 4, блок 5 выбора, блок б временного запоминания, блок 7 ввода и управления и блок 8 индикации.

Рассмотрим работу устройства на примере фрагмента сети (см. фиг, 2), 5 где а, b, с, d, е — узлы сети, ab, ас, bd, cb — ребра.

Стоимость ребра сети G= (N, А) есть функция V(t), определяемая выражением

8,1, при t=t, тр, Ч, (t), при Р. (t ((,"

0, при t= tP>, N — конечное множество узлов, А — конечное множество ребер, ребро ц из А — вектор, соединяющий любую пару узлов i, 1 из Ж, Ч (t) — функция, отображающая множество А в множество неотрицательных чисел и монотонно убывающая при монотонном возрастании аргумента о для каждого ребра от (т/ до

2S6128

1 — аргумент, монотонно возрастающий на интервале (0, T j и принимающий значение t 1 и t",. соответственно в начале и в конце каждого ребра ij, Т вЂ” значение аргумента при достижении конечного узла на сети, S, — величина стоимости всего ребра ij.

Топология сети реализуется на блоке 7.

При этом соединяются произвольно выбранные ячейки в матрице узлов 8 и в адресной матрице 2. Для определенности индексы ячеек в памяти 1, матрице 2 и в матрице узлов 8 совпадают с индексикацией на фиг. 2.

Ячейка ab и в матрице 2 через блок 7 соединяется с ячейками а и b в матрице узлов 3.

При этом в ячейку ЛВ куба памяти 1, имеющую адресный признак, определяемый ячейкой ab, из матрицы 2 записывается код стоимости ребра ab, вводимый через блок 7.

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

Устройство работает следующим образом.

Пусковой импульс поступает в ячейку а матрицы узлов 8, после чего ячейка а разрешает вызов ячеек ab и ас матрицы 2, которые выдают импульс считывания ячеек АВ и АС куба памяти 1. При вызове любой ячейки матрицы 2 в блок 5 поступает импульс, по которому в блоке 4 выбираются свободные ячейки а и р и в них записываются коды АВ и

АС. После выбора ячейки в блоке 4 устанавливается временная связь через блок б между ячейкой ab матрицы 2 и ячейкой а блока 4, а также ячейкой ас матрицы 2 и ячейкой блока 4.

Итак, в выбранных ячейках а и Р оказываются записанными значения функций стоимостей V g(t) и Ч „(г), соответственно равные S,ь и S „ïðè этом значение аргумента 1 функции равняется to и /О, причем го

И пока аргумент t возрастает от 1 „до 1 " в блоке б сохраняется связь между адресной ячейкой ab матрицы 2 и ячейкой а блока 4, в которую был записан код стоимости ребра ab.

Аналогичным образом сохраняется связь между ячейкой Р блока 4 и ячейкой ас матрицы 2 до тех пор, пока аргумент t возрастает

or t,o,,po t,", . При значении аргумента t=t, ", по определению Ч,g(t) =О и через связь блока б в ячейку ab матрицы 2 из ячейки а блока 4 поступает импульс. Одновременно связь я — ab разрушается. Затем следует импульс из ячейки ab матрицы 2 в ячейку Ь матрицы узлов 8.

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

В случае, когда имеется критический путь, т. е. до прихода импульса из ячейки ab в ячейку b ранее пришел импульс из ячейки eb, то ячейка b матрицы узла 8 разрешает считывание ячейки bd матрицы 2 и через него— ячейки BD куба памяти 1. В противном слу(ае, ячейка b матрицы узлов 8 срабатывает после импульса из ячейки eb. Блок 8 долже ° выдавать индикацию решения задачи. Поэтому одновременно с разрешением считывания ячейки od матрицы 2 из ячейки bуз,ла 3 поступает импульс через ячейку ab матрицы 2 в ячейку блока 8, соответствующую ребру ab по топологии сети, в результате чего ребро ab отмечается индикацией.

Аналогично проходятся все остальные ребра сети до конечного узла и те ребра из всего множества отмеченных, которые образуют непрерывную последовательность из начального

35 узла в конечный, являются оптимальными.

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

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

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

50 управления с матрицей узлов для вызова кодов стоимостей по временному признаку, а по другому каналу — с блоком временного запоминания, который своим первым входом соединен с функциональным блоком, а вторым

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

296128 Риг 1 иг 2

Составитель А. В. Вейц

Техред 3. Н. Тараненко

Корректор Г. С. Мухина

Редактор Е. В. Семанова

Типография, пр. Сапунова, 2

Заказ 13!7/4 Изд. № 580 Тираж 473 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий прп Совете Министров СССР

Москва, ®-35, Раушская наб., д. 4!5