Cómo demostrar que el algoritmo codicioso es correcto

Tengo un algoritmo codicioso que sospecho que podría ser correcto, pero no estoy seguro. ¿Cómo verifico si es correcto? ¿Cuáles son las técnicas a utilizar para probar que un algoritmo codicioso es correcto? ¿Existen patrones o técnicas comunes?

^{Espero que esto se convierta en una pregunta de referencia que pueda usarse para señalar a los principiantes; de ahí su alcance más amplio de lo habitual. Tenga cuidado de dar respuestas generales, presentadas didácticamente, que se ilustran con al menos un ejemplo, pero que sin embargo cubren muchas situaciones. ¡Gracias!}

En última instancia, necesitará una prueba matemática de corrección. Llegaré a algunas técnicas de prueba para eso a continuación, pero primero, antes de sumergirme en eso, permítame ahorrarle algo de tiempo: antes de buscar una prueba, intente realizar pruebas al azar.

Pruebas aleatorias

Como primer paso, le recomiendo que use pruebas aleatorias para probar su algoritmo. Es sorprendente lo efectivo que es esto: en mi experiencia, para algoritmos codiciosos, las pruebas aleatorias parecen ser irrazonablemente efectivas. Dedique 5 minutos a codificar su algoritmo, y podría ahorrarse una o dos horas tratando de encontrar una prueba.

La idea básica es simple: implemente su algoritmo. Además, implemente un algoritmo de referencia que sepa que es correcto (por ejemplo, uno que pruebe exhaustivamente todas las posibilidades y tome lo mejor). Está bien si su algoritmo de referencia es asintóticamente ineficiente, ya que solo lo ejecutará en casos pequeños de problemas. Luego, genere aleatoriamente un millón de instancias de problemas pequeños, ejecute ambos algoritmos en cada uno y verifique si su algoritmo candidato da la respuesta correcta en cada caso.

Empíricamente, si su algoritmo codicioso candidato es incorrecto, generalmente lo descubrirá durante las pruebas aleatorias. Si parece ser correcto en todos los casos de prueba, entonces debe pasar al siguiente paso: proponer una prueba matemática de corrección.

Pruebas matemáticas de corrección

Bien, entonces tenemos que demostrar que nuestro algoritmo codicioso es correcto: que genera la solución óptima (o, si hay múltiples soluciones óptimas que son igualmente buenas, que genera una de ellas).

El principio básico es intuitivo:

Principio: si nunca haces una mala elección, lo harás bien.

Los algoritmos codiciosos generalmente implican una secuencia de elecciones. La estrategia de prueba básica es que vamos a tratar de demostrar que el algoritmo nunca hace una mala elección. Los algoritmos codiciosos no pueden dar marcha atrás, una vez que toman una decisión, se comprometen y nunca la deshacen, por lo que es fundamental que nunca hagan una mala elección.

¿Qué se consideraría una buena opción? Si hay una única solución óptima, es fácil ver cuál es una buena opción: cualquier opción que sea idéntica a la que se hizo con la solución óptima. En otras palabras, intentaremos demostrar que, en cualquier etapa de la ejecución de los algoritmos codiciosos, la secuencia de elecciones realizadas por el algoritmo hasta ahora coincide exactamente con algún prefijo de la solución óptima. Si hay varias soluciones óptimas igualmente buenas, una buena opción es una que sea consistente con al menos una de las óptimas. En otras palabras, si la secuencia de opciones del algoritmo hasta ahora coincide con un prefijo de una de las soluciones óptimas, todo está bien hasta ahora (nada ha salido mal todavía).

Para simplificar la vida y eliminar las distracciones, centrémonos en el caso en el que no hay vínculos: hay una única solución única y óptima. Toda la maquinaria se trasladará al caso donde puede haber múltiples óptimos igualmente buenos sin ningún cambio fundamental, pero debe ser un poco más cuidadoso con los detalles técnicos. Comience por ignorar esos detalles y enfóquese en el caso en que la solución óptima es única; eso te ayudará a concentrarte en lo que es esencial.

Hay un patrón de prueba muy común que usamos. Trabajaremos duro para demostrar la siguiente propiedad del algoritmo:

Reclamación: Sea la salida de la solución por el algoritmo y sea ​​la solución óptima. Si es diferente de , entonces podemos ajustamos para obtener otra solución que es diferente de y estrictamente mejor que .$S$$O$$S$$O$$O$$O^*$$O$$O$

Observe por qué esto es útil. Si la afirmación es verdadera, se deduce que el algoritmo es correcto. Esto es básicamente una prueba de contradicción. O es lo mismo que o es diferente. Si es diferente, entonces podemos encontrar otra solución que sea estrictamente mejor que , pero eso es una contradicción, ya que definimos que es la solución óptima y no puede haber ninguna solución mejor que esa. Entonces nos vemos obligados a concluir que no puede ser diferente de ; siempre debe ser igual a$S$$O$$O^*$$O$$O$$S$$O$$S$$O$, es decir, el algoritmo codicioso siempre genera la solución correcta. Si podemos probar la afirmación anterior, entonces hemos demostrado que nuestro algoritmo es correcto.

Multa. Entonces, ¿cómo demostramos el reclamo? Pensamos en una solución como un vector que corresponde a la secuencia de elecciones realizadas por el algoritmo, y de manera similar, pensamos en la solución óptima como un vector correspondiente a la secuencia de opciones que conduciría a . Si es diferente de , debe existir algún índice donde ; nos centraremos en los más pequeños como . Luego, modificaremos cambiando un poco en la$S$$(S_1,\dots,S_n)$$n$$O$$(O_1,\dots,O_n)$$O$$S$$O$$i$$S_i \ne O_i$$i$$O$$O$$i$La posición para que coincida con , es decir, modificaremos la solución óptima cambiando la ésima opción a la elegida por el algoritmo codicioso, y luego mostraremos que esto conduce a una solución aún mejor. En particular, definiremos como algo así$S_i$$O$$i$$O^*$

excepto que a menudo tendremos que modificar la parte ligeramente para mantener la consistencia global. Parte de la estrategia de prueba implica cierta inteligencia para definir adecuadamente. Entonces, la carne de la prueba estará de alguna manera usando datos sobre el algoritmo y el problema para mostrar que es estrictamente mejor que ; ahí es donde necesitará algunas ideas específicas del problema. En algún momento, deberás sumergirte en los detalles de tu problema específico. Pero esto le da una idea de la estructura de una prueba típica de corrección para un algoritmo codicioso.$O_{i+1},O_{i+2},\dots,O_n$$O^*$$O^*$$O$

Un ejemplo simple: subconjunto con suma máxima

Esto podría ser más fácil de entender trabajando con un ejemplo simple en detalle. Consideremos el siguiente problema:

Entrada: Un conjunto de enteros, un entero Salida: Un conjunto de tamaño cuya suma es lo más grande posible$U$$k$
$S \subseteq U$$k$

Hay un algoritmo codicioso natural para este problema:

1. Conjunto .$S := \emptyset$
2. Para : $i := 1,2,\dots,k$
   • Supongamos que es el número más grande en que aún no se ha elegido (es decir, el número más grande en ). Añadir a .$x_i$$U$$i$$U$$x_i$$S$

Las pruebas aleatorias sugieren que esto siempre da la solución óptima, así que demostremos formalmente que este algoritmo es correcto. Tenga en cuenta que la solución óptima es única, por lo que no tendremos que preocuparnos por los lazos. Probemos la afirmación descrita anteriormente:

Reclamación: Sea la salida de la solución mediante este algoritmo en la entrada y la solución óptima. Si , entonces podemos construir otra solución cuya suma es incluso más grande que .$S$$U,k$$O$$S \ne O$$O^*$$O$

Prueba. Asumo , y dejar sea el índice de la primera aparición, siendo . (Tal un índice tiene que existir, ya que hemos asumido y por la definición del algoritmo tenemos .) Puesto que (por supuesto) es mínima, nos debe tener , y en particular, tiene la forma , donde los números se enumeran en orden descendente. Mirando cómo el algoritmo elige$S \ne O$$i$$x_i \notin O$$i$$S \ne O$$S=\{x_1,\dots,x_k\}$$i$$x_1,\dots,x_{i-1} \in O$$O$$O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$$x_1,\dots,x_{i-1},x'_i,\dots,x'_n$$x_1,\dots,x_i$, vemos que debemos tener para todo . En particular, . Por lo tanto, definir , es decir, se obtiene mediante la supresión de la ésimo número en y la adición de . Ahora la suma de elementos de es la suma de elementos de más y , por lo que la suma de es estrictamente mayor que la suma deEsto prueba el reclamo. $x_i > x'_j$$j\ge i$$x_i > x'_i$$O^ = O \cup \{x_i\} \setminus \{x'_i\}$$O^*$$i$$O$$x_i$$O^*$$O$$x_i-x'_i$$x_i-x'_i>0$$O^*$$O$$\blacksquare$

La intuición aquí es que si el algoritmo codicioso alguna vez toma una decisión que es inconsistente con , entonces podemos demostrar que podría ser aún mejor si se modificara para incluir el elemento elegido por el algoritmo codicioso en esa etapa. Dado que es óptimo, no puede haber ninguna forma de hacerlo aún mejor (eso sería una contradicción), por lo que la única posibilidad restante es que nuestra suposición sea incorrecta: en otras palabras, el algoritmo codicioso nunca tomará una decisión que es incompatible con .$O$$O$$O$$O$

Este argumento a menudo se llama argumento de intercambio o lema de intercambio . Encontramos el primer lugar donde la solución óptima difiere de la solución codiciosa e imaginamos intercambiar ese elemento de por la elección codiciosa correspondiente (intercambiado por ). Algunos análisis mostraron que este intercambio solo puede mejorar la solución óptima, pero por definición, la solución óptima no se puede mejorar. Entonces, la única conclusión es que no debe haber ningún lugar donde la solución óptima difiera de la solución codiciosa. Si tiene un problema diferente, busque oportunidades para aplicar este principio de intercambio en su situación específica.$O$$x'_i$$x_i$

Usaré el siguiente algoritmo de clasificación simple como ejemplo:

repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

Para probar la corrección, utilizo dos pasos.

• Primero muestro que el algoritmo siempre termina.
• Luego muestro que la solución donde termina es la que quiero.

Para el primer punto, elijo una función de costo adecuada para la cual puedo mostrar que el algoritmo la mejora en cada paso.

Para este ejemplo, elijo el número de inversiones en la lista de entrada. Una inversión en una lista es un par de entradas , tal que pero . El número de inversiones siempre es no negativo y una lista ordenada tiene 0 inversiones.$A$$A[i]$$A[j]$$A[i] > A[j]$$i<j$

Intercambiar claramente dos elementos adyacentes , que están en el orden incorrecto elimina la inversión pero no afecta ninguna otra inversión. Por lo tanto, el número de inversiones se reduce en cada iteración.$A[i]$$A[i+1]$$A[i],A[i+1]$

Esto prueba que el algoritmo finalmente termina.

El número de inversiones en una lista ordenada es 0. Si todo va bien, el algoritmo reducirá el número de inversiones a 0. Solo necesitamos mostrar que no se atasca en un mínimo local.

Usualmente pruebo esto por contradicción. Supongo que el algoritmo se detuvo, pero la solución no es correcta. En el ejemplo, esto significa que la lista aún no está ordenada, pero no hay elementos adyacentes en el orden incorrecto.

Si la lista no está ordenada, debe haber al menos dos elementos que no estén en la posición correcta. Supongamos que y , , sean dos de estos elementos, la diferencia entre y es mínima. Como el algoritmo no se detuvo, no son adyacentes, por lo que . Debido a que asumimos la minimidad, y , pero luego y tenemos una contradicción.$A[i]$$A[j]$$i<j$$A[i]>A[j]$$i$$j$$i+1 < j$$A[i]<A[i+1]$$A[i+1]<A[j]$$A[i]<A[j]$

Esto demuestra que el algoritmo solo se detiene cuando se ordena la lista. Y por lo tanto hemos terminado.