1.1.4. Виды алгоритмов

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

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

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

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

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

20