Помощь      Поиск      Участники      Календарь      Новости
 Учебные Материалы      ВАЛтест     Фотогалерея Фотогалерея
 Правила форума      Виртуальные тренажеры      Мемуары


  Reply to this topicStart new topicStart Poll

> Жадный алгоритм (поиска) (Википедия)
Подписка на тему | Сообщить другу | Версия для печати
VAL
Дата 9.03.2019 09:01
Quote Post
Offline



Мэтр, проФАН любви... proFAN of love
*****

Профиль
Группа: Администраторы
Сообщений: 38059
Пользователь №: 1
Регистрация: 6.03.2004
Жадный алгоритм (поиска) (Википедия)
Источник: https://ru.wikipedia.org/wiki/%D0%96%D0%B0%...%B8%D1%82%D0%BC

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

Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование. 


QUOTE
Выбор заявок

Формулировка № 1. Даны n {\displaystyle n} n заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ( s i {\displaystyle s_{i}} s_{i} и f i {\displaystyle f_{i}} f_{i} для i {\displaystyle i} i-й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами i {\displaystyle i} i и j {\displaystyle j} j совместны, если интервалы [ s i , f i ) {\displaystyle [s_{i},f_{i})} [s_{i},f_{i}) и [ s j , f j ) {\displaystyle [s_{j},f_{j})} [s_{j},f_{j}) не пересекаются (то есть f i ≤ s j {\displaystyle f_{i}\leq s_{j}} f_{i}\leq s_{j} или f j ≤ s i {\displaystyle f_{j}\leq s_{i}} f_{j}\leq s_{i}). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Формулировка № 2. На конференции, чтобы отвести больше времени на неформальное общение, различные секции разнесли по разным аудиториям. Учёный с чрезвычайно широкими интересами хочет посетить несколько докладов, проходящих в разных секциях. Известно начало s i {\displaystyle s_{i}} s_{i} и конец f i {\displaystyle f_{i}} f_{i} каждого доклада. Определить, какое максимальное количество докладов можно посетить.

Приведём жадный алгоритм, решающий данную задачу. При этом полагаем, что заявки упорядочены в порядке возрастания времени окончания. Если это не так, то можно отсортировать их за время O ( n log ⁡ n ) {\displaystyle O(n\log n)} O(n\log n); заявки с одинаковым временем конца располагаем в произвольном порядке. 


ЗЫ. Смю: презентацию
QUOTE
!Greedy search

"A greedy search algorithm is an algorithm that uses a heuristic for making locally optimal choices at each stage with the hope of finding a global optimum. 

"No backtracking!
•No reevaluating choices that the algorithm committed to earlier. 


--------------------
www.valinfo.ru
Всегда... Always....
Quod licet jovi, non licet bovi!
PMEmail PosterUsers Website
Top
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Программное обеспечение. Data и text mining | Следующая тема »

Topic Options Reply to this topicStart new topicStart Poll

 

Powered by Invision Power Board(U) v1.3 Final © 2003  IPS, Inc.
Установка, модификация и поддержка:
Barsum | 1px Design Group & Xac | OппаRU форум