Глава 3. Методы разработки алгоритмов

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

В разд. 3.1 содержится краткое описание трех основных методов решения задач. По крайней мере один из этих методов в некотором смысле лежит в основе многих процедур и алгоритмов, обсуждаемых в последующих главах книги. В разд. 3.3 и 3.4 рассмотрены два общих метода решения больших комбинаторных задач - метод отхода и метод ветвей и границ. Рекурсия, инструмент, который может в значительной степени упростить логическую структуру многих алгоритмов, представлена в разд. 3.5. В разд. 3.2 и 3.6 изучаются два широко используемых «житейских» метода: эвристика и имитация. Видимо, в больших, сложных прикладных программах эти два метода используются чаще, чем все остальные вместе взятые.

3.1. Методы частных целей, подъема и отрабатывания назад

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

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

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

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

1. Можем ли мы решить часть задачи? Можно ли, игнорируя некоторые условия, решить оставшуюся часть задачи?

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

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

4. Встречались ли мы с похожей задачей, решение которой известно? Л1ожно ли видоизменить ее решение для решения нашей задачи? Возможно ли, что эта задача эквивалентна известной нерешенной задаче?

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

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

Название «подъем» отчасти происходит от алгоритмов нахождения максимумов функций нескольких переменных. Предположим, что / {х, у) - функция переменных х и у и задача состоит в нахождении максимального значения f. Функция f может быть представлена поверхностью (имеющей холмы и впадины) над плоскостью ху, как на рис. 3.1.1. Алгоритм подъема может начать работу в любой точке Zg этой поверхности и проделать путь вверх к вершине в точке zi. Это значение является «локальным» максимумом в отличие от «глобального» максимума, и метод подъема не дает оптимального решения.

Вообще методы подъема являются «грубыми». Они запоминают не-

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

Как показывает наш пример, алгоритмы подъема могут быть полезны, если нужно быстро получить приближенное решение. Этот вопрос будет исследован дальше в разд. 3.2.

Третий метод, рассматриваемый в этом разделе, известен как

Рис. 3.1.1. Подъем к локальному максимуму.

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

Давайте постараемся применить все три метода этого раздела в довольно трудном примере.

Задача о джипе

Мы хотели бы пересечь на джипе 1000-мильную пустыню, израсходовав при этом минимум горючего. Объем топливного бака джипа 500 галлонов, горючее расходуется равномерно, по 1 галлону на милю. В точке старта имеется неограниченный резервуар с топливом. Так как в пустьше нет складов горючего, мы должны установить свои собственные хранилища и наполнить их топливом из бака машины. Где расположить эти хранилища? Сколько горючего нужно залить в каждое из них?

Подойдем к этой задаче с помощью метода отрабатывания назад. С какого расстояния от конца мы сможем пересечь пустыню, имея запас горючего в точности на k баков? Мы будем задавать этот вопрос для k=\, 2, 3, . . . , пока не найдем такое целое п, что п полных баков позволят пересечь всю 1000-мильную пустыню.