Полное построение алгоритма шаг за шагом

Построение модели

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

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

1. Какие математические структуры больше всего подходят для задачи?

2. Существуют ли решенные аналогичные задачи?

Второй вопрос, возможно, самый полезный во всей математике. В контексте моделирования он часто дает ответ на первый вопрос. Действительно, большинство решаемых в математике задач, как пра­вило, являются модификациями ранее решенных. Большинство из нас просто не обладает талантом Ньютона, Гаусса или Эйнштейна, и для продвижения вперед нам приходится руководствоваться накоп­ленным опытом.

Сначала нужно рассмотреть первый вопрос. Мы должны описать математически, что мы знаем и что хотим найти. На выбор соответст­вующей структуры будут оказывать влияние такие факторы, как: 1) ограниченность наших знаний относительно небольшим количест­вом структур, 2) удобство представления, 3) простота вычислений, 4) полезность различных операций, связанных с рассматриваемой структурой или структурами.

Сделав пробный выбор математической структуры, задачу следует переформулировать в терминах соответствующих математических объектов. Это будет одна из возможных моделей, если мы можем ут­вердительно ответить на такие вопросы, как:

Вся ли важная информация задачи хорошо описана математиче­скими объектами?

Существует ли математическая величина, ассоциируемая с иско­мым результатом?

Выявили мы какие-нибудь полезные отношения между объектами

модели?

Можем мы работать с моделью? Удобно ли с ней работать?

Пример. Возвращаемся к задаче агента по продаже компьютеров, рассмотренной ранее в этом разделе. Начинаем с постановки задачи, данной в конце примера.

Решали ли мы ранее аналогичные задачи? В математическом смысле, вероятно, нет. Однако все мы сталкивались с задачами вы­бора пути по дорожным картам или в лабиринтах. Можем ли мы прийти к удобному представлению нашей задачи наподобие карты?

Очевидно, нужно взять лист бумаги и нанести на нем по одной точке, соответствующей каждому городу. Мы не собираемся изобра­жать точки так, чтобы расстояние между каждой парой точек, соот­ветствующих городам.i и /, было пропорционально стоимости проезда Cij. Расположим точки любым удобным способом, соединим точки i и / линиями и проставим на них «веса» Сц.

Схема, которую мы только что изобразили,— это частный случай известного в математике графа, или сети. В общем случае сеть — это множество точек (на плоскости) вместе с линиями, соединяющими некоторые или все пары точек; над линиями могут быть проставлены веса. Для простоты предположим, что у Джека только пять городов, для которых матрица стоимостей показана на рис. 1.3.1, а. Тогда сете­вая модель может быть изображена, как на рис. 1.3.1, б. Предполо­жим также, что стоимость проезда из города i в город / такая же, как н из / в I, хотя это и необязательно. Что мы ищем в задаче? В терминах теории сетей список городов (который мы ранее описали) определяет замкнутый цикл, начинаю­щийся с базового города и возвращающийся туда же после прохож­дения каждого города по одному разу. Такой цикл соответствует не­отрывному движению карандаша вдоль линий сети, которое проходит через каждую точку только один раз и начинается и оканчивается в одной и той же точке. Обход такого

 

d

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

На рис. 1.3.1,6 обход 1—5—3—4—2—1 есть тур со стоимостью 5+2+1+4+1 = 13. Является ли он туром с минимальной стоимостью?

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

Разработка алгоритма

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

Пример. Вернемся к коммивояжеру из предыдущего раздела. По­становка задачи и модель, описанные ранее, наводят на мысль о сле­дующем алгоритме.

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

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

Algorithm ETS (Исчерпывающий коммивояжер). Решить задачу ком­мивояжера с N городами, последовательно рассматривая все переста­новки из N—1 положительных целых чисел. Таким образом мы рас­смотрим каждый возможный тур и выберем вариант TOUR с наимень­шей стоимостью MIN. Алгоритм ETS требует в качестве входных дан­ных число городов N и матрицу стоимостей С.

Шаг 0. [Инициализация, т. е. установка в начальное состояние]

Set TOUR^-0; and MIN^-oo. Шаг 1. [Образование всех перестановок] For /-<-1 to (N—1)! do through шаг 4 od; and STOP.

Шаг 2. [Получение новой перестановки] Set P-+-I-я пере­становка целых чисел 1,2,..., N—1. (Заметим, что здесь нужен под алгоритм.) Шаг 3. [Построение нового тура] Строим тур Т(Р), соот­ветствующий перестановке Р; and вычисляем стои­мость COST (Т (Р)). (Заметим, что здесь нужны два других под алгоритма.) Шаг 4. [Сравнение] If COST (7^,(P))<MIN then set TOUR+- <-T(P); and MIN^COST (7(P)) fi.

Алгоритм ETS — неплохое первое приближение к точному алго­ритму. Ему недостает некоторых важных под алгоритмов, и он недо­статочно близок к окончательной программе. Эти недостатки будут устранены позже.

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

3.Правильность алгоритма

Доказательство правильности алгоритма — это один из наиболее трудных, а иногда и особенно утомительных этапов создания алго­ритма.

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

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

Пример. Алгоритм ETS настолько прост, что его правильность легко доказать. Поскольку проверяется каждый тур, должен быть проверен и тур с минимальной стоимостью; как только до него дойдет очередь, он будет запомнен. Он не будет отброшен — это может слу­читься только в том случае, если существует тур с меньшей стоимо­стью. Алгоритм должен закончить работу, так как число туров, ко­торые нужно проверить, конечно. Подобный метод доказательства известен как «доказательство исчерпыванием»; это самый грубый из всех методов доказательства.

Подчеркнем тот факт, что правильность алгоритма еще ничего не говорит о его эффективности. Исчерпывающие алгоритмы редко бы­вают хорошими во всех отношениях.

4.Реализация алгоритма

Как только алгоритм выражен, допустим, в виде последователь­ности шагов и мы убедились в его правильности, настает черед реали­зации алгоритма, т. е. написания программы для ЭВМ.

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

Каковы основные переменные?

Каких они типов?

Сколько нужно массивов и какой размерности?

Имеет ли смысл пользоваться связными списками?

Какие нужны подпрограммы (возможно, уже записанные в па­мяти)?

Каким языком программирования пользоваться?

Конкретная реализация может существенно влиять на требования к памяти и на скорость алгоритма.

Другой аспект построения программной реализации —• это про­граммирование сверху - вниз. Объяснение этого понятия будет дано в разд. 2.1, а пока укажем, что программирование сверху - вниз — это подход к разработке и реализации, который состоит в преобразо­вании алгоритма в такую последовательность все более конкретизи­рованных алгоритмов, что окончательный вариант представляет собой

программу для ЭВМ.

Сделаем одно важное замечание. Одно дело — доказать правиль­ность конкретного алгоритма, описанного в словесной форме. Другое дело — доказать, что данная машинная программа, предположи­тельно являющаяся реализацией этого алгоритма, также правильна. Таким образом, необходимо очень тщательно следить, чтобы процесс преобразования правильного алгоритма (в словесной форме) в машин­ную программу «заслуживал доверия».

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

 

5.Анализ алгоритма и его сложности

Существует ряд важных практических причин для анализа алго­ритмов. Одной из них является необходимость получения оценок или границ для объема памяти или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память — относительно дефицитные (и дорогие) ресурсы, на которые часто одновременно претендуют многие пользователи. Всегда следует избегать прогонов программы, отвергаемых системой из-за нехватки запрошенного времени, которое указывается на рабо­чей карте. Поразительно, скольким программистам приходится слиш­ком дорогим способом выяснять, что их программа не может обрабо­тать входные данные раньше, чем через несколько дней машинного времени. Лучше было бы предугадать такие случаи с помощью каран­даша и бумаги для того, чтобы избежать ненужных прогонов. Хоро­ший анализ способен выявить узкие места в наших программах, т. е. разделы программы, на которые расходуется большая часть времени (см. упр. 1.3.16).

Существуют также важные теоретические причины для анализа алгоритмов. Хотелось бы иметь некий количественный критерий для сравнения двух алгоритмов, претендующих на решение одной и той же задачи. Более слабый алгоритм должен быть улучшен или отброшен. Желательно также иметь механизм для выявления наиболее эффек­тивных алгоритмов и замены устаревших. Иногда невозможно соста­вить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, в то время как другой лучше работает на каких-то специальных входных данных. Хотелось бы иметь возможность де­лать аналогичные выводы о сравнительных достоинствах двух алго­ритмов.

Важно также установить абсолютный критерий. Когда можно считать решение задачи оптимальным? Иными словами, когда наш алгоритм настолько хорош, что невозможно (независимо от наших умственных способностей) значительно его улучшить?

Пусть А — алгоритм для решения некоторого класса задач, an — размерность отдельной задачи из этого класса. Во многих задачах в этой книге n — просто скаляр, равный числу вершин графа. В об­щем случае n может быть массивом или длиной вводимой последова­тельности. Определим f_A (п) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций (сложения, сравнения и т. д.), которые должен выполнить алгоритм А для реше­ния любой задачи размерности п. Будем пользоваться следующим критерием для оценки качества алгоритма А. Говорят, что алгоритм А полиномиальный, если f_A(n) растет не быстрее, чем полином от п, в противном случае алгоритм А экспоненциальный. Этот критерий основан на времени работы в худшем случае, но аналогичный крите­рий может быть также определен для среднего времени работы. «периментальная» основа для этого критерия качества заключается в том, что, по-видимому, последовательные или параллельные машины более или менее способны воспринимать полиномиальные алгоритмы для больших задач, а на экспоненциальных алгоритмах они доволь­но быстро «задыхаются».

Следующее обозначение стандартно во многих математических дисциплинах, в том числе и в анализе алгоритмов. Функцию }(n) определяют как О и говорят, что она порядка g(n) для боль­ших п, если

lim = constant =/=0.

П оо § (я) ^

Это обозначается, как f(n)=0[g(n)]. Функция h(n) является о [z(n) для больших я, если

lim ₌ П-+ ОО ² (я)

Эти символы произносятся соответственно, как «О большое» и «о ма­лое». Интуитивно, если /(z) есть 0[g(n)], то эти две функции, по су­ществу, возрастают с одинаковой скоростью при z-*-оо. Если /(z) есть o[g(n)], то g(n) возрастает гораздо быстрее, чем (z).

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

Генетический алгоритм

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Пример

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

#define KEY_LEN 2048 // Длина ключа

bool key[KEY_LEN]; //Неизвестный ключ

#define POP_SIZE 20 // Размер популяции

#define ELITE 5 // Количество привелигированных особей

struct gen_struct { // Особь, кортеж из генов и значения пригодности

bool gen[KEY_LEN];

int fitness;

gen_struct(){ //Инициализация случайными значениями

for(int i=0;i<KEY_LEN;++i)

gen[i]=(random()%2==0);

}

bool operator<(const gen_struct & g)const{

return (g.fitness>fitness);

}

gen_struct(const gen_struct& g){

for(int i=0;i<KEY_LEN;++i) gen[i]=g.gen[i];

fitness=g.fitness;

}

void Mutate(){ //Оператор мутаций

gen[random()%KEY_LEN]=random()%2;

}

void Crossingover(gen_struct & g){ //Оператор скрещивания

for(int i=0;i<KEY_LEN;++i){

if(random()%2){

gen[i]=g.gen[i];

}

}

}

};

int Fitness(bool gen[]){ //Целевая функция

int ret=0;

for(int i=0;i<KEY_LEN;i++){

ret+=(key[i]!=gen[i]);

}

return ret;

}

void GA(gen_struct &ret){

vector<gen_struct> pop;

pop.resize(POP_SIZE);

while(1){

for(int i=0;i<POP_SIZE;++i)

if((pop[i].fitness=Fitness(pop[i].gen))==0){

ret=pop[i];

return;

}

sort(pop.begin(), pop.end());

for(int i=ELITE;i<POP_SIZE;++i){// 5 лучших остаются без изменений

pop[i].Crossingover(pop[random()%(ELITE)]);

pop[i].Mutate();

}

}

}

int main(){

for(int i=0;i<KEY_LEN;i++){

key[i]=(random()%2==0);

}

gen_struct ret;

GA(ret);

cout << "key=";

for(int i=0;i<KEY_LEN; i++){

cout << ret.gen[i];

}

cout << endl;

}

Преимущества ГА

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

Недостатки ГА

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

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

Суть алгоритма

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

Разновидности

Практическое применение

Волновой алгоритм — один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма — поиск кратчайшего расстояния на карте в стратегических играх.

Численные алгоритмы

Методы интерполяции

Алгоритм Герона

Векторный алгоритм

Описание

Его можно представить как: «расскажи своим соседям, как выглядит Кэп». Каждый узел ведет таблицу маршрутизации с одной записью для каждого маршрутизатора подсети. Таблица представляет собой вектор, содержащий 2 компонента: выбранную линию и дистанцию. Узел оценивает дистанцию (количество ходов, задержку или длину очереди) до каждого соседа и рассылает её своим соседям, которые в свою очередь выполняют то же самое. В результате полученной информации каждый узел заново подсчитывает таблицу маршрутизации. Применяется в протоколе маршрутизации RIP. Впервые был применен в ARPANET.

Алгоритм

Предположим, что таблица только что была получена от соседа X, причем Xi является предположением X о том, сколько длится путь до маршрутизатора i. Если маршрутизатор знает, что передача данных до X длится m, то он знает так же, что он может достичь любой маршрутизатор і через X за Xi+m.

Плюсы и минусы

+самоорганизация

+относительно простая реализация

-плохая конвергенция («сходимость»)

-сложности при расширении сети

Пример

Алгоритмы баз данных

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

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

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

 

Добавление

Ввод новых данных

сущ запись в картотеке?

Создание записи в картотеке

Меню

Рисунок 4.1 – Алгоритм добавления новых данных

 

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

 

Меню

Удаление из журнала

Удалить из журнала

Рисунок 4.2 – Алгоритм удаления записи из журнала посещений

 

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

 

Удаление из журнала

Меню

Удалить из картотеки

Удаление из картотеки

Рисунок 4.3 – Алгоритм удаления данных из картотеки

При выборе 4-ого пункта происходит редактирование данных. При этом перед пользователем будет поставлен выбор – редактирование информации из первой либо из второй таблицы он желает осуществить (из журнала посетителей или из картотеки). В зависимости от выбора пользователя перед ним высветятся либо данные картотеки либо данные журнала посетителей и пользователь выберет номер редактируемой записи..При этом все данные выбранной строки удаляются и пользователь заново введет все данные о пациенте в выбранную таблицу (см. рис. 4.4).

 

Меню

Редактирование картотеки

Редактировать

редактирование картотеки

Редактирование журнала

Рисунок 4.4 – Алгоритм редактирования данных

 

При выборе пункта просмотра пользователю будут предложены два варианта – просмотр списка посещений либо просмотр картотеки. Выбранная таблица высветится на экране (см. рис. 4.5).

Меню

Просмотреть журнал

Просмотреть картотеку

Просмотр

просмотреть картотеку?

Рисунок 4.5 – Алгоритм просмотра данных

 

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

 

Меню

Поиск по имени

Вывод данных пользователя из журнала

Ввод фамилии пользователем

Вывод на экран данных пользователя из картотеки

Рисунок 4.6 – Алгоритм поиска по фамилии

Выход. При выборе этого пункта пользователем будет осуществлен выход из программы (см. рис. 4.8).

 

Меню

Выход

Рисунок 4.8 – алгоритм выхода из программы

Полное построение алгоритма шаг за шагом

 

 

1.Постановка задачи.

2.Построение модели.

3.Проверка правильности алгоритма.

4.Реализация алгоритма.

5.Анализ алгоритма и его сложности.

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

 

Алгоритмы

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

Попытаемся сначала выразить наши интуитивные соображения. Мы можем нестрого определить алгоритм как однозначно трактуемую процедуру решения задачи. Процедура — это конечная последова­тельность точно определенных шагов или операций, для выполнения каждой из которых требуется конечный объем оперативной памяти и конечное время. Дополнительно потребуем, чтобы алгоритм работал конечное время для любых входных данных.

Одно из неудобств этого определения состоит в том, что термин «однозначная трактовка» весьма неоднозначен. «Однозначен» для кого? Или по отношению к чему? Поскольку ничто не является абсолютно ясным или абсолютно неясным, должен быть указан, хотя бы неявно, исполнитель. Алгоритм вычисления производной кубического поли­нома может быть вполне ясен тем, кто знаком с анализом, но для прочих он может оказаться совершенно непонятным. Таким образом, следует также указать вычислительные возможности исполнителя.

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

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

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

Этот компьютер будет иметь неограниченную память с произволь­ным доступом, в которой могут храниться действительные и целые числа, а также логические константы. В одном слове этой памяти можно хранить произвольное конечное число, и можно извлечь любое слово за фиксированное, постоянное время (это удобное предположе­ние, может быть, немного нереалистично, но на практике это почти так). Такой компьютер может выполнять хранимую программу, кото­рая состоит из допустимой последовательности команд, охватываю­щих все стандартные арифметические операции, операции сравнения, переходы и т. д. Обычно мы будем считать, что каждая такая команда выполняется за единицу времени. Простыми описаниями часть памяти может быть организована в одно-, двух- и трехмерные массивы (мат­рицы). Мы будем пользоваться языком Фортран в качестве модели возможностей нашей машины, когда нужно будет что-то конкретизи­ровать.

По сути дела мы утверждаем, что только тогда имеется алгоритм для решения задачи, когда можно написать программу для ЭВМ, решающую эту задачу. Это спорный вопрос. Программы на описанном выше компьютере не могут зашнуровывать ботинки. Среди точно оп­ределенных шагов не содержатся шаги, необходимые для завязывания шнурков. Имеются весомые аргументы в пользу того, что мы на самом деле оперируем ограниченным понятием алгоритма. Человек, как машина, способен выполнять множество тонких операций, которые лежат за рамками возможностей нашего типичного компьютера. Од­нако ограниченное определение — это как раз то, что нам требуется в данной книге.

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

Рассмотрим простую задачу нахождения максимального числа в списке из N действительных чисел

R(1), R(2),..., R(N). Основная идея алгоритма заключается в том, чтобы перебирать по очереди все числа списка и запоминать наибольшее до сих пор встретившееся чис­ло. К тому моменту, когда весь список будет проверен, запомнится наибольшее число. Попробуйте нарисовать блок-схему этого алго­ритма прежде, чем читать дальше.

Запись А^В означает оператор присваивания, т. е. переменной А присваивается текущее значение В.

Algorithm МАХ. Даны N действительных чисел в одномерном массиве R(1), R(2),..., R(N), найти такие М и J, что

М =R (J) = шах R(K).

1 < K<N

В случае когда два или более элементов R имеют наибольшее значение, запоминается наименьшее значение J.

Шаг 0. [Установка в начальное состояние, или инициализация]

Set M<-R (1); and

Уч-1. Шаг 1. [N= 1?] If N=l then STOP fi ^l).

Ч В этом алгоритме fi и od используются соответственно для обозначения кон­ца конструкций if и do. Более детально это будет обсуждаться в разд. 2.1,

Шаг 2. {Проверка каждого числа] For К-+-2 to N do шаг 3 od; and STOP.

Шаг 3. [Сравнение] If M<CR(/()then set M+-R(K); and fi (теперь M •— наибольшее число из прове­ренных, а К — его номер в массиве).

Алгоритм МАХ не закодирован на каком-то языке, а записан в форме, которую легче воспринять; он выражен в виде шагов, кото­рые легко реализуются в каждом общепринятом языке программиро­вания. От такого представления нетрудно перейти к кодовой форме. Однако так бывает не всегда. Некоторые алгоритмы слишком сложны, чтобы перейти за один шаг от предварительного словесного описания к кодам машины. Может потребоваться ввести по крайней мере один промежуточный этап разработки.

1.3. Основные этапы полного построения алгоритма

Теперь мы кратко рассмотрим основные этапы, перечисленные в конце разд. 1.1. Прежде всего определим назначение каждого этапа и выясним, как эти этапы объединяются в единое целое. Постановка задачи

Прежде чем мы сможем понять задачу, мы должны ее точно сфор­мулировать. Это условие само по себе не является достаточным для понимания задачи, но оно абсолютно необходимо.

Обычно процесс точной формулировки задачи сводится к поста­новке правильных вопросов. Перечислим некоторые полезные воп­росы для плохо сформулированных задач:

Понятна ли терминология, используемая в предварительной фор­мулировке?

Что дано?

Что нужно найти?

Как определить решение?

Каких данных не хватает и все ли они нужны?

Являются ли какие-то имеющиеся данные бесполезными?

Какие сделаны допущения?

Возможны и другие вопросы в зависимости от конкретной задачи. Часто после получения полных или частичных ответов на некоторые из вопросов их приходится ставить повторно.

Пример. Джек — агент но продаже компьютеров (коммивояжер); на его территории 20 городов, разбросанных по всему Техасу. Компа­ния возмещает ему только 50% стоимости деловых автомобильных поездок. Джек вычислил, сколько ему будет стоить переезд на машине между каждыми двумя городами на его территории. Ему, естественно, хотелось бы снизить свои дорожные расходы.

Что дано? Исходная информация задана в виде перечня городов на территории Джека и соответствующей матрицы стоимостей, т. е. двумерного массива с элементами c_tj, равными стоимости переезда из города i в город /. В данном случае матрица стоимостей имеет 20 строк и 20 столбцов.

Что мы хотим найти? Мы хотим помочь Джеку снизить его дорож­ные расходы. Это звучит несколько туманно. Действительно, вопрос о том, каким будет решение, выглядит неуместным. Обдумав ситуа­цию, мы придем к выводу, что ничего не можем сделать без дополни­тельной информации от Джека. Имеет ли Джек в одних городах боль­ше покупателей, чем в других? Если да или если есть какие-то особые покупатели, то Джек, возможно, захочет посещать какие-то города чаще. Могут быть и такие города, в которые Джек специально не поедет, а заедет туда, когда окажется в соседнем городе. Другими словами, нам надо знать больше о приоритетах Джека и учитывать предпочтения при составлении графика поездок.

Поэтому мы возвращаемся к Джеку и требуем у него дополнитель­ную информацию. Он сообщает, что хотел бы иметь маршрут, начи­нающийся и оканчивающийся в его базовом городе и проходящий по одному разу через все остальные города на его территории. Следо­вательно, нам требуется список городов, содержащий каждый город только один раз, за исключением базового города, который стоит в списке первым и последним. Порядок городов в этом списке пред­ставляет собой маршрут, по которому Джек должен объезжать города па своей территории. Сумма стоимостей проезда между каждыми двумя последовательными городами списка -— это общая стоимость маршрута, представленного списком. Мы решим задачу Джека, если представим ему список с наименьшей возможной общей стоимостью. Это хорошая исходная постановка задачи. Мы знаем, что мы имеем и что хотим найти.