Buscando un ejemplo significativo que destaca el suboptimality los algoritmos codiciosos

Question

Una semana a partir de ahora, voy a presentar mi trabajo a un montón de compañeros de trabajo que no se utilizan para la optimización mundo y la terminología. Uno de los principales algoritmos he implementado utiliza un codicioso tipo de algoritmo (un multi-inicio aleatorio algoritmo greedy), y me gustaría realmente quiero hacer dos cosas muy claras, con ejemplos sencillos : lo que el algoritmo voraz es, y por qué es subóptima.

Pensé en dar ejemplos con el camino más corto problema, pero estoy buscando ejemplos de la vida real, tal vez situaciones en las que, naturalmente, el uso de un codicioso enfoque inconscientemente.

Puede usted pensar en algo ?

Answer 1

Poner monedas en una máquina expendedora o hacer el cambio. El objetivo es minimizar el número de monedas de usa. Un algoritmo voraz utiliza las monedas de denominación posible más alto primero. Si es o no el algoritmo voraz óptima depende del sistema de la moneda. En el sistema estadounidense y el sistema del Euro, el algoritmo voraz realmente es óptimo. Más información aquí.

Answer 2

Dos naturales de algoritmos para resolver el problema del viajante de comercio (TSP) (la búsqueda de un mínimo costo "circular" tour (hamiltonion circuito) de los vértices de un grafo completo) son codiciosos. Uno de esos algoritmo es empezar la casa y visitar la próxima que vértice que es la más cercana, pero que no ha sido visitado, y volver a casa sólo cuando no hay otro sitio está disponible para completar el recorrido. Otro algoritmo para ordenar los bordes con el fin de aumentar el tamaño y la forma de un tour por la adición de estas aristas en orden creciente de costo, de manera que se crea un circuito. No es difícil encontrar ejemplos en ambos de estos algoritmos generar visitas que no son óptimas.Es interesante que el segundo de estos algoritmos no funciona para encontrar un coste mínimo árbol de expansión de un grafo conexo (en esencia se Utiliza el algoritmo). Una variante de la primera algoritmo también trabaja para encontrar un coste mínimo árbol de expansión y es conocido como el algoritmo de Prim.

Answer 3

Problemas típicos que requieren programación dinámica generalmente fallará miserablemente con un algoritmo voraz. Por lo tanto, el problema de la mochila viene a la mente.

Por supuesto, caminos más cortos en un grafo con pesos negativos es muy fácil de ilustrar con gráficos muy pequeños. Naive algoritmos codiciosos del camino más cortos en cualquier gráfico, también trabajan. Esto inmediatamente se presta a una aplicación de la vida real: planificación de la ruta más corta desde el punto de $A$ a $B$ (p. ej., sistema GPS de coche).

Answer 4

Un ejemplo que viene a la mente, es problema de maximización de una ponderado independiente situado en un grafo ponderado, que es encontrar el mayor peso subconjunto del conjunto de vértices, de tal manera que no hay dos vértices en el subconjunto tiene un borde entre ellos. Para un poco irreal ejemplo del mundo real, considere la posibilidad de disponer de un conjunto de lugares que han pesos dado por el beneficio esperado obtenido a partir de la apertura de una tienda allí. Monopolio de las leyes previenen la empresa a partir de la apertura de tiendas en las ciudades conectadas por un único tramo de carretera. Ahora bien, si nuestra gráfica a este aspecto, uno central de la ciudad, lo que hará un poco más beneficios que la apertura de tiendas en cada una de las localidades vecinas, el algoritmo voraz sería increíblemente subóptima. De hecho, es mucho mejor abrir tiendas en todas las ciudades de la ciudad, pero cuando el algoritmo voraz recoge la primera ciudad se descarta la posibilidad de la apertura de tiendas en cualquier otro lugar.