¿Convertir un algoritmo de maximización en una minimización es una cuestión de cambiar de máximo a mínimo?

Esto podría parecer una pregunta tonta, pero tengo curiosidad por saber si se le dio un algoritmo de maximización y se me pidió que obtuviera el doble (versión de minimización), ¿es solo cuestión de convertir todos los máximos en min y hacer otros ajustes básicos?¿Convertir un algoritmo de maximización en una minimización es una cuestión de cambiar de máximo a mínimo?

En caso afirmativo, ¿hay algún problema en que este no sea el caso? Si no, ¿hay una buena razón intuitiva por la que esto no funciona?

Fuente

2011-03-04 Legend

¿Hay una versión mínima del problema Knapsack? –

@Bill the Lizard: ¡Lo siento! Lo apreté rápidamente. Edité mi pregunta. – Legend

En realidad estaba pensando que podría ser el contraejemplo que estás buscando. Minimizar el valor de los objetos en la mochila es trivialmente fácil, pero es un algoritmo muy diferente a cambiar los signos de la solución al problema de maximización de la mochila. –

Sí, los problemas de maximización y minimización son básicamente los mismos. La solución para max(f(x)) es la misma que -min(-f(x)).

Al buscar árboles de juego, esta relación se utiliza, por ejemplo, para convertir una búsqueda minimax en una búsqueda negamax. Esto tiene la ventaja de que en lugar de escribir dos funciones, una para maximizar su puntaje y otra para minimizar el puntaje del oponente, usted escribe una única función de maximización pero da la vuelta al signo del resultado de la función de evaluación cuando es el movimiento de la otra persona.

Fuente

2011-03-04 21:44:35

[Teoría de juegos] (http://en.wikipedia.org/wiki/Game_theory) trata de modelar el comportamiento social usando las matemáticas, no estudiando los juegos reales. Hay [este] (http://en.wikipedia.org/wiki/Combinatorial_game_theory), pero las personas no llaman a esto * "teoría de juegos" * - por lo general, simplemente lo llaman * "juego AI" * * (El minimax el artículo confunde aún más las cosas al combinar el teorema de la teoría de decisiones con el algoritmo relacionado con el mismo nombre. Realmente, estos deben ser artículos separados). * –

El hecho de que sea simple no significa que sea tonto :) El algoritmo minimax es la columna vertebral de cada algoritmo de ajedrez, incluido el utilizado por Deep Blue para vencer al campeón mundial Garry Kasparov en 1997. Un concepto aún más simple (Redes neuronales) forma la base de algunos de los sistemas de aprendizaje/reconocimiento de computadoras más potentes de la tierra. * (PD. No quiero estar en desacuerdo con usted; ya tiene mi +1) * –

Depende de cómo funciona su algoritmo de maximización. Los algoritmos numéricos que necesitan gradientes probablemente harán más de max y min, y pueden surgir otras complejidades.

Sin embargo, de hecho hay una solución muy fácil. Maximizar una función f(a,b,c) es equivalente a minimizar -f(a,b,c). Entonces, solo niegue el resultado de la función.

Fuente

2011-03-04 21:44:50 luqui

Funciona si el problema es obviamente simétrico, como encontrar el máximo frente a un mínimo en una superficie 2D. Sin embargo, como está citando el problema de Knapsack: esa es una clase de problemas completamente diferente, no se puede encontrar el óptimo aplicando alguna función max() de manera codiciosa a un vector.

Fuente

2011-03-04 21:47:30

Gran observación. ¿Puedes elaborar un poco más? – luqui

Knapsack * se puede afirmar como un problema de maximización: "Teniendo en cuenta estos 20 artículos con estas propiedades, maximiza el valor de los artículos que puedes caber en esta mochila". O equivalentemente, "minimiza el valor de los artículos que tienes que dejar atrás". –

@Mark Byers: Ese es el mismo problema. Resolver uno le da una ruta directa a la solución para el otro (solo mire qué elementos sobran). Compare eso con 'array.min()' vs. 'array.max()', que no tiene la misma propiedad. –

¿Convertir un algoritmo de maximización en una minimización es una cuestión de cambiar de máximo a mínimo?

Respuesta

Cuestiones relacionadas