1) площадка f — остановка (цель достигнута);
2) петля (П) — наматывание нити (от данной площадки расходятся, по крайней мере, два желтых коридора);
3) зеленая улица (ЗУ) — разматывание нити (от
- 622 -
данной площадки отходит хотя бы один зеленый коридор);
4) площадка a — остановка (исходный пункт);
5) отсутствие всех предыдущих признаков (ОП) — наматывание нити.
Попав на какую-нибудь площадку, свериться со схемой признаков и указанном порядке и делать очередной ход в соответствии с первым же обнаруженным признаком не проверяя остальных признаков. Такие ходы делаются до тех пор, пока не наступит остановка.
Один из возможных вариантов поиска содержит следующие ходы (в сокращенных обозначениях указаны номер хода, признак, ход, пройденный коридор, цвет коридора после его прохождения):
1) ЗУ — Р — ab — Ж;
2) ЗУ — Р — bc — Ж;
3) ЗУ — Р — cd — Ж;
4) ЗУ — Р — dg — Ж;
5) ЗУ — Р — gh — Ж;
6) ОР — Р — hg — K;
7) ОР — Р — gd — K;
8) ЗУ — Р — db — Ж;
9) П — Р - bd — K;
10) ЗУ — Р — df — Ж;
11) площадка f — остановка.
В данном случае площадка f оказалась достижимой (недостижимыми являются площадки i, k, l , m). Выделив коридоры, которые остались желтыми (ab, bc, cd, df), получим путь от a к f (abcdf, указанный на рис. 257 жирными дугами).
4. Общие свойства алгоритмов. Богатый опыт разработки и применения алгоритмов подсказывает ряд общих свойств, которые детализируют приведенное выше описание.
Дискретность алгоритма. Любой алгоритм можно рассматривать как процесс последовательного построения величин, идущий в дискретном времени по определенному предписанию, называемому программой. В начальный момент задается конечная совокупность величин (исходные данные), а в каждый следующий момент совокупность величин получается по программе из совокупности, имевшейся в предыдущий момент.
Детерминированность алгоритма. Совокупность величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется совокупностью величин, полученных в предшествующие моменты времени. Например, алгоритм поиска пути в лабиринте допускает произвол в выборе коридора при наличии нескольких зеленых коридоров, отходящих от данной площадки. Чтобы сделать его строго детерминированным, необходимо добавить предписание о выборе зеленого коридора ( например, первый по часовой стрелке).
Направленность алгоритма. Если способ получения последующей величины из какой-нибудь заданной не приводит к результату, то должно быть указание, что´ надо считать результатом алгоритма. Иначе говоря, алгоритм через конечное число тактов времени (шагов) должен привести к остановке, которая свидетельствует о достижении требуемого результата. Так, при поиске пути в лабиринте остановка наступает либо на достижимой площадке, либо при возвращении на исходную площадку, если указанная цель недостижима.
- 623 -
Массовость алгоритма. Алгоритм служит для решения целого класса задач, причем начальная совокупность величин может выбираться из некоторого множества. Например, в алгоритме Евклида числа a и b выбираются из бесконечного (счетного) множества целых числе, а в алгоритме поиска пути в лабиринте начальная и конечная площадки выбираются из конечного множества площадок лабиринта. В математике проблема считается решенной, если для нее найден общий алгоритм.
Элементарность шагов алгоритма. Предписание о получении последующей совокупности величин из предшествующей должно быть простым и локальным. Это означает, что соответствующая операция должна быть элементарной для исполнителя алгоритма (человека ли машины). Например, встречающиеся в алгоритме Евклида операции сравнения, вычитания и перестановки чисел можно было бы расчленить на более простые операции, если бы они не считались достаточно стандартными и привычными. В то же время сам алгоритм Евклида может фигурировать в качестве элементарной операции более сложного алгоритма.
5. Ассоциативное исчисление. Дальнейшее обобщение понятия алгоритма связано с ассоциативным исчислением, которое строится на множестве всех слов в данном алфавите.
Напомним, что алфавит представляет собой любую конечную систему различных символов, называемых буквами. Любая конечная последовательность n букв некоторого алфавита является словом длины n в этом алфавите. Например, в алфавите из трех букв {a, b, c} словами будут последовательности b, ac, bac, abba, cbcccacabca и т.д. Пустое слово, не содержащее ни одной буквы, обычно обозначается через ∧. если слово L является частью слова M, то говорят о вхождении слова L в слово M. Например, в слове abcbcbab имеются два вхождения слова bcb и одно вхождение слова ba.