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

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

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

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

2017-06-26 628
Методы разработки алгоритмов 0.00 из 5.00 0 оценок
Заказать работу

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

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

2) подъема

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

 

 

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

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

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

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

 

 

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

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

 

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

 

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

 

Пример:

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

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

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

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

 

 

 

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

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

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

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

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

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

 

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

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

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

 

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

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

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

Пример:

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

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

 

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

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

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

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

 

 


Поделиться с друзьями:

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

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой...

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



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.006 с.