Как почувствовать жадный алгоритм в задаче?

Revision ru3, by DJiGIT, 2017-10-15 19:55:54

Решаю-решаю я задачу, перебераю все методы которые могли бы быть в качестве решения, а что в итоге — забил я на свои мысли, пошел читать разбор и что я вижу — #ЖАДНЫЕ АЛГОРИТМЫ (оу щет). Читаю разбор: ну вроде все логично и понятно, но как, почему??? Начал гуглить что то вроде: "жадные алгоритмы и их методы решений", "как увидить жадину", "жадина, ты где?". В результате я нашел такую штуку, как Матроид и даже пример доказательства конкретной задачки на хабре. Но, чесно говоря, не совсем понял как это доказывать:

1) если 1, 2, 4 — успешно выполненные задания, то I = {{null}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} или другое множество? 2) стоит ли рассматривать все возможные комбинации успешно выполненых заданий или достаточно одной ?).

А вобщем, у меня вопрос следующий: если я хочу решить задачу жадиной, нужно мне расписовать этот матроид и проверять выполняються ли свойства матроида или чувство жадины должно прийти с опытом?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian DJiGIT 2017-10-15 19:55:54 1
ru2 Russian DJiGIT 2017-10-15 19:54:17 4
ru1 Russian DJiGIT 2017-10-15 19:47:43 1053 Первая редакция (опубликовано)