Data Structure & Algorithms
Greedy: decisiones locales y pruebas
Diseño de algoritmos greedy, greedy-choice property, optimal substructure, argumentos de intercambio y búsqueda de contraejemplos.
- Última actualización
- Actualizada
- Nivel
- Aplicación
Data Structure & Algorithms
Diseño de algoritmos greedy, greedy-choice property, optimal substructure, argumentos de intercambio y búsqueda de contraejemplos.
Un algoritmo greedy toma en cada paso la decisión que parece mejor localmente y no vuelve atrás. Puede ser muy eficiente, pero solo es correcto cuando el problema tiene una estructura que garantiza que esas decisiones locales pueden formar una solución global óptima.
“Parece razonable” no es una prueba.
estado actual
↓
mejor elección local según una regla
↓
problema restante
↓
repetir sin deshacerLa diferencia con backtracking es que greedy descarta alternativas de forma permanente. La diferencia con DP es que no compara todas las combinaciones de estados.
Dos propiedades frecuentes:
Existe una solución óptima que comienza con la elección greedy.
Después de esa elección, lo restante también es un problema óptimo de la misma familia.
Estas etiquetas ayudan a describir la estructura, pero todavía debes justificar por qué se cumplen.
Una técnica de prueba común:
Problema: elegir el máximo número de intervalos que no se solapen.
Regla greedy correcta: escoger primero el intervalo que termina antes.
type Interval = {
start: number;
end: number;
};
function maxNonOverlapping(intervals: Interval[]): Interval[] {
const sorted = [...intervals].sort((a, b) => a.end - b.end);
const selected: Interval[] = [];
let currentEnd = -Infinity;
for (const interval of sorted) {
if (interval.start >= currentEnd) {
selected.push(interval);
currentEnd = interval.end;
}
}
return selected;
}Elegir el que termina antes deja al problema restante la mayor cantidad de espacio posible. Cualquier solución óptima cuyo primer intervalo termine después puede intercambiarlo por el greedy sin invalidar los intervalos posteriores.
Tiempo: O(n log n) por ordenar; el recorrido es O(n). Espacio adicional depende del sort y del resultado.
Elegir el intervalo más corto no siempre maximiza la cantidad. Un intervalo corto ubicado en el centro puede bloquear uno a la izquierda y otro a la derecha.
Greedy falla cuando la métrica local no preserva suficientes opciones futuras.
Cada uno necesita su propia justificación. Compartir la palabra “mínimo” no los vuelve equivalentes.
Tomar siempre la moneda más grande funciona en algunos sistemas de denominaciones, pero no en todos.
Con monedas [1, 3, 4] y cantidad 6:
greedy: 4 + 1 + 1 = 3 monedas
óptimo: 3 + 3 = 2 monedasEl problema requiere DP salvo que las denominaciones tengan propiedades adicionales conocidas.
En selección de intervalos:
Después de procesar un prefijo ordenado por final,
selectedes una selección válida ycurrentEndes el final del último intervalo elegido.
El invariante prueba validez. El argumento de intercambio prueba optimalidad. Son preguntas distintas.
Prueba con:
Antes de implementar una regla greedy, intenta destruirla.
Greedy conserva una sola decisión por paso. DP conserva el mejor resultado para múltiples estados. Si la decisión local no puede demostrarse segura, DP suele modelar las alternativas necesarias, aunque con mayor costo.
Un greedy correcto necesita una regla local y una razón formal para descartar las demás opciones. La implementación suele ser corta; la dificultad está en la prueba.
¿Por qué encontrar una solución válida para muchos ejemplos no demuestra que una estrategia greedy sea óptima?
Porque los ejemplos solo muestran que la regla funciona en esas entradas. La optimalidad exige demostrar que ninguna alternativa produce un resultado mejor para cualquier entrada válida, o encontrar una transformación que lleve una solución óptima hacia la elección greedy sin empeorarla.