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

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

«Исчерпывающий алгоритм» решения задачи коммивояжера

Произвольно пронумеруем города целыми числами от 1 до n. Базовому городу припишем номер n. Таким образом, каждый гамильтонов цикл однозначно соответствует перестановке целых чисел:

n 1, 2, 3, … n-1, n

n n-5, 2, 3, …, n-1, n-2 n и др.

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

Исчерпывающий алгоритм (ETS):

1. Образуем перестановки первых n-1 чисел

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

3. Выбираем перестановку, строим соостветствующий путь и вычисляем его стоимость.

4. Сравниваем стоимость текущего пути с минимальной. Запоминаем минимальную из них. Возвращаемся к шагу 3.

Такой алгоритм называется исчерпывающим или переборным алгоритмом.

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

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

Методика доказательства правильности алгоритма.

Предположим, что алгоритм описан в виде последовательности шагов: от шага 1 до шага n.

1. Предложим обоснование правомерности каждого шага (выделение инварианта).

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

Доказательство для алгоритма «задачи коммивояжера».

1. Проверяется каждый цикл.

2. При этом будет проверен и цикл с минимальной стоимостью; он будет запомнен (не потеряем).

3. Этот путь будет отброшен только в том случае, если существует путь с меньшей стоимостью.

4. Алгоритм должен закончить работу, так как число путей, которые нужно проверить, конечно: (n-1)!

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

Реализация алгоритма в виде программы для эвм

На этом этапе следует ответить на вопросы:

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

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

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

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

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

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

Пункты 1-4 - построение структур данных.

Пункты 5-6 – непосредственное использование языка программирования.

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

Другой аспект построения программной реализации - это программирование "сверху - вниз".

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