Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Дисциплины:
2017-06-26 | 619 |
5.00
из
|
Заказать работу |
|
|
Существует три основных метода разработки алгоритмов:
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!