algorithm - programa - Pruebas unitarias de un algoritmo complejo.

prueba de escritorio en dfd (8)

Al probar algoritmos complejos, usted confía en los "datos" que deben verificarse. Supongamos que ya tiene soluciones (datos) en alguna forma del problema. Simplemente tome los datos y deje que su algoritmo se ejecute y vea si las respuestas coinciden. Tome el ejemplo de resolver un n-puzzle usando un algoritmo, no es determinista, pero tiene datos para verificar la solución.

¿Cómo escribirías pruebas para probar una solución para un algoritmo bastante complejo como el problema N Queens ? Lo que quiero decir es cuál debe ser el enfoque correcto para probar un algoritmo que

tiene muchas soluciones (no sabes / no te importa cuántos de ellos existen),
solo puede tener un pequeño subconjunto de todas las soluciones posibles, y
verificar que una solución es correcta puede ser un poco complicado (tal vez comparable en complejidad con el algoritmo mismo).

Sé que estas condiciones no están presentes en el problema de N-Queens en sí, pero lo mencioné para dar una especie de ejemplo.

Creo que esta es una muy buena pregunta y no hay una bala de plata. Solo te contaré sobre mi experiencia.

Escribí un algoritmo para encontrar el conjunto de puntos más cercano entre dos cilindros en el espacio 3D. Este es un problema muy complejo y el espacio de entrada es enorme.

Para probar mi código, al principio solo generé algunos casos canónicos, que estaban bastante alineados con los ejes, de modo que el resultado "correcto" era obvio. Pero eso era demasiado débil.

Luego pude "reforzar" los casos canónicos aplicando transformaciones aleatorias. Esto ayudó un poco.

Luego pensé en escribir otro algoritmo duplicado e implementación, pero eso era ridículamente difícil, y no hay manera de saber si ambos algoritmos podrían mostrar el mismo error. Sin embargo, para otro problema, esto podría ser factible, como con la fuerza bruta: no eficiente, pero muy simple de entender y verificar.

Entonces pensé en las propiedades de las soluciones establecidas. Por ejemplo, el vector de separación debe ser un mínimo local, por lo que debería poder "mirar alrededor" cada punto final de la solución (por un pequeño épsilon) y determinar si la solución es un mínimo local.

Entonces comencé a pensar en las propiedades topológicas de la función que mapea la entrada a la salida. En este caso, sé que la distancia de separación debe variar suavemente. Así que elegí una entrada aleatoria y un delta pequeño, y luego comparo la salida con y sin el delta aplicado. Si el algoritmo es correcto, entonces la diferencia en la salida debe ser pequeña.

Al combinar todas estas técnicas pude obtener una alta confianza en el código.

En su ejemplo, creo que usted está diciendo que quiere probar un algoritmo que verifique una solución propuesta.

Usted querría cubrir los siguientes casos:

Pruebas de ruta feliz para verificar que el algoritmo acepta una variedad de soluciones correctas
Pruebas de ruta feliz para verificar que el algoritmo rechaza una variedad de soluciones incorrectas
Pruebas de ruta triste para garantizar que el algoritmo maneje correctamente los no candidatos (por ejemplo, una "solución" con 7 reinas en lugar de 8, etc.)

Aquí, "una variedad" significa que desea que las soluciones cubran el espacio de posibilidades. Pero lo que significa cubrir ese espacio es específico del problema. No estoy lo suficientemente familiarizado con el problema de las N-reinas para saber qué variedad existe en las soluciones correctas, pero esa información sería útil si implementara las pruebas. En cuanto a las soluciones incorrectas, querría algunas que incluyan el mismo rango, el mismo archivo, la misma diagonal y una combinación. Algunas implican exposición a lo largo del borde del tablero y otras implican exposición fuera del borde. Etc.

Además, si tiene información sobre la distribución de soluciones, puede priorizar aquellas que son más probables, aunque al final querrá cubrir incluso aquellas soluciones que son menos probables ya que son las que tienden a romper las cosas en la realidad. vida.

Además, si el algoritmo es complicado, entonces tiene sentido descomponerlo en partes y probar la corrección de esas partes de la misma manera (distinguir entre ruta feliz y ruta triste, y probar entradas de ambos tipos).

La prueba de la unidad debe verificar la salida del algoritmo para una amplia variedad de entradas y, como esta tarea también es compleja, tiene que ser escrita por una persona diferente (y espero que si hay un error en el código, no lo haga). mismo error)

Los algoritmos son, en realidad, las cosas más fáciles de realizar una prueba unitaria, ya que no tiene dependencias externas. El mejor enfoque es usar el desarrollo guiado por pruebas: descubra cuál es el siguiente requisito que desea que cumpla el algoritmo, cree una prueba para él y luego escriba el código para satisfacer esa prueba (y no más código del necesario, incluso si esto significa codificar el resultado). Luego continúa, refactorizando el código base según sea necesario para hacerlo más general y aceptar más casos de uso. Cuando todos sus casos de uso estén cubiertos, debe tener una implementación sólida del algoritmo.

Si sabe qué tipo de algoritmo necesitará, entonces una opción es implementar algunas partes de ese algoritmo utilizando TDD. De modo que cuando esas partes se hayan implementado, construir el algoritmo completo será trivial.

Aquí hay un ejemplo de un problema ( diagrama de nueve lugares ) para el cual no conocía la solución, por lo que escribir una prueba hubiera sido difícil, si no imposible, o poco práctico desde el punto de vista de TDD (también habría requerido un gran salto). Reconocí que era bastante similar al problema de Nine Queens, así que decidí usar un algoritmo similar al que había usado para resolver Nine Queens. Utilicé DiagramTest para probar el Diagram , después de lo cual, juntar todo en DiagramOfNinePlaces fue solo una docena de líneas de código. Después de ejecutar el código, verifiqué el resultado final a mano y de hecho fue una solución al problema.

Solo puedes probar el comportamiento que sabes que puedes esperar.

¿Sabes que existe una solución para algunos datos de prueba? Por ejemplo, puede descubrir a mano que definitivamente es posible colocar seis reinas en un tablero de 8x8, o puede leer en un libro que existe al menos una solución para colocar ocho reinas en el tablero de 8x8. Luego puede probar que su programa devuelve al menos una solución (quizás no compruebe que sea una solución válida).

¿Sabe que no existe una solución para algunos otros datos de prueba? Por ejemplo, puedes convencerte fácilmente de que es imposible poner tres reinas en un 3x3 o nueve reinas en un 8x8. Luego, compruebe que su programa no devuelve ninguna solución o lanza la excepción esperada.

¿Quieres probar que una solución dada es válida? Luego, tiene que escribir el código que prueba su validez, y debe ejecutar este código, sin importar lo complejo que sea. Si es lo suficientemente complejo, escribe pruebas para ello también. Si tiene suerte, su programa se puede refaccionar de manera natural para que pueda reutilizar algunas partes más pequeñas de él para probar su solución (está bien reutilizar estas partes más pequeñas, no "presentará el mismo error" porque probó estas partes a fondo también).

Finalmente, una vez que encuentre un error, tendrá un ejemplo de dónde el programa devuelve un resultado inesperado. Escriba una prueba afirmando que no devuelve ese resultado la próxima vez.

No se puede tener una cobertura de prueba del 100% para ningún programa. Todo lo que puede hacer es evaluar los casos que conoce y tener tiempo para escribir.

Hay muchos problemas en los que crear una solución es mucho más difícil que verificar que cualquier solución sea correcta.

En el caso de algo como su problema con las N-reinas, simplemente necesita verificar que solo hay una reina en cada fila y diagonal del tablero y que hay N reinas en el tablero en la solución, para saber que la solución es válida.

Si se sabe que el problema tiene otros algoritmos que funcionan para un conjunto coincidente de entradas, entonces intente ese otro algoritmo para probar su algoritmo original en busca de conjuntos de entradas en las que ambos trabajen. Por ejemplo, una búsqueda de fuerza bruta puede funcionar, o puede ser precalculada y guardada para un rango más pequeño de entradas y utilizada como prueba. En algunos problemas matemáticos, las respuestas para un rango restringido de entradas (como los cuadrados, o potencias de 2, etc.) se verifican más fácilmente. Debes al menos probar para estos casos.