Информационная машина для поиска оптимального пути между начальным и конечным состоянием системы

 

О П И,„,C А,„,Н И Е

ИЗОБРЕТЕН ИЯ (»I665826

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

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

Республик

К П АТЕ НТУ (61) Дополнительный к патенту (22) Заявлено 13.05.74 (21) 2030119/18-24 (23) Приоритет — (32) 14.05.73 (31) 7317873 (33) Франция (43) Опубликовано 30.05.79. Бюллетень № 20 (45) Дата опубликования описания 30.05.79 (51) М. Кл

G 06F 15/20

Государственный комитет по делам изобретений и открытий (53) УДК 681.322 (088.8) (72) Авторы изобретения

Иностранцы

Жан Ледье и Филип Эшанбреннер (Франция) Иностранная фирма

«СИБКО С. А.» (Франция) (71) Заявитель (54) ИНФОРМАЦИОННАЯ МАШИНА ДЛЯ ПОИСКА

ОПТИМАЛЬНОГО ПУТИ МЕЖДУ НАЧАЛЬНЫМ И

КОНЕЧНЫМ СОСТОЯНИЯМИ СИСТЕМЫ

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

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

Известна вычислительная машина, которая содержит процессор, запоминающее устройства, устройства ввода-вывода данных (1).

Эта машина используется для компоновки электронных элементов и их соединений на поверхности печатных плат с применением волнового алгоритма для отыскания кратчайшего пути соединения точек при имеющихся ограничительных требованиях, Комплексные пробелы определения последовательности операций с большим числом переменных могут быть решены этой вычислительной машиной при условии, что она имеет достаточную емкость памяти и что нужное время ответа не будет слишком коротким. Сложные проблемы, связанные с эксплуатацией, могут быть решены большими группами побочных вычислительных машин, дающих решение за несколько десятков минут. Таким образом, можно составлять предварительные программы воздушных и железнодорожных графиков, производства и распределения электроэнергии, изготовления автомашин из сырья, получаемого с различных заводов, Ес10 ли случайная причина нарушила процесс эксплуатации, то для такой ситуации не существует достаточно мощной группы вычислительных машин для того, чтобы за короткое время исправить положение. Ра15 ботающая вычислительная машина выполняет операции последовательно, поэтому ей требуется сравнительно много времени.

Из известных машин наиболее близкой по технической сущности к изобретению яв20 ляется вычислительная машина (2), содержащая регистры переменных начальных у1стройств и сумматор. В машине используется метод записи в ячейку запоминающего устройства плоскости шага, который от25 деляет ее от начальной точки, рассматриваемой как исходная точка. Точнее, если обозначить А исходную точку и В конечную точку, то в ячейках, смежных с исход66582Ц

3 ной ячейкой, записывают цифру «1». Затем во всех ячейках, смежных с ячейками, в которых записана цифра «1», записывают цифру «2», после этого во всех ячейках, смежных с ячейками с цифрой 2, записывают цифру 3, и т. д. В конце шагов получают конечную точку В. Самый короткий путь можно начертить, начиная от точки

В и соединяя смежные ячейки, содержимое которых убывает на единицу с каждым шагом.

Этот алгоритм дает, помимо оптимального пути, его длину. Но машина, работающая в соответствии с этим алгоритмом, должна обязательно иметь NÐ позиций памяти, если N представляет квантовые величины, которые могут принимать каждая из обеих переменных плоскости, что является черезмерным в большинстве практических случаев использования, когда. число N может достигать, например, нескольких тысяч. Кроме того, эти позиции должны быть рассчитаны на запоминание числа, по крайней мере равного длине оптимального пути, который в некоторых случаях может приближаться к величине 2 N, что еще более не допустимо.

Для избежания этого недостатка был предложен алгоритм, в котором числа, записанные в ячейках, образуют такую последовательность, что число, которое предшествует символу этой последовательности, отлично от последующего числа. Таким образом, элементы памяти могут быть рассчитаны на запись органиченного числа разрядов, например 2, тем не менее в этом случае машина, использующая этот алгоритм, содержит NÐ позиций памяти.

Известен также итеративный алгоритм, в соответствии с которым поступают следующим образом. Сначала записывают во все ячейки плоскости «О», а «1» записывается в ячейку А, соответствующую исходной точке. Цифры «1» записываются затем во все ячейки, которые содержат еще

«0» и являются смежными с ячейками, в которых уже записана «1». Запись «1» распространяется таким образом от шага к шагу, и после нескольких шагов достигают ячейки С, начиная с которой можно за один шаг достигнуть конечной ячейки В.

Первое оптимальное элементарное действие, которое должна испытать система, является тогда тем, в результате которого система переходит от состояния точки В к состоянию точки С. После выполнения этого первого элементарного действия содержимые ячеек плоскости сводятся к нулю, и повторяется процесс исследования с помощью новой записи «1», при этом точку принимают за уровень конечной точки. После ряда шагов получают точиу М, начиная с которой можно достигнуть точки С за один шаг. Второе элементарное оптимальное действие — это действие, заставляющее пе5

4 рейти систему из точки С в точку М. Процесс повторяется до достижения исходной точки А.

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

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

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

Это дает возможность с одной стороны использовать лишь 2 N позиций памяти, что с учетом значений, которые число Л" способно принимать в практических случаях, ведет к значительному упрощению оборудования, С другой стороны, не производится исследования плоскости шаговым методом, что потребовало бы черезмерно большого времени. Это исследование осуществляется от ограничения к ограничению, что значительно повышает быстроту расчета.

Содержимое каждого из элементов памяти позволяет найти оптимальный путь без необходимости предусмотрения элементов памяти, максимальная емкость которых порядка величины оптимального пути, На фиг. 1 дана блок-схема машины; на фиг. 2 показано двумерное пространство для иллюстрации работы машины с двумя переменными; на фиг. 3 приведен пример конфигурации запоминающего устройства; на фиг. 4 изображен канал разрешения выходов позиций запоминающего устройства; на фиг. 5 показан пример реализации канала разрешения выходов позиций запоминающего устройства; на фиг. б схематически представлены все 128 позиций линейки 34; на фиг, 7 изображена схема сумматора; на фиг. 8 — схема вычисления адреса; на фиг. 9 дан пример реализации схем управления, Машина содержит регистры 1 перемен466826

«верхним диагональным адресом», обозначенным через Н, соответствует в представ- 45 ляющей плоскости точке напряжения, расположенной на самой верхней диагонали плоскости, а другое, называемое «нижним диагональным адресом», обозначенным через В, .соответствует точке напряжения, 50 расположенной на самой нижней диагонали плоскости.

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

Функция этой полосы из 18 ячеек соб0 б5,йых начальйого и конечного состояний, запоминающее устройство 2, сумматор 3, блок

4 коммутаций, блок 5 последовательного адресования, блок 6 записи единичных и нулевых значений (цифрой 7 обозначены средства установки исходного, нулевого, состояния запоминающего устройства), интегральные схемы 8, 9, 10, входы 11 и выходы

12 запоминающего устройства; канал 13 управления, канал 14 разрешения выходов (см. фиг. 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 N равно 18.

Таким образом, ЗУ содержит 18 ячеек.

Каждой из 18 ячеек присвоен адрес, называемый диагональным адресом. Эти адреса пронумерованы от 0 до 17. Можно считать, что эти ячейки приписаны одной из 18 диагоналей плоскости, представляющей поставленную задачу, Каждое напряжение выражается двумя числами, одно из которых, называемое стоит в вычислении искривления фронта волны при прохождении напряжения в 18 точках. Можно было бы создать машину, в которой ячейки вычисления и запоминания точно представляли бы сдвиг, выраженный в числе шагов фронта возмущенной волны относительно фронта невозмущенной волны. В этом случае первоначаль10

40 но в ячейках содержалось бы число, райное 0 для ячеек с адресами от 0 до 11 включительно, и числа, равные соответственно 1, 2, 3... 6 для ячеек с адресами от

12 до 17. Эта совокупность чисел представляет сдвиг между фронтом первоначально прямоугольной волны и фронтом теоретической линейной волны, совпадающими с осью ОУ.

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

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

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

В таблице 1 поясняется работа оператора.

В первой колонке находятся диагональные адреса, пронумерованные от 0 до 17, во второй †первоначальн сдвиги,в третьей колонке представлены приращения, соответствующие сдвигам из второй колонки.

Это приращение равно 0 вплоть до адреса

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

После обработки первого напряжения, определенного адресами В=8 и Н=13, в ячейках приращения оказываются равными 0 или 1 в зависимости от того, равно ли содержимое ячейки содержимому предшествующей ячейки или оно превышает его на единицу. После обработки первого напряжения новые приращения являются приращениями из четвертой колонки.

Ь65826

Таблица 1

Прира щение после второго напряжения

Началь- Приращение ное после прира- первого щение напряжения

Начальный сдвиг

Адрес

15

25

В пятой колонке проставлены приращения после второго напряжения, Между адресами В= 12 и Н= 16 сосчитанное число

«1» равно 3, и в пятой колонке, начиная с адреса 12+ 1 = 13, находятся три «1» в по- 35 ложениях 13, 14 и 15, соответственно, после чего интервал 12 — 16 дополняется «О» в адресе 16.

В табл. 1 не представлена обработка третьего и четвертого напряжений, кото- 40 рые обрабатываются таким же образом, .как первое и второе напряжения. Для каждой обработки осуществляются: суммирование всех единиц в интервале (В, Н), что дает сумму S; приведение к нулю ячеек, со- 45 держащих в интервале (В, H); запись числа

«1», равного сумме S, вычисленной, начиная с адреса, расположенного сразу после нижнего адреса В, а затем «О» до верхнего адреса; после последней обработки выпол- 50 няется суммирование всех «1», записанных вплоть до точки прихода включительно, что дает характеристический модуль этой точки прихода.

Запоминающее устройство машины обра- 55 зовано числом позиций на 1 бит, равным числу ячеек, т. е. Р, причем каждый бит представляет приращение на величину 0 или 1 для соответственной ячейки. Для избежания необходимости одновременной об- 60 работки всех P позиций ЗУ, связанных со всеми P адресами ячеек, предпочтительно выполнить 34 на 2ч линеек на 2" битов каждая, при Р=2ч+". Линейка, к которой относится адрес, определяется тогда всеми би- 65

17

16

14

13

12

11

8

6

4

2

1

1

1

0

1

0

0

0

0

8 тами самого старшего разряда указанног0 адреса. Для упрощения обозначений и в иллюстративных целях ниже будет рассмотрено 34 на 2048 позиций (2"), имеющее

24=16 линеек на 2 =128 битов. Каждая линейка тогда предпочтительно разделена на 16 октетов, обозначенных от j= 1 до

j=8. Один из 128 битов линейки носит, таким образом, обозначение из двух индексов Я 1.

Запоминающее устройство выполнено с использованием интегральных схем 8, 9, 10, которые содержат каждая 16 слов по 4 бита. Две последовательно соединенные 8, 9 интегральные схемы составляют 16 октетов, 32 последовательные интегральные схемы позволяют, следовательно, образовать 16 линеек по 128 битов. Канал управления 13 дает возможность передавать на каждую интегральную схему команду записи или считывания.

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

Для выполнения записи информации достаточно перевести канал 13 в логическое состояние «1» и подать на входы информацию, которая должна быть накоплена в адресованном слове.

В случае запоминающего устройства, организованного с 16 линейками слов все 4 бита старшего разряда адреса, который содержит 11 битов, отводят для выборки одной строки из 16. Группа из этих 4 битов старшего разряда будет ниже обозначена В для нижнего адреса и Н> для верхнего адреса или в общей форме Аь

В соответствии с изложенным выше необходимо выбрать все выходы позиций ЗУ, заключенных в интервале (В, Н), с тем, чтобы сумматор 3 смог суммировать все

«1», заключенные в этом интервале.

Удобно выполнять это разрешение в два приема, выбирая с одной стороны выходы, находящиеся слева от В, и с другой стороны выходы, находящиеся справа от Н, комбинируя затем эти выборки. Этот топ разрешения требует треугольных дешифраторов: их таблица истинности имеет треугольную конфигурацию типа представленной в табл. 2, пригодную для трех битов.

Дополняющий дешифратор, в котором «О» были бы заменены «1» и, наоборот, был бы естественно также треугольным дешифратором.

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

С этой целью изобретение предусматривает разделение каждой линейки на 128 битов на 16 октетов, что позволяет адресовать один из битов линейки с помощью двух адресов, одного из 4 битов для избирания

Входы дешифратора

665826

Выходы дешифратора

Таблица 2 октета из числа 16 октетов и другого из

3 битов для избирания одного бита из 8 битов.

Можно сказать, что любой адрес А из

11 битов разлагается на слово Аь образованное всеми 4 битами старшего разряда, на слово А, образованное всеми 4 битами среднего разряда, и на слово Аз, образованное всеми 3 битами младшего разряда (эти слова обозначены соответственно Bt, В, Вз для нижнего адреса и Ht, Н, Нз— для верхнего адреса) .

Дешифратор 18 имеет четыре входа и 16

t выходов, обозначенные В, где г изменяется от 1 до 16, дешифратор 19 — три

15 входа и восемь выходов, обозначенных Вз, где j изменяется от 1 до 8, дешифратор

21 — четыре входа и 16 выходов, обозна1 ченных Нз, где iизм,еняется от 1 до 16, и дешифратор 22 — три входа и восемь выходов, обозначенных Нз, где j изменяется

J от1до8.

Дешифраторы 17 и 20 формуют разрешение линейки. В этой линейке позиции разрешаются соответственно деши фраторами

18 — 19 для нижнего адреса и дешифраторами 21, 22 для верхнего адреса. Последнее разрешение в линейке выполняется с помощью канала 23 разрешения.

В соответствии со схемой, изображенной на фиг. 5, канал памяти разрешения выходов памяти в интервале (В, Ht содержит связанную с каждым выходом логическую схему 27 типа НŠ— ИЛИ, соединенную с 35 выходом каждой позиции запоминающего устройства, причем выход этой логической схемы НŠ— ИЛИ соединен с сумматором 3.

Один из обоих входов логической схемы соединен с выходом позиции 25 ЗУ, à дру- 40 гой — с выходом логической схемы 28.

На фиг. 6 схематически представлены все

128 позиций линейки ЗУ, которые обозначены двумя индексами т. е. М1 . Заштрихованная позиция является текущей позици- 45 ей i-го октета и /-го бита в этом октете, Для примера полагается, что нижний адрес В и верхний адрес H обрабатываемого ограничения содержится в этой же линейке, т. е. Bt — Ht (ниже будет рассмотрен случай, когда В отлично от Н ).

Для разрешения интервала (В, Н) выбираются выходы, находящиеся слева от

В (включительно В), и выходы, находящиеся справа от H (включительно Н).

Предполагается, что заштрихованный элемент (фиг. 6) Ми соответствует нижнему адресу, слева от которого требуется выбирать выходы.

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

Ниже строчной буквой обозначено логическое состояние выхода дешифратора, t т. е. например Ь для логического выхода

Вз дешифратора 18 или и для логического состояния выхода Н, дешифратора 22.

Если элементу ЗУ М, М",, M 8 соединять непосредственно с выходом В> дешифратора Вз и позиции Мз, М" М з— с выходом В и т. д., то вьгбираются все октеты от 1 до г, независимо от 1. Именно это условно представлено на фиг. 2 сплошной чертой, идущей от первого бита октета до последнего бита октета разряда г.

Если соединять теперь выходы позиций

М независимо от j с выходами В +, то эти выходы будут иметь логические уровни, которые были логическими уровнями позиций М+ в предыдущем случае. В этом случае получают тогда разрешение до предыдущего октета.

Для выбора позиций от i= 1, j= 1, до

МН нужно добавить к состоянию, представленному второй чертой (фиг.2), сегмент, идущий от j= l до j, в октете разряда i.

1 j

Значит логическое выражение Ьь "з (где точка условно обозначает логическую onet рацию «И» )равно единице, если bã и b< равны оба единице; это выражение равно

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

665826

11 слева от М1 нужно, следовательно комбинировать вторую и третью линии. Схема

28 образована логическими схемами типа

НŠ— И. Схема 28 имеет шесть входов, причем три входа 30, 31, 32 соединены с дешифраторами 18 и 19 нижнего адреса и три входа 32, 33, 34 — с дешифраторами 21 и

22 верхнего адреса.

Схема 28 имеет на своем выходе логический уровень 1 при всех позициях, заключенных на соединении обоих интервалов (1, В1I и IH, 128), если обозначает первый бит линейки и 128 — последний бит этой линейки. Если этот выход соединен с логической схемой 27 НŠ†И, соединенной с выходом позиции 25 связью 24, все выходы, которые не находятся на соединении (1 11+1Н, 128), разрешаются, т. е. окончательно выходы интервала (В, Н), что и является искомым результатом.

Можно было бы реализовать эту же функцию с помощью других логических схем, например, реализуя уже операции (1, В1+1Н, 128), затем используя логическую схему И на выходе позиции памяти.

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

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

44 посылается слово из 7 битов, представляющее сумму всех «1», содержащихся в интервале (В, Н).

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

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

На сумматор 53 поступают все 7 битов с буферной памяти 50 и все 7 битов с сумматооа 3, а также 128 битов по связи 54.

Элементы схемы 55 открыты в период, когда закрыты элементы схемы 51 и, наоборот.

12

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

4 битов с выхода счетчика 56 обозначено

XI и представляет все 4 бита старшего разряда адреса Х, все 7 битов разряда которого соответствуют, кроме того, слову

Х Хз.

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

Н не находятся в одной и той же линейке (В> отлично от Н,). Счетчик 60 предпочтительно устанавливается в состояние Вь На логическую схему 61 направления поступают Х1 и Н1, управляющая связь 62 определяет какое из слов Х или Н1 возникает на выходе 63. Схема 65 направления управляется сигналом, посылаемым по связи 62 и дополнительным сигналом, посылаемым с выхода 63. Схема 65 имеет два выхода 66 и 67, управляющих каждый одним из элементов схемы 68 направления, причем на один из элементов поступает слово Х,Х,, а на другой — слово Н, Нз. Выход схемы 68 направления соединен с дешифраторами 21 и 22.

Принцип действия этой схемы следующий: В и Н посылаются на компаратор

64. Если Н1 — — Вь то этот компаратор открывает элементы схемы 68, которые пропускают Н Н, на дешифратор верхнего адреса. Дешифратор, получив информацию, формирует сигнал суммирования всех «1».

Результат этой суммы прибавляется к нижнему адресу для получения адреса Х, затем выполняется повторная запись всех «1» между В и Х.

После этой операции сигнал «1», возникающий на входе 69, изменяет состояние схемы 65 направления, а именно Х Хз заменяют Н Нз на выходе схемы 68 направления. На основе определения Х Хз запись всех «1» не превышает адреса Х. Сигнал управления, посылаемый по связи 62, действует также на схему 61, которая посылает слова Х, на компаратор. Так как полагали, что B> —— H„=Н„и не происходит изменения сигнала, посланного компаратором.

B описании этого варианта для упрощения полагалось, что нижний и верхний адреса ограничения находились в одной и той же линейке. Ниже поясняется принцип действия машины, когда Н1 отлично от Вь

Если Н1 отлично от В, при сложениях в сумматорах 3 и 53 к значению В прибавляется сумма всех «1» линейки Вь Тогда посылается импульс, который увеличивает содержимое счетчика 60 и выполняют новое сложение B>+S +S .

Эти сложения выполняются до момента

665826

14

Рыг. 2 получения равенства между содержимым счетчика 60 и значением Нь Пока не получено это равенство, перезапись всех «1» запрещена, Когда содержимое счетчика 60 достигает значения H триггер (не представленный на фиг. 91 изменяет состояние, об чсловливаn следующие операции: повторный ввод слова В1 в счетчик 60; формирование сигнала «1», возникающего на связи 69, котооый управляет через схему 61 передачей Х1 компапатора 64 и через схему 68 передачей Х> Х: к дешифратору верхнего адреса; разоешение перезаписи всех

«1» в интервале (В, Н).

Опи ание работы машины относится к обпаботке двумерного пространства, соответствующего системе с двумя переменным .. Очевидно, что можно реализовать матпину, способную обработать либо парялр< р — 11 2 ) лельно, либо последовательно проблем такого типа, связанных с проблемой, которую ставит поиск оптимального пути для системы с переменными параметр р — I > 25 рами. При этом число соот2 ветствует числу различных комбинаций переменных, взятых по две. В этом случае

p" p I)

va èèíà укажет — -- — — - оптимальных

2 30 элементарных действий, которые комбинируются любым пригодным методом для нахождения в р-мерном пространстве оптимального элементарного действия, Формула изобретения

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

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

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

1. Патент CLUA № 3653071, кл. 444 — 01 (G 06F 15/46), 1972.

2. Л modification of Lee S patl connection algorithm. IEEE Transaction on

Electronic Computers, ЕС 16, 1967 г., р. 97.

Редактор Т. Рыбалова

Техред H. Строганова

Корректор Е. Угроватова

Заказ 1043/16 Изд. № 362 Тираж 779 Подписное

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

113035, Москва, )К-35, Раугпская наб., д. 4/5

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