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

Союз Советскик Социалистимескик Рвспублин(22) Заявлено 2 б.02,79 (21) 2729175/18-24 (51) М. КЛ,с присоединением эаявкн Йо 6 Об Р 15/20 Государственный комитет СССР но делам изобретений и открытий(54) УСТРОЙСТВО ЧЛЯ РЕМЕНИЯ ЗАЦАЧИ ВЫБОРА ОПТИМАЛЬНОГО ПУТИ 25 30 Изобретение относится к вычисли - тельной технике и может быть использовано для определения максимального потока в матричной сети с бинарными ограничениями на пропускные способности.Известно решение подобных задач на универсальных цифровых вычислительных машинах. Решение их основано на использовании алгоритма ФордаО фалкерсона или одного из алгоритмов решения задачи транспортного типа. Однако использовачие универсальных цифровых вычислительных машин 1не всегда возможно из-за их высокойстоимости. Кроме того, решение подобных задач на универсальных ЦВМ требует значительного времени, что непозволяет использовать их в системах, работающих в реальном масштабе времени.Известно устройство, содержащеегенератор, регистры и счетчики (1 .Недостатками данного устройстваявляются его низкие функциональныевозможности и недостаточное быстродействие.Наиболее близким по техническомурешению является устройство, содержащее генератор, блок регистров назначения и счетчики (2) .Однако данное устройство не позволяет решить задачу определения максимального потока в сети с бинарными ограничениями на пропускные способности и имеет низкое быстродействие.Решение задачи определения максимального потока в матричной сетис бинарными ограничениями на пропускные способности в настоящее время произвоцится на ЭВМ, что сложно итребует значительных затрат времени ЭВИ.Цель изобретения - повышение быстродействия устройства.Поставленная цель достигается тем, что в устройство, содержащее генератор, блок регистров назначения и счетчики, введены блок регистров разрешения, два блока умножения, сумматор, регистр состояний, регистр управления, регистр распределений, два регистра признаков, четыре скейт сравнения, элемент ИЛИ, два элемента И, причем первый входблока регистров разрешения и вход первого счетчика являются входами устройства, первый выход блока ре 81344165 гистров разрешения соединен с первым входом первого блока умножения,второй выход блока регистров разрешения соединен с первым входомвторого блока умножения, второй входпервого блока умножения соединен спервым выходом регистра состояний,а первый выход первого блока умножения соединен с первым входом блокарегистров назначения, первый выходблока регистров назначения являетсявыходом устройства, второй выход блока регистров назначения соединен спервым входом сумматора, выход которого соединен со входом регистрасостояний и первым входом .генератора, второй выход регистра состоянийсоединен со вторым входом сумматора,третий выход блока регистров назначения соединен со вторым входом второго блока умножения, а выход генератора соединен с входом второгосчетчика, выход первого счетчика сбединен с первым входом первой схемысравнения, первый выход второго счетчика соединен со вторым входом первой схемы сравнения, первыми входами второй и третьей схемы сравнения,второй выход второго счетчика соединен с первыми входами четвертойсхемы сравнения и регистра управления, первый выход регистра управления соединен со вторым входом четвертой схемы сравнения, первый выходчетвертой .схема сравнения соединенсо вторыми входами блока регистровразрешения и блока регистров назначения, второй вЫход четвертой схемысравнения соединен со вторым входомгенератора, второй вход регистра управления соединен с первым выходомтретьего счетчика и с третьим входом блока регистров назначения,третий вход регистра управлениясоединен с первым выходом четвертого счетчика и с первыми входами регистра распределения, первого ивторого регистров признаков, четвертый вход регистра управления соеди- .нен с первым выКодом первого элемента И и первым входом третьего счетчика, второй выход регистра управления соединен со вторым входом регистра распределений, второй входтретьего счетчика соединен с выходом элемента ИЛИ, второй выход третьего счетчика соединен со вторымвходомвторой схемы сравнения, третьим входом регистра распрЕделенийи вторыми входами первого и второгорегистров признаков, первый выходвторой схемы сравнения соединен спервым входом четвертого счетчика,второй выход схемы сравнения соединен с третьими входами первого ивторого регистров признаков, первыйвыход третьей схем сравнения соединен с четвертыми входами первого ивтброго регистров признаков, второй 5 10 15 20 25 30 40 45 50 55 60 выход третьей схемы сравнения соединен с третьим входом генератора,четвертым входом регистра распределения и пятым входом первого регистра признаков, второй вход третьейсхем сравнения соединен со вторымвыходом четвертого счетчика, второйвход четвертого счетчика соединенсо вторым выходом первого элементаИ, первый вход первбго элемента Исоединен со вторым выходом первогоблока умножения, второй вход первого элемента И соединен с первым выходом регистра распределений, третий вход первого элемента И соединен с первым выходом первого регистра приэнакбв, четвертый вход первого элемента И соединен с первым выходом второго регистра признаков, второй выход регистра распределений соединеН с первым входом элемента ИЛИ, второй вход элемента ИЛИ соединен с первым выходом второгоблока умножения, третий вход элемента ИЛИ соединен с первым выходомвторого элемента И, первый входвтОрого элемента И соединен со вторым выходом первого регистра признаков, второй вход второго элемента И соединен со вторым выходом второго регистра признаков, третий выход первого регистра признаков соединен с пятым входом второго регистра признаков, второй выход второго элемента И соединен с третьим входом второго блока умножения,второй выход второго блока умножения соединен с пятым входом регистра распределений, кроме того, третий выход второго блока умножения соединен с четвертым входом блока регистров назначения.В отличие от алгоритма ФордаФолкерсона,.устанавливающего цепоч.- ку связей между строкой и столбцом, столбцом и строкой и т.дпредлагаеьий алгоритм устанавливает связи между строками, что обеспечивает важное преимущество с вычислительной точки зрения, позволяя существенно упростить схему управления,и открывает возможность распараллеливания вычислительного процесса за счет использования разрядной сетки.На чертеже приведена блок-схема устройс тва.;Устройство содержит блок 1 ввода, блок 2 регистров разрешения, счетчики 3-6, блок 7 регистров на-, значения, блок 8 индикации, сумматор 9, генератор 10, регистр 11 состояний, схемы 12-15 сравнения, регистр 16 управления, блоки 17 и 18 умножения, регистр 19 распределений, регистры 20 и 21 признаков, элементы И,22 и 23 и элемент ИЛИ 24.Для пояснения работы устройства текущее значение счетчика 3 обозначим К, текущее значение счетчика 41, текущее значение регистра 16 - 1 ф, текущее значение счетчика 5 текущее значение счетчика бУстройство работает следующим образом.Перед началом работы сигналом с синхронизатора АСУ устройство приводится в исходное состояние, а именно, в регистре 11 все единицы, счетчик 3 - в младшем разряде единица, остальные нули, все остальные счетчики и регистры в нуле, Затем ф через блок 1 заносим последовательно информацию во все регистры блока 2. Количество используемых оегистрсв блока 2 фиксируется счетчиком 3. После окончания заполнения блока 2 35 по команде Пуск включается генератор 10, Сигнал с генератора 10 добавляет единицу в счетчик 4, и производится сравнение содержимого счетчика 3 с содержимим счетчика 4 2 О на схеме 12. В случае сравнения работа устройства прекращается, При несравнении устройство продолжает работу, т.е. происходит копирование состояния счетчика 4 на регистр 16, затем производится копирование содержимого 1 регистра блока 2 и регистра 11 на блок 17, в котором происходит логическое умножение содержимого регистров и .проверка результата на равенство нулю,В случае неравенства результата умножения нулю происходит пересылка результатав 1 регистр блока 7. Производится индикация 1 регистра блока 7 в блоке 8 и копирование в сумма- Зэ тор 9, в котором происходит логическое сложение содержимого 1" регистра блока 7 с содержимым регистра 11, Результат суммирования пересылается на регистр 11, Сигнал 40 разрешения поступает на генератор 10, с которого выдается сигнал, и работа устройства повторяется как было описано выше.В случае равенства нулю результата логического умножения блока 17 происходит установка в ноль счетчика 3, прибавление к содержимому счетчика 3 единицы и копирование содержимого счетчика 4 и счетчика 5 на схему 13. В случае неравенства содержимого счетчиков 4 и 5 (1 фЛ) производится проверка разряда регистра 20 и регистра 21 на равенство нулю. Если в Л разряде регистра 20 или регистра 21 будет записана еди- И ница, то к содержимому счетчика 5 будет добавлена единица. Если в Л разрядах регистров 20 и 21 будут равны нулю, то на блок 18 производится копирование содержимого 1 регист- щ ра блока 2 и Л регистра блока 7, Производится логическое умножение содержимого регистров и проверка результата на равенство нулю, В случае, если результат равен нулю, к содер- д жимсму счетчика 5 добавляется елиница. Если результат не равен нулю,то производится проверка содержимогоХ разряда регистра 19 на равенствонулю. Если содержимое Л оазряда регистра 19 не равно нулю, тс к значению счетчика 5 добавляется единица.Если содержимое Х разряда регистра19 равно нулю, то заносим содержимоерегистра 16 в Л разряд регистра 19.Затем в блок 17 копируем содержимоеЛ регистра блока 2 и содержимое регистра 11. Производится логическоеумножение и проверка результата наравенство нулю. Если результат равеннулю, к счетчику 5 прибавляется единица. Если результат-не равен нулю,,1копируем содержимое 1 регистра блока 2 и содержимое Л регистра блока7 на блок 18.Результат копируетсяв 1 регистр блока 7. Затем на блок17 копируется содержимое регистра11 и Х регистр блока 2, Результатумножения заносится в Х регистр блока /. Затем корректируем содержимоерегистра 11 тем, что посылаем насумматор 9 содержимое регистра 11 исодержимое 1 регистра блока 7.Результат логического сложения заносимв регистр 11.Если содержимое счетчика 5 будетравно содержимому счетчика 4, то сигналом со схемы 13 установится в нольсчетчик б. Затем добавляется единицак содержимому счетчика 6 и производится сравнение содержимого счетчика б с содержимым счетчика 4 на схеме 14. Если. содержимое счетчиков 4и б совпадает,. т.е. 1=3, то производится копирование 3 разряда регистра 20 в 3 разряд регистра 21. Затемпроизводится устайовка в ноль регистров 19 и 20Подается сигнал на генератор 10, прибавляется единица ксодержимому счетчика 4, иустройство продолжает работу, как было описано выше.Если содерйимое счетчиков 4 и 6не совпадает, то производится проверка содержимого 3 разряда регистра19 на равенство нулЮ, регистров 20и 21 на неравенство нулю. В случаеневыполнения этих,условий производится добавление единицы .к счетчику6. При выполнении этих условий производится копирование содержимогосчетчика 6 в регистр 16, занесениев 3 разряд регистра 20 единицы, установление в ноль счетчика Ь, добавление единицы к счетчику,б и т.д. поописанному выше алгоритму.Устройство работает до моментасравнения содержимого счетчиков 3 и4; После этого устройство прекращает работу и на блоке Ю отображаетсяинформация,Результаты теоретического расчета и математического моделированияпоказали, что введение отличительныхпризнаков объекта изобретения позволили решить задачу определения максимального потока в матричной сети с бинарными ограничениями на пропускные способности значительно эффективнее, чем при использовании известных алгоритмов решения задач транс портного типа и алгоритма Форда-Фолкерсона.При этом сокращается число выполненных операций, что обеспечивает увеличение скорости вычисления мак- О симального потока в матрической сети и приводит к повышению производительности АСУ. Так, время решения эапачи с матрицей 100 х 100 на ЭВМ .БЭСМсоставляет 3-5 минут. Время решения аналогичной задачи на предлагаемом устройстве составляет от 20 мксек до 1 мсек.20Фор ",ула изобретенияУстройство для решения задачи выбора оптимального пути, содержащеегенератор, блок регистров назначенияи счетчики, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, в него введены блок регистров разрешения, два блока умножения, сумматор, регистр состояний,регистр управления, регистр распределений, два регистра признаков,четыре схем сравнения, элемент ИЛИ,два элемента И, причем первый входблока регистров разрешения и входпервого счетчика являются .входами 35устройства, первый выход блока регистров разрешения соединен с первым входом первого блока умножения,второй выход блока регистров разрешения соединен с первым входом второго блока умножения, втопой входпервого блока умножения соединен спервым выходом регистра состояний,а первый выход первого блока умножения соединен с первым входом блока регистров назначения, первый выход 4блока регистров назначения являетсявыходом устройства, второй выходблока регистров назначения соединенс первым входом сумматора, выход которого соединен со входом регистрасостояний и первым входом генератора,второй выход регистра состоянийсоединен со вторым входом сумматора,третий выход блока регистров назначенЬя соединен со вторым входом вто- Ярого блока умножения, а выход генератора соединен с входом второгосчетчика, выход первого счетчикасоединен с первым входом первойсхемы сравнения, первый выход60второго счетчика соединен совторым входом первой схемы сравнения, первыми входами второй итретьей схемы сравнения, второйвыход второго счетчика соединен с первыми входами четвертой схемы сравнения и регистра управления, первый вчход регистра управления соединен со вторым входом четвертой схем сравнения, первый выход четвертой схем сравнения соединен со вторыми входами блока регистров разрешения и блока регистров назначения, второй выход четвертой схемы сравнения соединен со вторым входом генератора, второй вход регистра управления соединен с первым выходомтретьего счетчика и с третьим входом блока регистров назначения, третий вход регистра управления соединен с первым выходом четвертого счетчика и с первыми входами регистра распределения, первого и второго регистров признаков, четвертый вход регистра управления соединен с первым выходом первого элемента И и с первым входом третьего счетчика, второй выход регистра управления соединен со вторым входом регистра распределений, второй вход третьего счетчика соединен с выходом элемента ИЛИ, второй выход третьего счетчика соединен со вторым входом второй схемы сравнения, третьим входом регистра распределений и вторыми входами первого и второго регистров признаков, первый выход второй схемы сравнения соединен с первым входом.четвертого счетчика, второй выход второй схемы сравнения соединен с третьими входами первого и второго регистров признаков, первый выход третьей схемы сравнения соединен с четвертыми входами первого и второго регистров признаков, второй выход третьей схемы сравнения соединен с третьим входом генератора, четвертым входом регистра распределения и пятым входом первого регистра приэнаков, второй вход третьей схемы сравнения соединен со вторым выходом четвертого счетчика, второй вход четвертого счетчика соединен со вторым выходом первого элемента И, первый вход первого элемента И соединен со вторым выходом первого блока умножения, второй вход первого элемента И соединен с первым выходом регистра распределений, третнй вход первого элемента И соединен с первым выходом первого регистра признаков, четвертый вход первого элемента И соединен с первым выходом второго регистра признаков, второй выход регистра распределений соединен с первым входом элемента ИЛИ, второй вход элемента ИЛИ соединен с первым выходом второго блока умножения, третий вход элемента ИЛИ соединен с первым выходом второго элемента И, первый вход второго элемента И соединен со втЬрым выходом первого регистра признаков, второй вход второго элс:.нта И соединен со втотМ61344 1 10 Составитель В.КалашниковРедактор А.Наурсков ТехредЛ.Пекарь Корректор Е.Рошко Закаэ 775/6 3 Ти Раж 74 5 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д.4/5ВФилиал ППП 11 атентф, г.ужгород, ул.Проектная, 4 ходом второго регистра признаков, етий выход первого регистра призков соединен с пятым входом втого регистра признаков, второй выд второго элемента И соединен с етьим входом второго блока умнозния, второй выход второго блока чножения соединен с пятым входом згистра распределений, кроме того, эетий выход второго блока умножения соединен с четвертым нхоЛом блока регистров назначения. Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРВ 325279, кл. С 06 Г 15/32, 1971.2. Авторское свидетельство СССРВ 281012, кл. С 06 Г 15/30, 1969прототип),