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

Существует три основных метода разработки алгоритмов:

1) частных целей

2) подъема

3) отрабатывания назад

Метод частных целей

Метод частных целей основан на сведении трудной задачи к последовательности простых задач. Но и как большинство других методов его не всегда легко перенести на конкретную задачу.

Осмысленный выбор более простых задач: дело искусства, а не интуиции.

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

Метод подъема

Алгоритм начинается с принятия начального предположения или вычисления начального значения задачи. Затем переходим от начального значения к лучшему. Когда алгоритм достигает точки из которой нельзя перейти, он останавливается.

Метод отработки назад

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

Пример:

Подойдем к задаче с помощью метода отрабатывания назад. На основании этого метода мы задаемся целью (вопросом): с какого расстояния мы можем пересечь пустыню имея запас горючего точно для k баков.

k=1,2,3…n пока не найдем такое целое n, что позволяет пройти весь путь 1000км.

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

На первый вопрос ответить можно лишь тогда , когда ответ на второй вопрос будет не меньше 1000л.

Эвристики (гипотезы)

Эврист алгоритм определяющийся, как алгоритм со следующими свойствами:

1) обычно находит хорошие, но не обязательно оптимальные решения

2) его можно быстрее и проще реализовать, чем любой известный точный алгоритм

3) не существует задачи, которой нельзя описать эвристическим алгоритмом.

(многие основаны на методе частных целей и методе подъема)

Общий подход к построению эвристического алгоритма заключается в перечислении требований к общему решению и разделяется на два класса:

1) легко удовлетворять

2) не так легко удовлетворять

1) должны быть удовлетворены

2) те, по отношению к которым можно пойти на компромисс

Цель: Создать алгоритм, удовлетворяющий первые требования, но не обязательно вторые.

Пример:

13- оптимальных проходов 14-оптимальных проходов

В этом алгоритме реализована идея подъема, однако задача сведена к набору частных целей: найти на каждом шаге самый «дешевый» город.

Оптимальное решение имеет два свойства:

1) состоит из множества ребер, вместе представляющих тур (5 ребер)

(его гарантируем)

2) Стоимость никакого Другова не будет меньше заданного (идем на компромисс)