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