ГЛАВА XII. АЛГОРИТМЫ

§ 12.1. Примеры алгоритмов

Начнем с рассмотрения нескольких типичных примеров алгоритмов.

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

Определение символа в бесконечной последовательности. Рассмотрим последовательность, состоящую из нулей и единиц, о которой известно, что символы 0 и 1 все время чередуются.

Если мы видим только изображенное ниже начало этой бесконечной последовательности и ничего больше о ней не знаем, то никакого представления о всей последовательности мы создать не сможем. Однако такое представление немедленно создается, как только мы узнаем ее свойство — нули и единицы всегда . Теперь мы без труда можем предсказать, какой символ стоит, например, на , на или на месте: для этого надо лишь выяснить, является ли номер места четным или нечетным.

Рассмотрим последовательность, представляющую собой периодически повторяющуюся группу цифр 0, 7, 5,3.

Зная факт периодичности и начало последовательности (один период), снова можно определить, какой символ стоит в любом месте последовательности; чтобы это сделать, надо: а) разделить номер места на длину периода (т. е. на число цифр в периоде); б) посмотреть, какая цифра расположена в первом периоде на том его месте, номер которого совпадает с остатком от деления.

Если остаток равен нулю, то надо смотреть последнюю цифру периода.

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

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

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

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

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

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

Алгоритм Евклида. Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя двух заданных целых положительных чисел а и . Этот алгоритм может быть записан в виде следующей системы последовательных указаний:

1. Обозревай данные числа а и . Переходи к следующему указанию.

2. Сравни обозреваемые числа , или , или ). Переходи к следующему указанию.

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

4. Если первое обозреваемое число меньше второго, то переставь их местами. Переходи к следующему указанию.

5. Вычитай второе число из первого и обозревай два числа: вычитаемое и остаток. Переходи к указанию 2.

Итак, после того как выполнено последнее пятое указание, надо вновь возвратиться ко второму указанию и т. д. до тех пор, пока не окажется выполненным условие, содержащееся в третьем указании. Тогда процесс прекращается.

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

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

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

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

Будем говорить, что площадка У достижима из площадки X, если существует путь, ведущий от X к Учерез промежуточные коридоры и площадки. Это означает, что либо X и У — смежные площадки, либо существует - последовательность смежных площадок .

Очевидно, что если площадка У вообще достижима с площадки X, то она достижима и посредством простого пути (без петель), т. е. такого пути, в котором каждая площадка проходится лишь один раз.

Так, в случае лабиринта, показанного на рис. 12.1, один из простых путей, ведущих от площадки Н к площадке В, будет HDCB. Площадка же L недостижима из площадки А.

Пусть поиск пути начинается от площадки А. Требуется выяснить, достижима ли площадка F из площадки А, и если да, то требуется найти путь из А в F. Если же площадка F окажется недостижимой, то требуется после поиска, вернуться в А.

Рис. 12.1.

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

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

Находясь на какой-либо из площадок, можно попасть на смежную площадку посредством одного из двух ходов:

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

б) Наматывание нити. Возвращение от данной площадки по последнему пройденному желтому коридору до смежной площадки. При этом нить наматывается, а коридор объявляется красным.

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

Находясь на какой-либо площадке, можно различать обстановку, характеризуемую одним из пяти признаков:

1) Это площадка F — цель достигнута.

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

3) Зеленая улица: от данной площадки отходит по крайней мере один зеленый коридор.

4) Это исходная площадка А.

5) Пятый случай. Отсутствие всех предыдущих признаков.

Метод поиска теперь может быть задан следующей схемой:

Находять на какой-либо площадке, следует делать очередной ход так: нужно проверить по порядку номеров в соответствии с левым столбцом схемы, какой из перечисленных признаков имеет место. Обнаружив признак, следует, не проверяя более последующих признаков, делать соответствующий ход. Такие ходы делаются до тех пор, пока не наступит остановка.

Относительно предложенного метода поиска можно доказать справедливость следующих трех утверждений:

Первое. При любом взаимном расположении А и F после конечного числа ходов наступит остановка либо на площадке А, либо - на площадке .

Второе. Если остановка наступит на площадке F, то цель достигнута и нить протянута по простому пути, ведущему от А к .

Третье. Если остановка наступила на площадке А, то площадка F недостижима.

Покажем на примере лабиринта (рис. 12.1), как действует предложенный метод.

Процесс поиска удобно изобразить в виде табл. 12.1.

Таблица 12.1

В данном случае площадка F достижима. Выделив в предпоследнем столбце те коридоры, которые остались желтыми, получим простой путь от А к .

Заметим, что описанный метод поиска в произвольном конечном лабиринте содержит элемент произвола, которого не было в ранее рассмотренных примерах. Так, при нахождении наибольшего общего делителя Двух заданных чисел с помощью алгоритма Евклида операции, которые будут сделаны разными вычислителями, руководствующимися указаниями 1—5 этого алгоритма, совпадут во всех своих деталях, и никогда не встретится такой ситуации, когда вычислителю придется что-либо выбирать по своему усмотрению.

Здесь же, если от некоторой площадки отходит несколько зеленых коридоров, искателю предоставлена возможность выбрать любой из них. Разные искатели могут прийти от площадки А к площадке F по-разному.

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