¿Cómo demuestro el Algoritmo de Intervalo Mínimo diseñado?
Estoy tratando de aprender cómo demostrar la corrección y optimalidad de los algoritmos. Para ello, estoy tratando de hacerlo para el problema:
La entrada es una lista de intervalos ([l1,r1],[l2,r2],…,[ln,rn])
Encuentra la cobertura de intervalos mínima, es decir, la cobertura con la menor cantidad de intervalos que contienen todos los intervalos de la lista de intervalos.
Para ([1,4],[2,7],[10,11]), sería ([1,7],[10,11])
sort(X) //ordenar X por inicio de intervalo l de forma creciente
l’ <- izquierda(x0)
r' <- derecha(x0)
remove(x0,X) //eliminar x0 de la lista de intervalos X
for x in X:
l<- izquierda(x)
r<- derecha(x)
if r>r’ and l<=r'+1:
r'<-r
if l>r’:
expandedX = [l’,r’]
Result.add(expandedX)
l’= izquierda(x)
r’= derecha(x)
Tiempo de ejecución en O(nlogn+n)
Ahora realmente no sé cómo demostrarlo.
¿Cómo llego a un enfoque sistemático que resulte en una prueba válida?
Mi intento:
Sea Y la cobertura de intervalos producida por el algoritmo y sea Y’ la cobertura de intervalos óptima.
Supongamos que Y no es óptima.
Por lo tanto, |Y’| < |Y|
Esto implica que existe un y en Y tal que y no está en Y’ y existe un y’ tal que y es un subconjunto de y’
Esto implica que existe un y” en Y tal que izquierda(y”) <= derecha(y)
¿Es este un comienzo válido?
davy.ai
Sí, este es un comienzo válido. Has identificado la suposición de que Y no es óptimo y has demostrado que esto implica la existencia de dos intervalos y y y’ tales que y está contenido en y’, pero y’ no está en Y’. Esta es una observación útil que puede ayudarte a avanzar hacia una prueba por contradicción.
Para continuar, podrías suponer que Y es producido por el algoritmo, y luego asumir que Y no es óptimo. Esta suposición implica las afirmaciones previas que has hecho, es decir, que existe y en Y, existe y’ en Y’ tal que y es un subconjunto de y’, y el punto de inicio izquierdo de y” es menor o igual que el punto final derecho de y.
A continuación, podrías considerar los pasos del algoritmo y razonar sobre qué efecto tienen en la cobertura de intervalos. Por ejemplo, el primer paso ordenar la lista de intervalos en orden creciente de los puntos de inicio. ¿Cómo afecta esto a la cobertura resultante? ¿Cómo afecta la eliminación de x0 de la lista de intervalos a la cobertura?
Dividiendo el algoritmo en pasos más pequeños y reflexionando sobre el efecto de cada paso en la cobertura de intervalos, puedes construir un argumento sólido sobre la corrección y optimalidad del algoritmo. Además, podrías considerar casos específicos y ejecutar el algoritmo manualmente para comprobar que produce la salida esperada.