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

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

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

Следует отметить, что алгоритмы характеризуются пятью характеристиками:

1. Вход алгоритма.

2. Выход алгоритма

3. Определенность.

4. Выполнимость.

5. Конечность.

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

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

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

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

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

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

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

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

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

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

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

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

TOUR=0; МIN=Ґ.

Шаг 1. [Образование всех перестановок]

For I=1 to (N—1)

Шаг 2. [Получение новой перестановки]

P=I-я перестановка целых чисел 1, 2,..., N— 1.

(Заметим, что здесь нужен подалгоритм.)

Шаг 3. [Построение нового тура]

Строим тур Т(Р), соот­ветствующий перестановке Р и вычисляем стои­мость COST (Т (Р)). (Заметим, что здесь нужны два других подалгоритма.)

Шаг 4. [Сравнение]

If COST (Т(P))<MIN then TOUR= T(P), and MIN=COST(r(P)).

Ш аг 5 [ Вывод результатов и окончание программы]

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

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