Блог пользователя vitar

Автор vitar, 12 лет назад, По-русски

Мы с Milanin временами любим поспорить на тему отличия жадности и динамики. Он предпочитает большинство жадностей считать динамикой, я нет.

Что у них общего? И у того и у другого подхода решение задачи получается в результате множества этапов на каждом из которых мы получаем оптимальный ответ для какого-то состояния исходя из некоторых уже полученных оптимальных ответов для других состояний.

Что различного? В случае с динамикой мы фиксируем текущее состояние, для которого уже знаем оптимальный ответ, и рассматриваем ВСЕ способы достичь следующее. Необходимым условием является то, что следующее состояние должно быть достижимо только из уже посчитанных. Возможно на этом этапе используется жадность для того, что бы отсечь некоторые заведомо не оптимальные переходы.

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

Для примера рассмотрим кратчайший путь во взвешенном ориентированном графе. А именно вот в этом:

Из вершины 1 в вершину 3.

Эту задачу можно решать как дейкстрой так и динамикой. При этом дейкстра будет жадностью. Так как на каждом шаге у нас есть множество всевозможных переходов и мы не задумываясь ни о чём выбираем самый дешёвый (с учётом расстояния до вершины из которой он исходит). Мы совершенно не представляем куда можем попасть и у нас нет никаких ограничений, кроме существования перехода. Когда мы этот переход нашли, остальные нас уже не волнуют.

Если же решать задачу динамикой, то, считая ответ для вершины 3, нам необходимо уже знать ответ для вершины 2, и нам обязательно рассмотреть все способы в текущую вершину войти. В то время как жадность позволяет узнать ответ для 3, не зная ещё ответ для 2. Хотя и имея некоторые представления о нём. Для динамики обычно заранее известен порядок рассмотра вершин. Для ориентированного графа — одна из топологических сортировок. В то время как для жадности порядок рассмотра определяется самой жадностью. По крайней мере на него нельзя заранее наложить ограничения не диктуемые свойствами самой жадности.

Жадность позволяет вообще пропустить некоторые промежуточные состояния. Иногда это очень эффективно. Динамика рассматривает все возможные состояния и все возможные переходы между ними (возможно с некоторыми жадными отсечениями). Обычно это позволяет найти ответ для более широкого класса задач.

Буду рад комментариям на эту тему.

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится -46 Проголосовать: не нравится

Но, так или иначе, в основе любой динамики лежит жадная идея. Поясню. В динамике мы выбираем состояние и переходим дальше. А что такое состояние? Нужно доказать что состояние определяется только теми параметрами которые мы поставили в динамику, что нет зависимости от предыдущих состояний. Иными словами, почему наша жадность работает. Конкретный пример, задача о гамильтоновом пути или гамильтоновом цикле. Почему, перебирая маску, нас не интересует полный порядок вершин, а лишь последняя из посещенных? Нужно доказать, что жадная в своей сути идея — рассматривать только последнюю вершину из всех, которые мы посетили — правильна в своей сути. Да, доказательство тривиально. Но в сути этой динамики все равно лежит жадная идея, которую так или иначе нужно доказать. В основном, для большинства динамик, это, конечно, тривиально. Но нужно.

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

На мой взгляд не существует четких границ. Твои доводы нахожу разумными, но вот для моего мозга Дейкстра видится в большей степени динамикой чем жадностью. Спорить в этой ситуации считаю так же глупо, как спорить о том какая же зебра, она черно-белая или бело-черная.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

Ну еще возражу вот на это "Для динамики обычно заранее известен порядок рассмотра вершин" на то она и динамика, что это делается "динамически", онлайн. Я стартанул из вершины, а какие там дальше будут вершины сколько, какие и куда будут ребра мы пока не знаем, это зависит от множества факторов, и от передаваемых параметров тоже (от битмасок например). Для меня жадина это что-то более прямолинейное типа "возьмем самую большую конфету и дадим её самому маленькому ребенку", при этом это действие какбы уже никогда не отменить, можно в аутпут выводить сразу. А в динамике нет, пришли в вершину 3 из 2 с суммой 20, не факт еще что это конечный ответ, дальше считаем.

»
12 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Мне только что вспомнились те постулаты ДП, про которые говорил Станкевич в своей лекции, так вот, по-моему, из них вытекает, что все жадности можно назвать динамиками. Во всяком случае, на примере алгоритма Радо-Эдмондса (то, что он является жадным, я так думаю, ни у кого сомнения не вызывает), все три постулата выполняются:

  1. Рекуррентная последовательность: для данного линейно независимого множества сумма весов будет равна весу наименьшего элемента плюс вес множества, полученного из данного путем удаления этого самого наименьшего элемента.
  2. Порядок вычисления: от пустого множества к какому-либо произвольному максимальному линейно независимому множеству с добавлением на каждом шаге элемента с наибольшим весом среди тех, что не нарушают линейную независимость.
  3. Поиск ответа: ответ будет сохранен в некой заранее созданной переменной, хранящей сумму весов элементов множества.

P.S. ИМХО, пример абсурдный, как и сама идея спора.