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, el llamado algoritmo codicioso se basa en un principio simple: durante una iteración, el algoritmo siempre toma la decisión de la "mejor opción". Por lo tanto, necesitamos una elección óptima localmente con el objetivo de que esta elección conduzca a la solución óptima global. Sin embargo, el algoritmo no garantiza que la última solución sea una solución óptima.

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

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

Un ejemplo sencillo permite comprender 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 con la 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 global, pero su tiempo de ejecución y 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.

En general, el árbol de soluciones se representa como sugiere el nombre en forma de árbol. Considere 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:

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. El número de nodos generados hasta el objeto n es por lo tanto 2^no -1.