¿Cómo se prueba que la propiedad de elección codiciosa se mantiene en un problema dado?

Answer 1

Probar que el problema de selección de tareas exhibe la propiedad de elección codiciosa
Suponga que la lista ordenada de tareas T [1..m] es una solución aleatoria para el problema de ITS y la lista ordenada de tareas G [1..n] es una solución codiciosa en la que elegimos repetidamente la tarea de primer final.
Según la estrategia, G [1] termina a más tardar que S [1]. Por lo tanto, S [2] también es compatible con G [1], por lo que G [2] termina a más tardar que S [2]. Por inducción matemática, podemos demostrar que, en general, para 1 <= i <= m-1, G [i] termina a más tardar S [i] y por lo tanto S [i + 1] es compatible con G [i] y por lo tanto, S [m] es compatible con G [m-1], por lo que esta solución codiciosa contiene al menos m tareas. En otras palabras, no hay mejores soluciones que esta codiciosa solución, por lo que es óptima.
Por lo tanto, este problema exhibe la propiedad de elección codiciosa.