чае зависят от реализации; характеристика 0{п) обычно свойственна алгоритму, т. е. не зависит от различных особенностей реализации.

Важно также знать, насколько плохо работает экспоненциальный алгоритм. Существует много важных задач, для которых в настоящее время известны только экспоненциальные алгоритмы. Одна из них - задача коммивояжера, другие описаны в разных разделах книги. Эти задачи необходимо решать ввиду их практической значимости. Раз уж известны только экспоненциальные алгоритмы, то хотелосьбы пользоваться наиболее эффективными из них. Очевидно, что алгоритм, решающий задачу размерности п за 0(2") шагов, предпочтительнее алгоритма, решающего ее за 0{п\) или 0{п") шагов.

Пример. Рассмотрим ранее описанный алгоритм ETS. Сразу можно сделать вывод, что это экспоненциальный алгоритм с оценкой по крайней мере 0{п\). В задаче с п городами алгоритм ETS требует от нас исчерпывающе перечислить перестановки первых п-1 положительных целых чисел. Число таких перестановок (п-1)!. Даже если требуется только один шаг для каждой такой перестановки (грубая недооценка - см. упр. 1.3.5), эта часть алгоритма все же потребует 0[п-1)!]шагов. Как только представлена перестановка, как в шаге 1 алгоритма ETS, можно найти соответствующий тур и его стоимость за О (л) шагов (см. упр. 1.3.6). Поэтому любая верхняя граница для общего времени работы должна быть по крайней мере 0{п\).

Предположим, что у нашего коммивояжера 20 городов и что у нас есть феноменальный подалгоритм алгоритма ETS для шага 1, который генерирует новую перестановку только за один шаг. Предположим также, что мы имеем быстродействующую машину, которая выполняет каждый элементарный шаг (например, сравнение, сложение, поиск элемента матрицы) за 10" с. Тогда, так как 20!л:;2-10, решение нашей задачи с использованием алгоритма ETS займет немногим меньше 70 веков.

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

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

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

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

Проверка программы

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

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

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

Как выбрать входные данные для тестирования? На этот вопрос невозможно дать общего ответа. Для любого алгоритма ответ зависит от сложности программы, имеющегося ресурса времени, а также от персонала, занимающегося проверкой, числа вводов (т. е. вариантов входных данных), для которых можно установить правильность выводов, и т. д. Обычно множество всех вводов огромно, и полная проверка практически невозможна. Мы должны выбрать множество вводов, которые проверяют каждый участок программы. Надо обяза-

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

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

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

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

Программы следует тестировать также для того, чтобы определить их вычислительные ограничения. Многие программы для некоторых входных данных работают хорошо, а для других плохо. Желательно, чтобы характеристика работы алгоритма «плавно» менялась от хорошей к плохой при переходе от входных данных, на которых алгоритм хорошо работает, к входным данным, для которых это не так. Алгоритм ETS хорошо работает для п<6 и очень плохо для п15. К сожалению, в данном случае переход не плавный, и алгоритм имеет тенденцию плохо работать в промежуточных случаях. Желательно пользоваться как аналитическими, так и экспериментальными методами, чтобы охарактеризовать те входные данные, которые считаются или «хорошими», или «плохими». Например, предположим, что у нас есть алгоритм, который в худшем случае имеет трудоемкость 0{п\), а его средняя трудоемкость 0{п?). Было бы очень удобно, если бы мы могли охарактеризовать входные данные для нашего алгоритма другим параметром а, а затем установить, какие комбинации (п, а) требуют экспоненциального времени работы, а для каких комбинаций задача может быть решена за полиномиальное время. Ясно, что если средняя характеристика - порядка О (п), то должно быть меньше вводов, требующих экспоненциального времени. Если бы эти вводы можно