Estaba investigando programación dinámica y leí lo siguiente:
A menudo, cuando se utiliza un método más ingenuo, muchos de los subproblemas se generan y resuelven muchas veces.
¿Qué es un método ingenuo?
terminology
dynamic-programming
chopper draw lion4
fuente
fuente
Respuestas:
No es un término técnico con un significado preciso, es solo la palabra inglesa "ingenuo". En un contexto informático, la palabra generalmente significa algo así como "una de las cosas en las que pensaría primero, pero sin darse cuenta de un hecho menos obvio pero importante".
Por ejemplo, si uno sabe que la definición de los números de Fibonacci esF i b (n)= F i b (n-1)+ F i b (n-2) , entonces una implementación "ingenua" sería
¿Cuál es el problema? Que si llamamos, digamos,
Fib(7)
entonces terminamos haciendo muchas de las mismas llamadas una y otra vez, comoFib(4)
(porqueFib(7)
llamaFib(6)
yFib(5)
, yFib(6)
llamaFib(5)
yFib(4)
, y las dos veces lo llamamosFib(5)
llamadasFib(4)
yFib(3)
, y así sucesivamente).Entonces, una solución más "sofisticada", en lugar de ingenua, sería como una programación dinámica y evitar todos los cálculos adicionales.
fuente
En general, podemos resolver cada problema en NP a tiempo2poli ( n ) por fuerza bruta , lo que significa que enumeramos explícitamente a todos los candidatos para un testigo NP, que tiene un polinomio de longitud en el tamaño de entradanorte . En este contexto, el método de "verificar todas las soluciones posibles" puede considerarse ingenuo.
fuente
La implementación ingenua es la solución donde parece sencilla y menos complicada posible.
En algunos casos, puede no tener un buen comportamiento en el espacio o el tiempo, como la implementación ingenua de la función de Fibonacci (exponencial en lugar de lineal).
Pero en muchos casos, puede funcionar bien la mayor parte del tiempo. Entonces, no hay nada malo con el enfoque ingenuo, puede hacerlo en 3 pasos:
"Haz que funcione" (según lo solicitado) -> "Hazlo elegante / hermoso" (refactorización, más legible) -> "Hazlo rápido" (optimización del rendimiento)
Para los lenguajes de programación con tradiciones de "sobre-ingeniería" como Java, recomendaría la "solución más simple" cualquier día.
fuente