Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Каждый, кто занимается разработкой алгоритмов, должен овладеть некоторыми основными методами и понятиями. Всем когда-то впервые пришлось столкнуться с трудной задачей, задать вопрос: с чего начать? Один из возможных путей — просмотреть свой запас общих алгоритмических методов для того, чтобы проверить, нельзя ли с помощью одного из них сформулировать решение новой задачи.
Ну, а если такого запаса нет, то как все-таки разработать хороший алгоритм? С чего начать? У всех есть печальный опыт, когда смотришь на задачу и не знаешь, что делать. Рассмотрим три общих метода решения задач, полезных для разработки алгоритмов.
Первый метод связан со сведением трудной задачи к последовательности более простых задач. Конечно, мы надеемся на то, что более простые задачи легче поддаются обработке, чем первоначальная задача, а также на то, что решение первоначальной задачи может быть получено из решений этих более простых задач. Такая процедура называется методом частных целей.
Этот метод выглядит очень разумно. Но, как и большинство общих методов решения задач или разработки алгоритмов, его не всегда легко перенести на конкретную задачу. Осмысленный выбор более простых задач — скорее, искусство или интуиция, чем наука. Более того, не существует общего набора правил для определения класса задач, которые можно решать с помощью такого подхода.
Второй метод разработки алгоритмов известен как метод подъема. Алгоритм подъема начинается с принятия начального предположения или вычисления начального решения задачи. Затем начинается насколько возможно быстрое движение «вверх» от начального решения по направлению к лучшим решениям. Когда алгоритм достигнет такой точки, из которой больше невозможно двигаться наверх, алгоритм останавливается. К сожалению, мы не можем всегда гарантировать, что окончательное решение, полученное с помощью алгоритма подъема, будет оптимальным. Эта ситуация часто ограничивает применение метода подъема.
Вообще методы подъема являются «грубыми». Они запоминают некоторую цель и стараются сделать все, что могут и где могут, чтобы подойти ближе к цели. Это делает их несколько недальновидными. Недальновидность метода подъема хорошо иллюстрируется следующим примером. Пусть требуется найти максимум функции у= f(x), представленной графиком (рис. 1.24).
Если начальное значение аргумента х равно а, то метод подъема даст устремление к ближайшей цели, т. е. к значению функции в точке х=b, тогда как подлинный максимум этой функции находится при х=с. То есть метод подъема в данном примере находит максимум, но не тот. В этом и заключается «грубость» метода подъема.
Третий метод известен как отрабатывание назад, т. е. работа алгоритма начинается с решения задачи, и затем осуществляется движение к начальной постановке задачи. Затем, если эти действия обратимы, производится движение обратно — от постановки задачи к решению.
Дата публикования: 2015-09-18; Прочитано: 1918 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!