Algoritmo avaro

Un algoritmo avaro es un algoritmo que sigue el problema que soluciona heurístico de hacer la opción en la localidad óptima en cada etapa

con la esperanza de encontrar un grado óptimo global. En algunos problemas, una estrategia avara no tiene que producir una solución óptima, pero sin embargo un heurístico avaro puede ceder soluciones en la localidad óptimas que se acercan una solución óptima global.

Por ejemplo, una estrategia avara para el problema del viajante de comercio (que es de una complejidad computacional alta) es el heurístico siguiente: "En cada etapa visitan una ciudad no visitada el más cercana a la ciudad corriente". Esto heurístico no tiene que encontrar una el mejor solución, pero termina en un número razonable de pasos; el descubrimiento de una solución óptima típicamente requiere irrazonablemente muchos pasos. En la optimización matemática, los algoritmos avaros solucionan problemas combinatorios que tienen las propiedades de matroids.

Datos concretos

En general, los algoritmos avaros tienen cinco componentes:

  1. Un candidato se puso, de que una solución se crea
  2. Una función de selección, que elige al mejor candidato para añadirse a la solución
  3. Una función de viabilidad, que es usada para determinar si un candidato puede ser usado para contribuir a una solución
  4. Una función objetiva, que asigna un valor a una solución, o una solución parcial y
  5. Una función de solución, que indicará cuando hemos descubierto una solución completa

Los algoritmos avaros producen soluciones buenas en algunos problemas matemáticos, pero no en otros. La mayor parte de problemas para los cuales trabajan, tendrán dos propiedades:

Propiedad selecta avara: podemos hacer cualquier opción parece lo mejor en este momento y luego solucione los subproblemas que se levantan más tarde. La opción hecha por un algoritmo avaro puede depender de opciones hechas hasta ahora, pero no de futuras opciones o todas las soluciones del subproblema. Iterativamente hace una opción avara después del otro, reduciendo cada problema dado en uno más pequeño. En otras palabras, un algoritmo avaro nunca reconsidera sus opciones. Esto es la diferencia principal de la programación dinámica, que es exhaustiva y se garantiza encontrar la solución. Después de cada etapa, la programación dinámica toma decisiones basadas en todas las decisiones tomadas en la etapa anterior y puede reconsiderar el camino algorítmico de la etapa anterior a la solución.

Subestructura óptima: "Un problema expone la subestructura óptima si una solución óptima del problema contiene soluciones óptimas de los subproblemas."

Casos de fracaso

Para muchos otros problemas, los algoritmos avaros no pueden producir la solución óptima y pueden producir hasta la solución posible única peor. Un ejemplo es el problema del viajante de comercio mencionado anteriormente: para cada número de ciudades hay una asignación de distancias entre las ciudades para cual los productos heurísticos vecinos más cercanos el viaje único peor posible.

Imagine el ejemplo de la moneda con sólo 25 centavos, 10 centavos, y monedas de 4 centavos. El algoritmo avaro no sería capaz de hacer el cambio por 41 centavos, ya que después destinar a usar una moneda de 25 centavos y una moneda de 10 centavos sería imposible usar monedas de 4 centavos para el equilibrio de 6 centavos. Mientras que una persona o un algoritmo más sofisticado podrían hacer el cambio por 41 centavos con una moneda de 25 centavos y cuatro monedas de 4 centavos.

Tipos

Los algoritmos avaros se pueden caracterizar como 'corto visto', y como 'no recuperables'. Sólo son ideales para problemas que tienen 'la subestructura óptima'. A pesar de esto, los algoritmos avaros mejor se satisfacen para problemas simples (p.ej dando el cambio). Es importante, sin embargo, notar que el algoritmo avaro se puede usar como un algoritmo de selección a opciones prioritize dentro de una búsqueda, o rama y algoritmo atado. Hay unas variaciones al algoritmo avaro:

Aplicaciones

Los algoritmos avaros generalmente (pero no siempre) no pueden encontrar la solución globalmente óptima, porque por lo general no actúan exhaustivamente sobre todos los datos. Pueden asumir compromisos a ciertas opciones demasiado temprano que les impiden encontrar la mejor solución total más tarde. Por ejemplo, todos los algoritmos de colorante avaros conocidos para el problema de colorante del gráfico y todos otros problemas NP-complete no encuentran consecuentemente soluciones óptimas. Sin embargo, son útiles porque son rápidos para idear y a menudo dar aproximaciones buenas al grado óptimo.

Si se puede probar que un algoritmo avaro cede el grado óptimo global para una clase del problema dada, típicamente se hace el método de opción porque es más rápido que otros métodos de optimización como la programación dinámica. Los ejemplos de tales algoritmos avaros son el algoritmo de Kruskal y el algoritmo de Prim para encontrar árboles mínimos que atraviesan, algoritmo de Dijkstra para encontrar la fuente sola los caminos más cortos y el algoritmo para encontrar el grado óptimo árboles de Huffman.

La teoría de matroids y la teoría más general de greedoids, proporcionan clases enteras de tales algoritmos.

Los algoritmos avaros aparecen en el encaminamiento de la red también. Usando el encaminamiento avaro, un mensaje se expide al nodo vecino que es "el más cercano" al destino. La noción de la posición de un nodo (y de ahí "proximidad") puede ser determinada por su posición física, como en el encaminamiento geográfico usado por ad hoc redes. La posición también puede ser una construcción completamente artificial como en pequeño encaminamiento mundial y tabla hash distribuida.

Ejemplos

Véase también

Notas

Enlaces externos



Buscar