Realmente no.
El problema principal por el cual los algoritmos codiciosos y las pruebas se mencionan a menudo en la misma oración es que es realmente fácil diseñar algoritmos codiciosos incorrectos . Hay muchas situaciones en las que un algoritmo codicioso parece plausible pero no funciona. Es por eso que a menudo se enfatiza que es importante probar la corrección de un algoritmo codicioso propuesto.
Por supuesto, importante no tiene que significar difícil . De hecho, lo contrario a menudo es cierto: si tiene el algoritmo codicioso correcto, su corrección a menudo es razonablemente fácil de mostrar. Por lo general, todo lo que tiene que hacer es demostrar que no hay forma de tomar la solución producida por su algoritmo y modificarla en una solución mejor.
- ¿Qué tipo de operaciones podrían aplicarse sobre un árbol de segmentos?
- ¿Cuál es la mejor manera de dominar los algoritmos de clasificación?
- Dado un gráfico no dirigido y dos conjuntos de nodos, ¿cuál es el mejor algoritmo para verificar que cada elemento del primer conjunto sea adyacente a cada elemento del segundo conjunto?
- Cómo construir robots enjambre
- ¿Está sesgado el algoritmo de aleatorización del Reproductor de Windows Media?
Aquí hay un ejemplo simple de cómo funciona la técnica general en muchos casos.
Imagine que hay una sola bomba de agua y que [matemática] n [/ matemática] personas simplemente vinieron a usarla. Las personas llevan cubos de [matemáticas] n [/ matemáticas] volúmenes diferentes: [matemáticas] v_1, \ puntos, v_n [/ matemáticas]. ¿En qué orden deben obtener agua para minimizar el tiempo de espera total (o, equivalentemente, el tiempo de espera promedio)?
Aquí se explica cómo descubrir el algoritmo codicioso correcto junto con su prueba de corrección:
Imagine que la gente ya se alineó de alguna manera. Mira a dos personas consecutivas . Si el que está más adelante en la alineación tiene un cubo más pequeño que el que está delante de ellos, podemos intercambiarlos. Esto siempre mejorará el tiempo de espera total: la suma de los tiempos de espera de nuestros dos actores ha disminuido claramente y nadie más se vio afectado.
Y esa es básicamente la prueba completa. Un orden que puede mejorarse intercambiando dos personas no puede ser óptimo. Por lo tanto, en el orden óptimo no podemos intercambiar dos personas. Pero solo hay un orden de este tipo: el que ordena a las personas de acuerdo con el tamaño de su cubo, comenzando con el más pequeño. Por lo tanto, tenemos un algoritmo codicioso (un tipo simple) y también un argumento por el cual siempre produce la solución óptima.
Argumentos de cambio similares a menudo se pueden usar para probar la corrección de algoritmos codiciosos (o incluso para descubrirlos).
