Является ли преобразование алгоритма максимизации в минимизацию вопросом изменения max на min?

Question

Это может показаться глупым вопросом, но мне любопытно узнать, если дать алгоритм максимизации и попросить получить двойное (версия минимизации), это просто вопрос преобразования всех максимумов в минимумы и выполнения других базовых настроек?

Если да, есть ли проблемы, когда это не так?Если нет, есть ли хорошая интуитивная причина, почему это не работает?

Answer 1

Да, проблемы максимизации и минимизации в основном одинаковы. Решение для max(f(x)) такое же, как -min(-f(x)).

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

Answer 2

Это зависит от того, как работает ваш алгоритм максимизации.Численные алгоритмы, которым нужны градиенты, вероятно, будут делать больше, чем max и min, и могут возникнуть другие сложности.

Однако, действительно, это очень легко исправить.Максимизация функции f(a,b,c) эквивалентна минимизации -f(a,b,c).Так что просто отмените результат функции.

Answer 3

Работает, если задача явно симметрична, как поиск максимума или минимума на 2D-поверхности.Тем не менее, поскольку вы цитируете задачу о ранце: это целый другой класс проблем, оптимум не может быть найден путем жадного применения некоторой функции max () к вектору.