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

 

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

Социалистимескик

Рвс ублин

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ оо813441 (61) Дополнительное к авт. свмд-ву (22) Заявлено 260279 (21) 2729175/18-24 с присоединением заявим ¹ (51))ф. Кл.2

G Об Р )5/20

Государственный комитет

СССР но делам изобретений и открытий (23) Приоритет—

Опубликовано 15.0381. Бюллетень ¹ 10

Дата опубликования описания 15.0 381 (53) УДК б81.З25 (088. 8) (72) Авторы изобретения

В.Б.Реут и В.С. Калашников с k ь, .;, ",: -"" „::=, i (71) Заявитель (54 ) УСТРОЙСТВО ЧЛЯ PErtlEHHH ЗАЦАЧИ

ВЫБОРА ОПТИМАЛЬНОГО ПУТИ

30

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

Известно решение подобных задач на универсальных цифровых вычислительных машинах. Решение их основано на использовании алгоритма Форда-!

О

Фалкерсона или одного из алгоритмов решения задачи транспортного типа.

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

Известно устройство, содержащее генератор, регистры и счетчики (1) .

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

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

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

Решение задачи определения максимального потока в матричной сети с бинарными ограничениями на пропускные способности в настоящее время произвоцится íà 3BN, что сложно и требует значительных затрат времени ЭВИ.

Цел ь и зоб ре те ни я — повыше ни е быс троде йс тв и я ус трой с тв а .

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

65 гистров разрешения соединен с первым входом первого блока умножения, второй выход блока регистров разрешения соединен с первым входом второго блока умножения, второй вход первого блока умножения соединен с первым выходом регистра состояний, а первый выход первого блока умножения соединен с первым входом блока регистров назначения, первый выход блока регистров назначения является выходом устройства, второй выход блока регистров назначения соединен с первым входом сумматора, выход которого соединен со входом регистра состояний и пепвым входом .генератора, второй выход регистра состояний соединен со вторым входом сумматора, третий выход блока регистров назначения соединен со вторым входом второго блока умножения, а выход генератора соедин ен с входом второ го счетчика, выход первого счетчика соединен с первым входом первой схемы сравнения, первый выход второго счетчика соединен со вторым входом первой схемы сравнения, первыми входами второй и третьей схем сравнения, второй выход второго счетчика соединен с первыми входами четвертой схемы сравнения и регистра управления, первый выход регистра управления соединен со вторым входом четвертой схемы сравнения, первый выход четвертой .схема сравнения соединен со вторыми входами блока регистров разрешения и блойа регистров назначения, второй вЫход четвертой схемы сравнения соединен со вторым входом генератора, второй вход регистра управления соединен с первым выходом третьего счетчика и с третьим входом блока регистров назначения, третий вход регистра управления соединен с первым выходом четвертого счетчика и с первыми входами регистра распределения, первого и второго регистров признаков, четвертый вход регистра управления соеди- . нен с первым выходом первого элемента И и первым входом третьего счетчика, второй выход регистра управления соединен со вторым входом регистра распределений, второй вход третьего счетчика соединен с выходом элемента ИЛИ, второй выход третьего счетчика соединен со вторым входом ° второй схемы сравнения, третьим входом регистра распрЕделений и вторыми входами первого и второго регистров признаков, первый выход второй схемы сравнения соединен с первым входом четвертого счетчика, второй выход схемы сравнения соединен с третьими входами первого и второго регистров признаков, первый выход третьей схем сравнения соединен с четвертыми входами первого и второго регистров признаков, второй

5 !

О

60 выход третьей схемы сравнения соединен с третьим входом генератора, четвертым входом регистра распределения и пятым входом первого регистра признаков, второй вход третьей схем сравнения соединен со вторым выходом четвертого счетчика, второй вход четвертого счетчика соединен со вторым выходом первого элемента

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

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

Иа чертеже приведена блок-схема устройс тва.

;Устройство содержит блок 1 ввода, блок 2 регистров разрешения, счетчики 3-6, блок 7 регистров на-, эначени я, блок 8 индикации, сумматор 9, генератор 10, регистр 11 состояний, схемы 12-15 сравнения, регистр 16 управления, блоки 17 и

18 умножения, регистр 19 распределений, регистры 20 и 21 признаков, элементы И,22 и 23 и элемент ИЛИ 24.

Для пояснения работы устройства текущее значение счетчика 3 обозначим К, текущее значение счетчика 4813441 текущее значение регистра 16 текущее значение счетчика 5 текущее значение счетчика б

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

Перед началом работы сигналом с синхронизатора ACY устройство приводится в исходное состояние, а именно, в регистре ll все единицы, счетчик 3 — в младшем разряде единица, остальные нули, все остальные счетчики и регистры в нуле, Затем через блок 1 заносим последовательно информацию.во все регистры блока 2.

Количество используемых регистров блока 2 фиксируется счетчиком 3.

После окончания заполнения блока 2 35 по команде Пуск включается генератор 10, Сигнал с генератора 10 добавляет единицу в счетчик 4, и производится сравнение содержимого счетчика 3 с содержимим счетчика 4 2О на схеме 12. В случае сравнения работа устройства прекращается, При несравнении устройство продолжает работу, т. е. происходит копирование состояния счетчика 4 на регистр 16, затем производится копирование со.1 держимого i регистра блока 2 и регистра 11 на блок 1/, в котором происходит логическое умножение содержимого регистров и .проверка результата на равенство нулю.В случае неравенства результата умножения нулю происходит пересылка результата в i - регистр блока 7. Произво. 1 дится индикация i регистра блока

7 в блоке 8 и копирование в сумматор 9 в котором происходит логическое сложение содержимого i" регистра блока 7 с содержимым регистра 11. Результат суммирования пересылается на регистр 11. Сигнал 40 разрешения поступает на генератор

l0 с которого выдается сигнал, и работа устройства повторяется как было описано выше.

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

5 на схему 13. В случае неравенства содержимого счетчиков 4 и 5 (1сЛ) производится проверка разряда регистра 20 и регистра 21 на равенство нулю. Если в Л разряде регистра 20 или регистра 21 будет записана единица, то к содержимому счетчика 5 будет добавлена единица. Если в Л разрядах регистров 20 и 21 будут равны нулю, то на блок 18 производится копирование содержимого i регист- y} ра блока 2 и Л регистра блока 7.

Производится логическое умножение содержимого регистров и проверка результата на равенство нулю. В случае, если результат равен нулю, к содержимому счетчика 5 добавляется елиница. Если результат не равен нулю, то производится проверка содержимого

Л разряда регистра 19 на равенство нулю. Если содержимое Л оазряда регистра 19 не равно нулю, тс к зна-. чению счетчика 5 добавляется единица.

Если содержимое Л разряда регистра

19 равно нулю, то заносим содержимое регистра 16 в Л разряд регистра 19, Затем в блок 17 копируем содержимое

Л регистра блока 2 и содержимое регистра 11. Производится логическое умножение и проверка результата на равенство нулю. Если результат равен нулю, к счетчику 5 прибавляется единица. Если результат- не равен нулю, .1 копируем содержимое i регистра блока 2 и содержимое Л регистра блока

7 на блок 18.Результат копируется в i регистр блока 7. Затем на блок

17 копируется содержимое регистра

11 и Л регистр блока 2, Результат умножения заносится в Л регистр блока /. Затем корректируем содержимое регистра 11 тем, что посылаем на сумматор 9 содержимое регистра 11 и содержимое i регистра блока 7.Ре° М зультат логического сложения заносим в регистр 11.

Если содержимое счетчика 5 будет равно содержимому счетчика 4, то сиг налом со схемы 13 установится в ноль счетчик б. Затем добавляется единица к содержимому счетчика 6 и производится сравнение содержимого счетчика б с содержимым счетчика 4 íà схеме 14. Если- содержимое счетчиков 4 и б совпадает,. т.е. i=j, то производится копирование j разряда регистра 20 в j разряд регистра 21. Затем производится установка в ноль регистров 19 и 20 ° Подается сигнал на генератор 10, прибавляется единица к содержимому счетчика 4, и устройство продолжает работу, как было описано выше.

Если содержимое счетчиков 4 и 6 не совпадает, то производится проверка содержимого j разряда регистра

19 на равенство нулЮ, регистров 20 и 21 на неравенство нулю. В случае невыполнения этих.:условий производится добавление единицы.к счетчику

6. При выполнении этих условий производится копирование содержимого счетчика 6 в регистр 16, з анесение в j разряд регистра 20 единицы, установление в ноль счетчика Ь, добавление единицы к счетчику .6 и т.д. по описанному выше алгоритму.

Устройство работает до момента сравнения содержимого счетчиков 3 и

4; После этого устройство прекращает работу и на блоке Ю отображается информация.

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

81 3441 признаков объекта изобретения позволили решить з адачу определения максимального потока в матричной сети с бинарными ограничениями на пропускные способности значительно эффективнее, чем при использовании известных алгоритмов решения задач транспортного типа и алгоритма Форда-Фолкерсона.

При этом сокращается число выполненных операций, что обеспечиваетувеличение скорости вычисления мак- !О симального потока в матрической сети и приводит к повышению производительности АСУ. Так, время решения задачи с матрицей 100х100 на ЭВМ .БЭСМ-6 составляет 3-5 минут. Время решения аналогичной з ад ачи н а предлагаемом устройстве составляет от 20 мксек до 1 мсек.

Фор ",ула изобретения

Устройство для решения задачи выбора оптимального пути, содержащее генератор, блок регистров назначения и счетчики, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок регистров разрешения, два блока умножения, сумматор, регистр состояний, регистр управления, регистр распре- 30 делений, два регистра признаков, четыре схем сравнения, элемент ИЛИ, два элемента И, причем первый вход блока регистров разрешения и вход первого счетчика являются .входами Я5 устройства, первый выход блока регистров разрешения соединен с первым входом первого блока умножения, второй выход блока регистров разрешения соединен с первым входом второго блока умножения, втотюй вход первого блока умножения соединен с первым выходом регистра состояний, а первый выход первого блока умножения соединен с первым входом блока регистров назначения, первый выход 45 блока регистров назначения является выходом устройства, второй выход блока регистров назначения соединен с первым входом сумматора, выход которого соединен со входом регистра 50 состояний и первым входом генератора, второй выход регистра состояний соединен со втопчем входом сумматора, третий выход блока регистров назначенЬя соединен со вторым входом вто- 55 рого блока умножения, а выход генератора соединен с входом второго счетчика, выход первого счетчика соединен с первым входом первой схемы сравнения, первый выход

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

51344 1

Составитель В. Калашников

Редактор A ° Наурсков Техред Л. Пекарь Корректор Е.Рошко

Закаэ 77 /6 3 Тираж 74 5 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д,4/5 филиал ППП Патент, г.ужгород, ул. Проектная, 4 ходом второго регистра признаков, етий выход первого регистра приз нав соединен с пятым входом вто го регистра признаков, второй вы д второго элемента И соединен с

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

Источники информации, принятые во внимание при экспертизе

1 .. Авторское свидетельство СССР

325279, кл. G 06 F 15/32, 1971.

2. Авторс коз свидетельство CCCP

М 281012, кл. G 06 F 15/30, 1969 (прототип).