Prueba de algoritmos (deterministas) con respuestas correctas múltiples o difíciles de probar correctas

Prefiero decir que esta pregunta es similar, pero mi pregunta no implica aleatoriedad, solo determinismo quisquilloso, por lo que la respuesta de "usar una semilla conocida" no se aplica realmente. Del mismo modo, esta pregunta es similar, pero de nuevo, no espero que el algoritmo falle nunca, simplemente no sé de qué manera será correcto.

Esta pregunta surgió al probar algoritmos gráficos. pero de ninguna manera se limita a ellos. Algunos algoritmos como A * pueden tener múltiples respuestas correctas. Dependiendo de su implementación exacta, puede obtener cualquiera de varias respuestas, cada una de las cuales es igualmente correcta. Sin embargo, esto puede hacer que sean difíciles de probar, porque no sabes cuál va a escupir con anticipación, y es muy lento calcular las respuestas a mano.

En mi caso específico, lo solucioné modificando Floyd-Warshall para escupir cada camino más corto posible , y pasé el tiempo probando eso. Tenía el beneficio de ser una buena característica por derecho propio. Entonces podría probar otras funciones en términos de las rutas correctas conocidas de FW (si la ruta devuelta es cualquiera de las rutas devueltas por FW para ese par de inicio / final, es correcta). Por supuesto, esto solo funciona para gráficos densos debido a cómo funciona FW, pero sigue siendo agradable.

Sin embargo, eso no siempre es viable para todos los algoritmos con esta característica. Hasta ahora, la mejor respuesta que he encontrado es probar las características de una respuesta correcta, en lugar de la respuesta correcta en sí. Para volver a los algoritmos de ruta más corta, puede verificar el costo de la ruta devuelta contra el costo correcto conocido y asegurarse de que la ruta sea válida.

Esto funciona, pero puede correr el riesgo de no verificar todo correctamente mientras haya más criterios de corrección, especialmente si la verificación en sí misma es compleja (por ejemplo, mientras existan algoritmos correctos , verificar un árbol de expansión mínimo es un problema difícil conocido; probablemente más difícil que construir el propio MST), en cuyo caso ahora debe probar exhaustivamente su código de prueba. Peor aún: presumiblemente tiene que construir un MST para probar un algoritmo de verificación MST, por lo que ahora tiene un gran escenario en el que su prueba MST se basa en el funcionamiento de su algoritmo de verificación MST, y su prueba del algoritmo de verificación MST se basa en su código de generación MST funcionando.

Finalmente, está la "forma barata", que consiste en observar la salida, verificarla a mano, luego codificar la prueba para probar la salida que acaba de verificar, pero esa no es una gran idea ya que es posible que tenga que revisar la prueba cada vez que cambiar un poco la implementación (que es lo que se supone que deben evitar las pruebas automatizadas).

Obviamente, la respuesta depende del algoritmo exacto que esté probando hasta cierto punto, pero me preguntaba si había alguna "mejor práctica" para verificar los algoritmos que tienen varias salidas definidas y deterministas "correctas", pero esas salidas correctas precisas son difíciles de saber de antemano, y posiblemente difícil de verificar incluso después del hecho.

No estoy seguro de que esté intentando probar la propiedad correcta, y esto causa su ambigüedad.

Los algoritmos de gráficos no tienen como objetivo encontrar el camino más corto (esto es un efecto secundario), sino minimizar o maximizar alguna función de costo definida en el conjunto de bordes y vértices. Por lo tanto, puede verificar la corrección de una solución probando el valor final de esta función y afirmando que el primer y el último nodo son los realmente necesarios.

Si puede calcular previamente el valor de la función de costo final para cada ruta posible (generalmente poco realista), entonces solo tiene que verificar que el costo de la solución proporcionada por la implementación bajo prueba es igual al costo mínimo entre este conjunto (comparación absoluta ) Si "solo" tiene un algoritmo y / o implementación estándar de oro, entonces debe comparar el costo de su salida con el del algoritmo bajo prueba (comparación relativa)

Por ejemplo, una configuración de prueba ingenua sería:

1. Calcule todas las rutas posibles entre Va y Vb en el gráfico de prueba con un algoritmo codicioso.
2. Calcule la función de costo (por ejemplo, la longitud si todos sus pesos de borde son iguales a 1) para cada una de estas rutas y encuentre el valor mínimo.
3. Aplicar el algoritmo bajo prueba.
4. Haga una afirmación en su prueba unitaria de que el valor de costo del algoritmo probado es igual al mínimo de las soluciones codiciosas.

Si desea saber más sobre la optimización basada en gráficos, puede echar un vistazo a las publicaciones de Yuri Boykov aquí , aunque en otro contexto (problemas de visión por computadora).

Creo que la respuesta directa a su pregunta es elegir mejores casos de prueba. Me pregunto sobre los casos de prueba que está utilizando. Las gráficas que utiliza pueden ser gráficas CANNED donde es relativamente fácil para un humano determinar la respuesta esperada. Intente descubrir los casos de "borde" que desea asegurarse de que su algoritmo maneja y cree un gráfico fijo para cada uno de los casos de borde particulares que sea fácil de calcular para un humano. Por ejemplo, en el caso del algoritmo Djikstra, probablemente pueda crear algunos gráficos de 5x5 o 7x7 que cubran todos sus casos límite, a pesar de que su sistema real podría ser 500x500.

Luego, como comprobación final de cordura, puede crear un caso de prueba de gráfico más realista o dos. Pero en cualquier caso, creo que sansuiso tiene claro dónde debe señalarse que debe asegurarse de que está probando la propiedad correcta.