Книга является наиболее полным руководством по разработке эффективных ал

Глава 1. Введение в разработку алгоритмов 
31 
П
ОДВЕДЕНИЕ ИТОГОВ
В основе любого алгоритма лежит 
идея
.
Если в описании алгоритма не просматривается 
ясно ваша идея, значит, вы используете для ее выражения нотацию слишком низкого 
уровня. 
1.3.2. Задачи и свойства 
Чтобы продемонстрировать правильность алгоритма, одного его описания недостаточ-
но. Нам также нужно подробное описание задачи, которая подлежит решению. 
Постановка задачи состоит из двух частей: набора допустимых входных экземпляров и 
требований к выходу алгоритма. Невозможно доказать правильность алгоритма для 
нечетко поставленной задачи. Иными словами, поставьте неправильно задачу, и вы 
получите неправильный ответ. 
Постановки некоторых задач допускают слишком широкий диапазон входных экземп-
ляров. Допустим, что в нашей задаче календарного планирования съемки фильмов мо-
гут прерываться на некоторое время. Например, съемки фильма могут быть запланиро-
ваны на сентябрь и ноябрь, а октябрь свободен. Тогда календарный план съемок для 
любого фильма будет состоять из 
набора
временных интервалов. В этом случае мы 
можем браться за роли в двух фильмах с чередующимися, но не пересекающимися
периодами съемок. Такую общую задачу календарного планирования нельзя решить
с помощью алгоритма самого раннего окончания съемок. Более того, для решения этой 
общей задачи вообще 
не существует
эффективного алгоритма. 
П
ОДВЕДЕНИЕ ИТОГОВ
Важным и заслуживающим внимания приемом разработки алгоритмов является сужение 
множества допустимых экземпляров задачи до тех пор, пока не будет найден правильный 
и эффективный алгоритм. Например, задачу общих графов можно свести к задаче деревь-
ев, или двумерную геометрическую задачу свести к одномерной. 
При указании требований выхода алгоритма часто допускаются две ошибки. Первая из 
них — плохая формулировка вопроса. Примером может служить вопрос о 
наилучшем
маршруте между двумя точками на карте при отсутствии определения, что значит 
"наилучший". Лучший в каком смысле? В смысле самого короткого расстояния, самого 
короткого времени прохождения или, может быть, минимального количества пово- 
ротов? 
Второй ошибкой является формулирование составных целей. Каждый из трех только 
что упомянутых критериев наилучшего маршрута является четко определенной целью 
правильного эффективного алгоритма оптимизации. Но в качестве требования к реше-
нию из этих критериев можно выбрать только один. Например, формулировка: "Найти 
самый короткий маршрут от точки к точке, содержащий количество поворотов не бо-
лее чем в два раза превышающее необходимое" является вполне четкой постановкой 
задачи. Но решить такую задачу очень трудно, т. к. решение требует сложного анализа. 
Для примеров постановки задач читателю настоятельно рекомендуется ознакомиться
с постановкой каждой из 75 задач во второй части этой книги. Правильная постановка 
задачи является важной частью ее решения. Изучение постановок всех этих классиче-
ских задач поможет вам распознать задачи, постановкой и решением которых кто-то 
уже занимался до вас. 

---

32