Жадные алгоритмы

[Arion]

день алгоритмов на хабре, спасибо за статью

[Rustam]

студенты готовятся к экзаменам

[Neofant]

У роботов-продавцов точно будет устанавливаться такой алгоритм :) Спасибо вам за полезную информацию.

[Bashuk]

Неплохо было бы еще привести пример, в котором очевидная жадность не является правильным решением (к примеру, задача о рюкзаке).
В целом — отличная статья, спасибо.

[NeoNN]

Для рюкзака есть эвристика, дающая доказанную эффективность максимум 11/9 от оптимального результата, только вот является ли она жадным алгоритмом?

[Scorpil]

Торт!

[Throwable]

Помню в свое время на российской олимпиаде по информатике было задание запрограммировать игру Filler. Среди тестов были тесты на жадность, поэтому жадные программы (т.е. на каждом ходу «присоединяющие» максимальное количество квадратов) получали только половину баллов. Максимальное количество баллов получали те программы, которые учитывали поведение соперника и избирали ту или иную стратегию: если не успевают добраться до «куша» раньше соперника, то начинают есть жадно все, что вокруг.

[Rustam]

Вот пример задачи, где не срабатывает жадность и даже рекурсивный перебор.

[pomkaster]

«Если множества A и B принадлежат множеству I, а также известно, что размер А меньше B, то существует какой-нибудь элемент из B, не принадлежащий А, который будет принадлежать множеству I.» — меня как-то смутила эта фраза. Всё-таки принадлежать множеству I будет не сам элемент (назовём x), а Union[A,{x}]. В формуле всё верно, а вот расшифрофку стоит подправить на мой взгляд.
А статья классная, да.

[Rustam]

О да, это точно. В противном случае каждая вторая NP-полная задача решалась бы перебором.

Спасибо, исправил!

[Pastafarianist]

Сам по себе жадный алгоритм имплементится примерно вот так

имплементится

Я, конечно, не то чтобы борец за чистоту русского языка, но ЭТО…

[mktums]

Ой, да ладно вам, мы тут суржик читаем и не ругаемся, а вы к слэнгу прицепились =)

[Rustam]

буквально вчера я сдавал перевод по английскому языку и препод удивлялась, почему я никак не хочу переводить слово «Random».

За сленг извините, исправил.

[Meroving]

Странно, что вы отнесли алгоритм Дейкстры к жадным. Это тоже пример реализации метода динамического программирования и практически прямого использования уравнения Беллмана.

[Meroving]

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

[WingedFlame]

Спасибо за статью :) Вспомнились мои олимпиады по программированию, когда судорожно решал — писать за 10 минут жадное решение и приступать к другим задачам, либо додумывать правильное решение и писать его непонятно сколько времени =)

[SeptiM]

Жизнь, матроиды, конечные автоматы… ИТМО какое-то.