Информационная машина для поиска оптимального пути между начальным и конечным состоянием системы Советский патент 1979 года по МПК G06F15/173 G06F15/177 

ной ячейкой, записывают цифру «1. Затем во Всех ячейках, смежных с ячейками, в которых записана цифра- «1, записывают цифру «2, после этого во всех ячейках. смежных с ячейками с цифрой 2, записывают цифру 3, и т. д. В конце шагов получают конечную точку В. Самый короткий путь можно начертить, начиная от точки В и соединяя смежные ячейки, содержимое которых убывает на единицу с каждым шагом. Этот алгоритм дает, помимо оптимального пути, его длину. Но машина, работающая в соответствии с этим алгоритмом, должна обязательно иметь Л позиций памяти, если N представляет квантовые величины, которые могут принимать каждая из обеих переменных плоскости, что является чрезмерным в большинстве практических случаев использования, когда число yV может достигать, например, нескольких тысяч. Кроме того, эти позиции должны быть рассчитаны на запоминание числа, по крайней мере равного длине оптимального пути, который в некоторых случаях может приближаться к величине 2 N, что еще более не допустимо. . Для избежания этого недостатка был предложен алгоритм, в котором числа, записанные в ячейках, образуют такую последовательность, что число, которое предшествует си-мволу этой последовательности, отлично от последующего числа. Таким образом, элементы памяти могут быть рассчитаны на запись ортаниченного числа разрядов, например 2, тем не менее в этом случае машина, использующая этот алгоритм, содержит N позиций памяти. Известен также итеративный алгоритм, в соответствии с которым поступают еледующим образом. Сначала записывают во все ячейки плоскости «О, а «1 записывается в ячейку А, соответствующую исходной точке. Цифры «1 записываются затем во все ячейки, которые содержат еще «О и являются смежными с ячейками, в которых уже записана «1. Запись «1 распространяется таким образом от шага к шагу, и после нескольких шагов достигают ячейки С, начиная с которой можно за один шаг достигнуть конечной ячейки В. Первое оптимальное элементарное действие, которое должна испытать система, является тогда тем, в результате которого система переходит от состояния точки В к состоянию точки С. После выполнения этого первого элементарного действия содержимые ячеек плоскости сводятся к нулю, и повторяется процесс исследования с помощью новой записи «1, при этом точку принимают за уровень конечной точки. После ряда шагов получают точку М, начиная с которой можно достигнуть точки С за один шаг. Второе элементарное оптимальное действие - это действие, заставляющее перейти систему из точки С в точку М. Процесс повторяется до достижения исходной точки Л. Информационная машина, действующая в соответствии с этим алгоритмом, требует еще № позиций памяти. Кроме того, время расчета может быть очень большим, если длина оптимального пути велика, даже в случае, когда число ограничений очень мало. Цель изобретения - повышение быстродействия машины и ее упрощение. Поставленная цель достигается тем, что предлагаемая информационная машина для поиска оптимального пути мелсду начальным и конечным состояниями системы содержит блок коммутаций, блок записи единичных и нулевых значений и блок последовательного адресования, вход и первый выход которого соединены соответственно с выходами и входами регистраторов переменных начального и конечного состояний, а второй, третий ичетвертый выходы подключены соответственно к адресным входам запоминающего устройства, сумматора и блока коммутаций, информационный вход которого соединен с выходом запоминающего устройства, а выход подключен к входу сумматора, выход сумматора подключен к входу блока записи единичных и нулевых значений, выход которого соединен с входом запоминающего устройства. Это дает возможность с одной стороны использовать лишь 2 N позиций памяти, что с учетом значений, которые число .V способно принимать в практических случаях, ведет к значительному упрощению оборудования. С другой стороны, не производится исследования плоскости шаговым методом, что потребовало бы чрезмерно больтого времени. Это исследование осуществляется от ограничения к ограничению, что значительно повышает быстроту расчета, Содержимое каждого из элементов памяти позволяет найти оптимальный путь без необходимости предусмотрения элементов памяти, максимальная емкость которых порядка величины оптимального пути. На фиг. 1 дана блок-схема машины; на фиг. 2 показано двумерное пространство для иллюстрации работы машины с двумя переменными; на фиг. 3 приведен пример конфигурации запоминающего устройства; на фиг. 4 изображен канал разрешения выходов позиций запоминающего устройства; на фиг. 5 показан пример реализации канала разрешения выходов позиций запоминающего устройства; на фиг. 6 схематически редставлены все 128 позиций линейки 34; на фиг. 7 изображена схема сумматора; на фиг. 8 - схема вычисления адреса; на фиг. 9 дан пример реализации схем управения. Машина содержит регистры 1 перемен,йых начального и конечного состояний, запоминающее устройство 2, сумматор 3, блок 4 коммутаций, блок 5 последовательного адресования, блок 6 записи единичных и нулевых значений (цифрой 7 обозначены средства установки исходного, нулевого, состояния запоминающего устройства), интегральные схемы 8, 9, 10, входы 11 и выходы 12 запоминающего устройства; канал 13 управления, канал 14 разрешения 1выходов (см. фиг. 4), дещифратор 15 нижнего адреса, дешифратор 16 верхнего адреса, дешифраторы 17-22, канал 23 разрешения, связь 24, позицию 25 запоминающего устройства, связь 26 (см. фиг. 5), логическую схему НЕ-ИЛИ 27, логическую схему 28 с входами 29-34, схемой НЕ-И 35, связью 36, схемами НЕ-И 37, 38 связью 39, сумматоры групп битов 40-43, общий сумматор 44, выход 45 сумматора, входы 46, 47, 48 сумматора, связь 49, буферную память 50, логическую схему И 51, связь 52, сумматор 53, связь 54, логическую схему И 55, счетчик 56 с тактовым входом 57, связь 58, вход 59 для подключения источника Питания, счетчик 60 (см. фиг. 9), логическую схему 61 направления, управляющую связь 62, выход 63 схемы 61, «омпаратор 64, схему 65 направления, выходы 66, 67 схемы 65, схему 68, вход 69, узел 70 управления.

Машина имеет запоминающее устройство (ЗУ), содержащее 2 ячеек. В упрощенном случае (см. фиг. 2) это число 2 Л равно 18. Таким образом, ЗУ содержит 18 ячеек. Каждой из 18 ячеек присвоен адрес, называемый диагональным адресом. Эти адреса пронумерованы от О до 17. Можно считать, что эти ячейки приписаны одной из 18 диагоналей плоскости, представляющей поставленную задачу.

Каждое напряжение выражается двумя числами, одно из которых, называемое «верхним диагональным адресом, обозначенным через Я, соответствует в представляющей ПЛОСКОСТИ точке напряжения, расположенной на самой верхней диагонали плоскости, а другое, называемое «нижним диагональным адресом, обозначенным через В, .соответствует точке на Пряжения, расположенной на самой нижней диагонали плоскости.

Например, первое напряжение имеет адреса и В 8. Содержимое ячейки с адресом X обозначено символически через (X)..

Функция этой полосы из 18 ячеек состоит в вычислении искривления, фронта волны при прохождении напряжения в 18 точках. Можно было бы создать машину, в которой ячейки вычисления и запоминания точно представляли бы сдвиг, выраженный в числе шагов фронта возмущен. ной волны относительно фронта невозмущенной волны. В этом случае первоначально в ячей1ках содержалось бы число, раёное О для ячеек с адресами от О до 11 включительно, и числа, равные соответственно 1, 2, 3... 6 для ячеек с адресами от 12 до 17. Эта совокупность чисел представляет сдвиг между фронтом первоначально прямоугольной волны и фронтом теоретической линейной волны, совпадающими с осью ОУ.

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

равна либо О, либо 1. Первоначально приращение ячеек равно О для ячеек с адресами от О до И включительно, и это приращение равно 1 для ячеек, адреса которых изменяются от 12 до 17.

Чтобы обработать напряжение, определенное своими верхним Я и нижним В адресами, машина выполняет следующие операции (ниже нижнего адреса приращения остаются неизменными): начиная с нижнего адреса в B-f 1, S+2,..., S+S записывают S раз по 1, где 5 равно (Я) - (В), т. е. числу считанных яеред обработкой рассмотренного напряжения приращений между адресами В и Я, причем В исключается, а Я включается (интервал, символически обозначенный через В, Я). Начиная с адреса B + S+l, приращения равны нулю вплоть до Я; вне Я приращения остаются неизменными. Операция обработки напряжений завершается измерением содержимого точки прихода, что достигается посредством суммирования всех «1, содержащихся до точки прихода. В таблице 1 поясняется работа оператора.

В первой колонке находятся диагональные адреса, пронумерованные от О до 17, во второй-первоначальные сдвиги, в третьей колонке представлены приращ ия, соответствующие сдвигам из второй колонки. Это. приращение равно О вплоть до адреса 11 и равно 1 в адресах 12-17. Таким образом, третья колонка представляет шервоначальное состояние ячеек в случае, когда

последние предназначены для обработки

приращений;. ,.., . -..,..

После обработки первого напряжения, определенного адресами В 8 и , з ячейках приращения оказываются равными О или 1 в зависимости от того, равно ли содержимое ячейки содержимому предшествующей ячейки или оно превышает его на единицу. После обработки первого напряжения новые приращения являются приращениями из четвертой колонки. Таблица В Пятой колонке проставлены приращения после второго напряжения. Между адресами В-12 и сосчитанное число «1 равно 3, и в пятой колонке, начиная с адреса 12+1 13, находятся три «1 в положениях 13, 14 и 15, соответственно, после чего интервал 12-16 дополняется «О в адресе 16. В табл. 1 не представлена обработка третьего и четвертого напряжений, которые обрабатываются таким же Образом, как первое и второе напряжения. Для каждой обработки осуществляются: суммирование всех единиц в интервале В, Я, что дает сумму S; приведение к нулю ячеек, содержащих в интервале В, запись числа «1, равного сумме S, вычисленной, начиная с адреса, расноложенного сразу после нижнего адреса В, а затем «О до верхнего адреса; после последней обработки вынолняется суммирование всех «1, записанных вплоть до точки прихода включительно, что дает характеристический модуль этой точки прихода. Запоминающее устройство машины образовано числом позиций на 1 бит, равным числу ячеек, т. е. Р, причем каждый бит представляет приращение на величину О или 1 для соответственной ячейки. Для избежания необходимостй одновременной обработки всех Р позиций ЗУ, связанных со всеми Р адресами ячеек, предпочтительно выполнить 34 на 2 линеек на 2 битов каждая, при Р . Линейка, к которой относится адрес, определяется тогда всеми битами самого старшего разряда указйнйбгб адреса. Для упрощения Обозначений и в иллюстративных целях ниже будет рассмотрено 34 на 2048 позиций (2), имеющее 2 16 линеек на 2 128 битов. Каждая линейка тогда предпочтительно разделена на 16 октетов, о бозначенных от до . Один из 128 битов линейки носит, таким Образом, обозначение из двух индексов М. Запоминающее устройство выполнено с использованием интегральных схем 8, 9, 10, которые содержат каждая 16 слов по 4 бита. Две последовательно соединенные 8, 9 интегральные схемы составляют 16 октетов, 32 последовательные интегральные схемы -позволяют, следовательно, образовать 16 линеек по 128 битов. Канал управления 13 дает возможность передавать на каждую интегральную схему команду записи или считывания. Можно использовать цепи ЗУ, -которые во время фазы считывания выдают на каждый выход дополнение накопленного бита. Для выполнения записи информации достаточно перевести канал 13 в логическое состояние «1 и подать на входы информацию, которая должна быть накоплена в адресованном слове. В случае запоминающего устройства, организованного с 16 линейками слов все 4 бита старшего разряда адреса, который содержит 11 битов, отводят для выборки одной строки из 16. Группа из этих 4 битов старшего разряда будет ниже Обозначена 1 для нижнего адреса и HI для верхнего адреса или в общей форме AI. В соответствии с изложенным выще необходимо выбрать все выходы позиций ЗУ, заключенных в интервале В, Н, с тем, чтобы сумматор 3 смог суммировать все «1, заключенные в этом интервале. Удобно выполнять это разрешение в два нриема, выбирая с одной стороны выходы. Находящиеся слева от 5, и с другой стороны выходы, находящиеся справа от Я, комбинируя затем эти выборки. Этот ти1П разрешения требует треугольных дешифраторов: их таблица истинности имеет треугольную конфигурацию типа представленной в табл. 2, -пригодную для трех битов. Дополняющий дешифратор, в котором «О были бы заменены «1 и, наоборот, -был бы естественно также треугольным дешифратором. Сложность треугольного дешифратора сильно возрастает с увеличением числа битов, поэтому предпочтительно разделять число обрабатываемых битов, что заставляет комбинировать несколько дешифраторов. С этой целью изобретение предусматривает разделение ка:ждой линейки на 128 битов на 16 октетов, -что -позволяет адресовать один из битов линейки с Помощью двух адресов, одного из 4 битов для избирания

Таблица 2

октета из числа 16 октетов и другого из 3 битов для избирания одного бита из 8 битов.

Можно сказать, что любой адрес Л из 11 битов разлагается на слово AI, образованное всеми 4 битами старшего разряда, на слово AZ, образованное всеми 4 битами среднего разряда, и на слово Лз, образованное всеми 3 битами младшего разряда (эти слова обозначены соответственно BI, BZ, BZ для нижнего адреса и HI, Н, Яз - для верхнего адреса).

Дешифратор 18 имеет четыре входа и 16 выходов, обозначенные В2, где i изменяется от I до 16, дешифратор 19 - три

входа и восемь выходов, обозначенных Вз где / изменяется от 1 до 8, дешифратор 21 - четыре входа и 16 выходов, обозначенных HZ, где t изменяется от 1 до 16, и дешифратор 22 - три входа и восемь выходов, обозначенных Яз, где / изменяется от 1 до 8.

Дешифраторы 17 и 20 формуют разрешение линейки. В этой линейке позиции разрешаются соответственно дешифраторами 18-19 для нижнего адреса и дешифраторами 21, 22 для верхнего адреса. Последнее разрешение в линейке выполняется с помощью канала 23 разрешения.

В соответствии со схемой, изображенной на фиг. 5, канал памяти разрешения выходов памяти в интервале S, Я содержит связанную с каждым выходом логическую схему 27 типа НЕ-ИЛИ, соединенную с выходом каждой лозиции запоминающего устройства, причем выход этой логической схемы НЕ-ИЛИ соединен с сумматором 3. Один из обоих входов логической схемы соединен с выходом позиции 25 ЗУ, а другой - с выходом логической схемы 28.

На фиг. 6 схематически представлены все 128 позиций линейки ЗУ, которые обозначены двумя индексами т. е. М Заштрихованная позиция является текушей позицией i-ro октета и /-го бита в этом октете. Для примера полагается, что нижний адрее В и верхний адрес Я обрабатываемого ограничения содержится в этой же линейке, т. е. Bi Hi (ниже будет рассмотрен случай, когда BI отлично от HI). Для разрешения интервала В, Я выбираются выходы, находящиеся слева от В (включительно В), и выходы, находящиеся справа от Я (включительно Я). Предполагается, что заштрихованный

элемент (фиг. 6) AfJ соответствует нижнему адресу, слева от которого требуется выбирать выходы.

Выборы (разрешения или запрещения) выполняются с помощью треугольных дещифраторов, форма таблиц истинности дана в табл. 2.

Ниже строчной буквой обозначено логическое состояние выхода дешифратора, т. е. например &2 для логического выхода 52 дешифратора 18 или hi для логического состояния выхода Яз дешифратора 22. Если элементу , ЗУ , М.,..., соединять непосредственно с выходом В2

дешифратора BZ и позиции , ,8 с выходом В и т. д., то выбираются все октеты от 1 до i, независимо от /. Именно это условно представлено на фиг. 2 сплошной чертой, идущей от первого бита октета до последнего бита октета разряда i.

Если соединять теперь выходы позиций М независимо от / с выходами то эти выходы будут иметь логические уровни, которые были логическими уровнями

позиций Л1+1 в предыдущем случае. В этом случае получают тогда разрешение до предыдущего октета.

Для выбора позиций от , , до MJ нужно добавить к состоянию, представленному второй чертой (фиг.2), сегмент, идущий от до /, в октете разряда 1. Значит логическое выражение bz, Ьз (где точка условно обозначает логическую операцию «И ) равно единице, если Ь и bi

равны оба единице; это выражение равно 1 вдоль сегментов, представленных третьей чертой на фиг. 2. Для разрешения выводов.

11

слева от Afl нужно, следовательно комбинировать вторую и третью линии. Схема 28 образована логическими схемами типа НЕ-И. Схема 28 имеет шесть входов, причем три входа 30, 31, 32 соединены с дешифраторами 18 и 19 нижнего адреса и три входа 32, 33, 34 - с дешифраторами 21 и 22 верхнего адреса.

Схема 28 имеет на своем выходе логический уровень 1 при всех позициях, заключенных на соединении обоих интервалов (1, и /Я, 128), если обозначает Первый бит линейки и 128 - последний бит этой линейки. Если этот выход соединен с логической схемой 27 НЕ-ИЛИ, соединенной с выходом позиции 25 связью 24, все выходы, которые не находятся на соединении (1,11-{-1Н, 128), разрешаются, т. е. окончательно выходы интервала В, Я, что и является искомым результатом.

Можно было бы реализовать эту же функцию с ПОМОЩЬЮ других логических схем, например, реализуя уже операции (1, , 128), затем исполъзуя логическзю схему И на выходе позиции памяти.

На сумматор 3 поступают логические сигналы тольКо с выходов ЗУ, которые были разрешены, т. е. которые заключены в интервале В, Н. Его функция состоит в получении суммы «I, содержащихся в этом интервале. Предпочтительно использовать сумматор, принцип действия которого состоит в следующем.

Все 128 битов распределены по 4 группам из 31 бито; оставшиеся биты обрабатываются по отдельности. Каждая группа обрабатывается в блоке сумматора, выходы которого соединяются затем с другим сумматором. Сумматоры -40-43 отведены для групп из 31 бита. Они выдают сигналы из 5 битов, которые посылаются на сумматор 44; .последний принимает, кроме того, 125-, 126- и 127-й биты рассматриваемой линейки. С выхода 45 сумматора 44 посылается слово из 7 битов, представляющее сумму всех «1, содержащихся в интервале В, Я.

После Получения суммы всех «1, заключенных в интервале В, Н, остается вычислить адрес X l-}-S, до которого следует записать все «1, начиная от нижнего адреса. Это сложение выполняется схемой, изображенной на фиг. 8.

В буферную память 50 на 8 битов поступают все 7 битов слов 62 Вз через логическую схему 51, управляемых одновременно по связи 52. Слово из 7 битов, возникающее на выходах буферной памяти 50, образует слово, обозначенное Х, Х.

На сумматор 53 поступают все 7 битов с буферной памяти 50 и все 7 битов с сумматооа 3, а также 128 битов по связи 54. Элементы схемы 55 открыты в период, когда закрыты элементы схемы 51 и, наоборот.

12

Счетчик 56 на 4 бита предварительно устанавливается в состояние BI, а тактовый вход 57 его соединен связью 58 с выходом старшего разряда сумматора 53. Слово из 4 битов с выхода счетчика 56 обозначено X и представляет все 4 бита старшего разряда адреса X, все 7 битов разряда которого соответствуют, кроме того, слову Xz Xz.

Значения с выхода сумматора 53 могут накапливаться в буферной памяти 50. Можно также прибавить столько раз, сколько это нужно, значения с выхода сумматора 3, чтобы учитывать случай, «огда адреса В и

Я не находятся в одной и той же линейке (Si отлично от Я)). Счетчик 60 предпочтительно з станавливается в состояние Б. На логическую схему 61 направления поступают Xi и HI; управляющая связь 62 определяет какое из слов Х или HI возникает на выходе 63. Схема 65 направления управляется сигналом, посылаемым по связи 62 и дополнительным сигналом, посылаемым с выхода 63. Схема 65 имеет два выхода 66

и 67, управляющих каждый одним из элементов схемы 68 направления, причем на один из элементов поступает слово Х2Х, а на другой - слово Яг Яз- Выход схемы 68 направления соединен с дещифраторами 21

и 22.

Принцип. действия этой схемы следующий: BI и Я посылаются на компаратор 64. Если HI BI, то этот компаратор открывает элементы схемы 68, которые пропускают ЯзЯз на дещифратор верхнего адреса. Дещифратор, получив информацию, формирует сигнал суммирования всех «1. Результат этой суммы прибавляется к нижнему адресу для получения адреса X, затем

выполняется повторная запись всех «1 В и X.

После этой операции сигнал «1, возникающий на входе 69, изменяет состояние схемы 65 направления, а именно XzX заменяют на выходе схемы 68 направления. На основе определения XzX запись всех «1 не превыщает адреса X. Сигнал управления, посылаемый по связи 62, действует та-кже на схему 61, которая посылает слова Ai на компаратор. Так как полагали, что , то Xi Hi, и не происходит изменения сигнала, посланного компаратором. В описании этого варианта для упрощения полагалось, что нижний и верхний адреса ограничения находились в одной и той же линейке. Ниже поясняется принцип действия машины, когда HI отлично от Sj. Если Я; отлично от BI, при сложениях

в сумматорах 3 и 53 к значению В прибавляется сумма всех «1 линейки BI. Тогда посылается импульс, который увеличивает содержимое счетчика 60 и выполняют новое сложение 5 +Si+S2.

Эти сложения выполняются до момента получения рзвенства между содержимым счетчика 60 и значением Яь Пока не иолучено это равенство, перезапись всех «1 запрешена. Когда содержимое счетчика 60 достигает значения Н,, триггер (не представленный на фиг. 9) изменяет состояние, обусловливая следующие операции: повторный ввод слова В в счетчик 60; формирование сигнала «1, возникающего на связи 69, котопый управляет через схему 61 передачей Х компапатора 64 и через схему 68 передачей Х Js к дещифратору верхнего адреса; разрешение перезаписи всех «1 в интервале В, Н. работы машины относится к обработке двумерного пространства, соответствующего систел-ге с двумя переменными. Очевидно, что можно реализовать мащипу, способную обработать либо парял-. р( лельпо, либо последовате.льно - проблем такого типа, связанных с проблемой, которую ставит поиск оптимального пути для системы с переменными параметХр-П . рами. При этом число ветствует числу различных комбинаций переменных, взятых по две. В этом случае ) Мишина укажет - оптимальных -- 2 элементарных действий, которые комбинируются любым пригодным методом для нахождения в р-мерном пространстве оптимального элементарного действия, 14 Формула изобретения Информационная машина для поиска оптимального пути между начальным и конечкым состояниями системы, содержащая регистры переменных начального и конечного состояний, запоминающее устройство и сумматор, отличающаяся тем, что, с целью повышения быстродействия и упрощения, она содержит блок коммутаций, блок записи единичных и нулевых значений и блок последовательного адресования, вход и первый выход которого соединены соответственно с выходами и входами регистров переменных начального и конечного состояний, а второй, третий и четвертый выходы подключены соответственно -к адресным входам запоминающего устройства, сумматора и блока коммутации, информационный вход которого соединен с выходом запоминающего устройства, а выход - подключен к входу сумматора, выход сумматора подключен к входу блока записи единичных и нулевых значений, выход которого соединен с входом запоминающего Зстройства. Источники информации, принятые во внимание при экспертизе 1.Патент США № 3653071, кл. 444-01 (G 06F 15/46), 1972. 2. А modification of LeeS pat connection algorithm. IEEE Transaction on Electronic Computers, EC 16, 1967 г., p. 97.

РигЛ

jj

J.r7

/ s

Л

-

3 г

W

.

.J

2S,

p..

32 H

./

JS

.33

f .

гэ::- ZS

37

30

-vfL.

.35

-1

fpUi.S

-vfLJ

L.

--.I

QJui.S

,Il

-з

-31

fz

4S

fus.7