Técnicas para la resolución de problemas np-completos



Descargar 75.4 Kb.
Página2/4
Fecha de conversión12.08.2020
Tamaño75.4 Kb.
1   2   3   4
El problema: Dado x1 , x2 , x3 .... xn un conjunto de números reales entre 0 y 1; dividiendo los números en pocos subconjuntos de forma que en cada conjunto haya al menos uno.

Una heurística para este problema es poner x1 en el primer bin, y para cada i, poner xi en el primer lugar que tiene para ello, o comenzar un nuevo bin si no hay sitio en los bins usados. Este algoritmo es llamado "first fit". Este algoritmo no es demasiado malo.

El algoritmo first fit requiere al menos 2 OPT bins, donde OPT es el mínimo número de bins.

First fit no puede dejar dos bins a no ser que no esté medio lleno; por otro lado; el item en el segundo bin podría ser colocado en el primer bin. Sin embargo, el número de bins usados no es mas que la suma del tamaño de todos los items (redondeando).El teorema siguiente da por hecho que el número de bins en la mejor solución no puede ser menos que la suma de todo el tamaño (en cuyo caso todos los items son perfectamente empacados).

El first fit puede ser mejorado con una simple modificación. El peor caso se produce cuando aparecen al principio todos los números pequeños entonces, en vez de colocar los números en los bins en el orden que aparecen, nosotros los ordenamos en orden decreciente, y entonces usamos first fit. Esta modificación del algoritmo es llamada decreasing first fit.

El algoritmo decreasing first fit requiere al menos 11/9 OPT + 4 bins, donde OPT es el mínimo número de bins.

Esta constante es también tigh. First fit y decreasing first fit son ambos heurísticas. Hay otros métodos que nos proporcionan mejores constantes. En muchos casos, el análisis es complicado.

Las estrategias descritas son típicas de algoritmos heurísticos.


Euclidean traveling salesman


El problema traveling salesman (TSP), es un problema importante con muchas aplicaciones. Se discute aquí una variación del TSP con restricciones adicionales que el peso corresponde a distancias Euclídeas.




Compartir con tus amigos:
1   2   3   4


La base de datos está protegida por derechos de autor ©odont.info 2019
enviar mensaje

    Página principal