Algoritmo ingenuo / codicioso / de enumeración: sistemas complejos e inteligencia artificial

Contenido

Algoritmo ingenuo

a algoritmo naif tiene como objetivo proporcionar un resultado básico a un problema. El método ingenuo no realiza ningún cálculo preparatorio y utiliza solo los datos básicos del problema.

Tomemos por ejemplo un problema de mochila. El algoritmo ingenuo consistiría en tomar primero los objetos de menor tamaño hasta que no se puedan poner más objetos nuevos en la bolsa.

para I de 1 Para no
   si w [i] + w_conso ≤ W entonces
      x [i]: = 1 w_conso: = w_conso + w [i]
   de lo contrario
      x [i]: = 0
   terminara si
final para

Algoritmo codicioso (método intuitivo)

Al igual que el algoritmo ingenuo, un algoritmo llamado codicioso se basa en un principio simple: durante una iteración, el algoritmo siempre toma la decisión de la "mejor elección". Por lo tanto, es necesaria una elección localmente óptima con el objetivo de que esta elección conduzca a la solución óptima global. Sin embargo, el algoritmo no ofrece ninguna garantía de que la última solución sea una solución óptima.

Intuitivamente, podemos decirnos que para maximizar la utilidad en el problema de la mochila, basta con poner el elemento de mayor utilidad (con un tamaño compatible con el tamaño restante en la bolsa) hasta que no tenga más espacio en la bolsa.

Para esto consideraremos X y w los vectores de la elección del objeto y de su peso ordenados en orden decreciente de eficiencia (eficiencia = utilidad / peso). Entonces el algoritmo funciona como el método ingenuo.

Un simple ejemplo nos permite entender que esta elección no siempre es óptima: tomemos un objeto de tamaño 1 y utilidad 2, y un objeto de tamaño y utilidad igual al tamaño de la bolsa. En estas condiciones, se elegirá primero el primer objeto de mayor utilidad. No hay más espacio para colocar el segundo objeto. La solución óptima sería elegir solo el segundo objeto de la bolsa.

Fuerza bruta o enumeración

A diferencia del algoritmo ingenuo, este método garantiza el óptimo general, pero su tiempo de ejecución y el consumo de memoria pueden superar rápidamente los límites de una PC. El principio es simple, debe enumerar todas las posibles soluciones al problema y elegir la mejor solución.

Por lo general, el árbol de soluciones se representa como su nombre indica como un árbol. Tomemos el ejemplo del problema de la mochila con cuatro objetos con los siguientes parámetros y un tamaño de bolsa de 30:

objeto	1	2	3	4
u_i	7	3	4	3
Wisconsin	13	8	12	10

El árbol se construye por iteración: en cada iteración, las nuevas hojas representan si tomar o no el siguiente objeto. Obtenemos el siguiente árbol binario:

algoritmo ingenuo algoritmo codicioso enumeración de fuerza bruta

Las tapas en rojo superan el tamaño máximo de bolsa, la tapa en violeta es la solución óptima. Como puede ver, el número de hojas es igual a 2^(n-1) para el objeto no. Por tanto, el número de nodos generados hasta el objeto n es 2^no -1.