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

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

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

2) подъема

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

 

 

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

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

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

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

 

 

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

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

 

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

 

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

 

Пример:

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

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

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

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

 

 

 

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

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

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

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

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

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

 

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

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

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

 

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

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

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

Пример:

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

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

 

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

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

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

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