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

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

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

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

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

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

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

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

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

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

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

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