Tester des algorithmes (déterministes) avec des réponses correctes multiples ou difficiles à prouver

Je voudrais faire précéder ceci que cette question est similaire, mais ma question n'implique pas le hasard, juste un déterminisme capricieux, donc la réponse de "utiliser une graine connue" ne s'applique pas vraiment. De même, cette question est similaire, mais encore une fois, je ne m'attends pas à ce que l'algorithme échoue jamais - je ne sais tout simplement pas de quelle manière il sera correct.

Cette question est survenue lors du test des algorithmes de graphes. mais n'y est nullement limité. Certains algorithmes tels que A * peuvent avoir plusieurs réponses correctes. En fonction de votre implémentation exacte, vous pouvez obtenir l'une des réponses, chacune étant également correcte. Cependant, cela peut les rendre difficiles à tester, car vous ne savez pas lequel il va cracher à l'avance, et il faut beaucoup de temps pour calculer les réponses à la main.

Dans mon cas spécifique, je l'ai contourné en modifiant Floyd-Warshall pour cracher tous les chemins les plus courts possibles , et j'ai passé le temps à tester cela. Elle avait l'avantage d'être une bonne caractéristique à part entière. Ensuite, je pourrais tester d'autres fonctions en termes de chemins corrects connus de FW (si le chemin retourné est l'un des chemins retournés par FW pour cette paire de début / fin, c'est correct). Bien sûr, cela ne fonctionne que pour les graphiques denses en raison du fonctionnement de FW, mais c'est toujours agréable.

Cependant, cela peut ne pas toujours être viable pour tous les algorithmes avec cette caractéristique. Jusqu'à présent, la meilleure réponse que j'ai trouvée est de tester les caractéristiques d'une bonne réponse, plutôt que la bonne réponse elle-même. Pour revenir aux algorithmes de chemin le plus court, vous pouvez vérifier le coût du chemin renvoyé par rapport au bon coût connu et vous assurer que le chemin est valide.

Cela fonctionne, mais cela peut courir le risque de ne pas tout vérifier correctement plus il y a de critères de correction, surtout si la vérification est elle-même complexe (par exemple, alors qu'il existe des algorithmes corrects , la vérification d'un arbre couvrant minimum est un problème difficile connu; probablement plus difficile que construction du MST lui-même), auquel cas vous devez maintenant tester en profondeur votre code de test. Pire: vous devez probablement construire un MST pour tester un algorithme de vérification MST, vous avez donc maintenant un excellent scénario dans lequel votre test MST repose sur le fonctionnement de votre algorithme de vérification MST, et votre test d'algorithme de vérification MST repose sur le fonctionnement de votre code de génération MST.

Enfin, il y a la "méthode bon marché", qui consiste à observer la sortie, à la vérifier à la main, puis à coder en dur le test pour tester la sortie que vous venez de vérifier, mais ce n'est pas une bonne idée car vous devrez peut-être réviser le test à chaque fois que vous changer un peu l'implémentation (ce que les tests automatisés sont censés éviter).

Évidemment, la réponse dépend de l'algorithme exact que vous testez dans une certaine mesure, mais je me demandais s'il y avait des "meilleures pratiques" pour vérifier les algorithmes qui ont plusieurs sorties "correctes" déterminées et déterministes, mais ces sorties correctes précises sont difficiles à savoir à l'avance, et peut-être même difficile à vérifier après coup.

Je ne suis pas sûr que vous essayez de tester la propriété correcte, ce qui crée votre ambiguïté.

Les algorithmes graphiques ne visent pas à trouver le chemin le plus court (c'est un effet secondaire), mais à minimiser ou maximiser une fonction de coût définie sur l'ensemble des arêtes et des sommets. Ainsi, vous pouvez vérifier l'exactitude d'une solution en testant la valeur finale de cette fonction et en affirmant que les premier et dernier nœuds sont ceux réellement requis.

Si vous pouvez pré-calculer la valeur finale de la fonction de coût pour chaque chemin possible (généralement irréaliste), il vous suffit de vérifier que le coût de la solution fournie par l'implémentation sous test est égal au coût minimum parmi cet ensemble (comparaison absolue ). Si vous avez "juste" un algorithme et / ou une implémentation de référence, alors vous devez comparer le coût de sa sortie avec celui de l'algorithme testé (comparaison relative)

Par exemple, une configuration de test naïf serait:

1. Calculez tous les chemins possibles entre Va et Vb dans le graphique de test avec un algorithme gourmand.
2. Calculez la fonction de coût (par exemple, la longueur si tous vos poids de bordure sont égaux à 1) pour chacun de ces chemins et trouvez la valeur minimale.
3. Appliquez l'algorithme testé.
4. Faites une affirmation dans votre test unitaire que la valeur de coût de l'algorithme testé est égale au minimum des solutions gourmandes.

Si vous souhaitez en savoir plus sur l'optimisation basée sur les graphiques, vous pouvez consulter les publications de Yuri Boykov ici , bien que dans un autre contexte (problèmes de vision par ordinateur).

Je pense que la réponse directe à votre question est de choisir de meilleurs cas de test. Je me pose des questions sur les cas de test que vous utilisez. Les graphiques que vous utilisez peuvent être des graphiques EN CONSERVE où il est relativement facile pour un humain de déterminer la réponse attendue. Essayez de comprendre les cas «de bord» que vous voulez être sûr que votre algorithme gère et créez un graphique prédéfini pour chacun des cas de bord particuliers qui est facile à calculer pour un humain. Par exemple, dans le cas de l'algorithme Djikstra, vous pouvez probablement créer des graphiques 5x5 ou 7x7 qui couvrent tous vos cas de bord, même si votre système réel peut être 500x500.

Ensuite, en guise de vérification finale, vous pouvez créer un ou deux cas de test de graphique plus réalistes. Mais en tout état de cause, je pense que sansuiso a l'endroit où il est souligné que vous devez être sûr de tester la bonne propriété.