Я читаю tutorial о "жадных" алгоритмах, но мне сложно определить их реальные проблемы с "Top Coder".
Если я знаю, что данная проблема может быть решена с помощью "жадного" алгоритма, довольно легко закодировать решение. Однако, если мне не говорят, что эта проблема "жадная", я не могу ее заметить.
Каковы общие свойства и модели проблем, решаемых с помощью "жадных" алгоритмов? Могу ли я свести их к одной из известных "жадных" проблем (например, MST)?
Формально вам, конечно, нужно будет доказать матроидное свойство. Тем не менее, я предполагаю, что с точки зрения topcoder вы скорее захотите быстро узнать, если к проблеме можно обратиться с жадностью или нет.
В этом случае наиболее важным является свойство оптимальной субструктуры. Для этого вы должны уметь определить, что проблема может быть разложена на подзадачи и что их оптимальное решение является частью оптимального решения всей проблемы.
Конечно, жадные проблемы приходят в таком широком разнообразии, что почти невозможно предложить общий правильный ответ на ваш вопрос. Поэтому мой лучший совет - подумать где-то по этим строкам:
Вместе с нагрузками и опытом (просто нужно было сказать это тоже) это должно помочь вам быстро выявить жадные проблемы. Конечно, вы можете в конечном итоге классифицировать проблему как жадную, а это не так. В этом случае вы можете только надеяться на это, прежде чем работать над кодом слишком долго.
(Опять же, для справки, я предполагаю контекст topcoder.. для чего-либо более реалистичного и практического результата я настоятельно рекомендую фактически проверить структуру матроида перед выбором жадного алгоритма.)
Часть вашей проблемы может быть вызвана мышлением о "жадных проблемах". Есть жадные алгоритмы и проблемы, где есть жадный алгоритм, который приводит к оптимальному решению. Существуют и другие серьезные проблемы, которые также могут быть решены жадными алгоритмами, но результат не обязательно будет оптимальным.
Например, для проблемы с упаковкой ящиков есть несколько жадных алгоритмов, все из которых с гораздо большей степенью сложности, чем экспоненциальный алгоритм, но вы можете быть уверены, что получите решение, которое ниже определенного порога по сравнению с оптимальное решение.
Только в тех случаях, когда жадные алгоритмы приведут к оптимальному решению, я предполагаю, что доказательство индуктивной корректности кажется абсолютно естественным и легким. Для каждого из ваших жадных шагов совершенно ясно, что это было лучше всего.
Обычно проблемы с оптимальными, жадными решениями в любом случае легки, а другие заставляют вас придумывать жадные эвристики из-за ограничений сложности. Обычно значимое сокращение будет показывать, что ваша проблема на самом деле по крайней мере NP-hard, и, следовательно, вы знаете, что вам нужно будет найти эвристику. Для этих проблем я большой поклонник опробовать. Реализуйте свой алгоритм и попытайтесь выяснить, являются ли решения "довольно хорошими" (идеально, если у вас также есть медленный, но правильный алгоритм, с которым вы можете сравнивать результаты, в противном случае вам могут понадобиться вручную созданные истины). Только если у вас есть что-то, что хорошо работает, попробуйте подумать, почему и, возможно, даже попытаться найти доказательство границ. Возможно, это работает, возможно, вы обнаружите пограничные случаи, когда они не работают и нуждаются в уточнении.
"Термин, используемый для описания семейства алгоритмов. Большинство алгоритмов пытаются достичь некоторой" хорошей "конфигурации из некоторой начальной конфигурации, делая только легальные действия. Часто существует некоторая мера" доброты "решения (если предположить, что найденный). Жадный алгоритм всегда пытается выполнить лучший законный ход, который он может сделать. Обратите внимание, что этот критерий является локальным: жадный алгоритм не "задумывается", соглашаясь выполнить какое-то посредственно выглядящее движение сейчас, что позволит лучше двигаться дальше.
Например, жадный алгоритм для египетских фракций пытается найти представление с малыми знаменателями. Вместо того, чтобы искать представление, где последний знаменатель мал, он принимает на каждом шаге наименьший юридический знаменатель. В общем, это приводит к очень большим знаменателям на последующих этапах.
Основным преимуществом жадного алгоритма обычно является простота анализа. Это также очень легко программировать. К сожалению, он часто не оптимален ". --- ariels (Http://www.everything2.com/title/greedy+algorithm?searchy=search)