Cuando decimos que un algoritmo es codicioso, solo queremos decir que en cualquier momento dado, optimiza algún resultado a corto plazo. En algunos problemas (pero no en otros), la optimización en los puntos de decisión de un resultado particular a corto plazo también optimiza la función objetivo global.
Algunos problemas de la entrevista le piden que optimice alguna función objetivo (“Encontrar el máximo …”). En algunos de estos casos, la idea anterior puede conducir a una solución. En algunos casos, puede que no. Definitivamente es útil como técnica de resolución de problemas considerar si un enfoque ambicioso funcionaría o no. Entonces sí, es útil.
Su utilidad depende de lo que consideres un uso no trivial. Usas un razonamiento codicioso todo el tiempo y ni siquiera te das cuenta. Digamos que le pido que obtenga el valor máximo en una matriz. Usted razona que con cada nuevo valor que lee, puede tomar el mayor del máximo hasta ahora y el nuevo valor. Este es técnicamente un enfoque codicioso, ya que está optimizando el máximo global mediante un principio “local” de “tome lo que parece más grande en este momento”.
- ¿Cuál es la mejor video conferencia sobre diseño orientado a objetos?
- ¿Cuál es la diferencia entre la edición estándar y la edición india de Cracking the Coding Interview, 2011, sexta edición?
- ¿Cómo podemos permutar una cadena de modo que todas las ventanas de tamaño 'k' tengan caracteres únicos?
- ¿Por qué los montones de Fibonacci se llaman montones de Fibonacci?
- ¿Cuáles son las preguntas generales que se hacen en las entrevistas de IPM?
El razonamiento codicioso ya es una parte esencial de su razonamiento sobre muchos problemas. Estás preguntando qué tan útil es en casos donde no es obvio si es correcto, pero puedes ver cómo eso depende de dónde trazas la línea entre lo que es obvio y lo que no.
Nota al margen: el ejemplo anterior también muestra por qué nunca debe decir “solo use un método codicioso” para describir su enfoque a un problema. Sin más información sobre el resultado a corto plazo para el que está optimizando con avidez, o el orden en el que realiza la entrada, tal descripción no tiene sentido.