Vorrei premettere che la domanda è simile, ma la mia domanda non riguarda la casualità, solo il determinismo schizzinoso, quindi la risposta di "usare un seme conosciuto" non si applica realmente. Allo stesso modo, questa domanda è simile, ma ancora una volta, non lo sono aspettandomi che l'algoritmo fallisse mai, semplicemente non so da che parte sarà corretto.
Questa domanda è nata durante il test degli algoritmi del grafico. ma non è affatto limitato a loro. Alcuni algoritmi come A * possono avere più risposte corrette. A seconda dell'implementazione esatta, è possibile ottenere una delle varie risposte, ognuna delle quali è ugualmente corretta. Questo può renderli difficili da testare, però, perché non sai quale sputare fuori prima del tempo, ed è molto dispendioso in termini di tempo calcolare le risposte a mano.
Nel mio caso specifico, mi sono aggirato modificando Floyd-Warshall per sputare ogni possibile percorso più breve, e ho passato il tempo a provarlo. Aveva il vantaggio di essere una buona caratteristica di per sé. Quindi potrei testare altre funzioni in termini di percorsi conosciuti corretti da FW (se il percorso restituito è uno qualsiasi dei percorsi restituiti da FW per quella coppia start / end, è corretto). Naturalmente, questo funziona solo per grafici densi a causa di come funziona FW, ma è comunque bello.
Tuttavia, potrebbe non essere sempre fattibile per tutti gli algoritmi con questa caratteristica. Finora, la risposta migliore che ho trovato è quella di testare le caratteristiche di una risposta corretta, piuttosto che la risposta corretta stessa. Per tornare agli algoritmi del percorso più breve, puoi verificare il costo del percorso restituito rispetto al costo corretto noto e assicurarti che il percorso sia valido.
Funziona, ma può correre il rischio di non verificare tutto correttamente più ci sono criteri di correttezza, specialmente se la verifica è di per sé complessa (ad esempio mentre esistono algoritmi corretti , la verifica di un albero spanning minimo è un problema noto, probabilmente più difficile della costruzione del MST stesso), nel qual caso ora devi testare estesamente il tuo codice di prova. Peggio: presumibilmente devi costruire un MST per testare un algoritmo di verifica MST in modo da avere un ottimo scenario in cui il test MST si basa sull'algoritmo di verifica MST funzionante e il test dell'algoritmo di verifica MST si basa sul funzionamento del codice MST.
Infine, c'è il "metodo economico", che implica l'osservazione dell'output, verificandolo a mano, quindi l'hard coding del test per testare l'output appena verificato, ma non è una grande idea dato che potrebbe essere necessario rivedere il test ogni volta che cambi leggermente l'implementazione (che è ciò che si suppone che il test automatico eviti).
Ovviamente la risposta dipende dall'algoritmo che stai testando fino a un certo punto, ma mi chiedevo se ci fossero delle "migliori pratiche" per verificare gli algoritmi che hanno diversi output "corretti" definiti deterministici, ma quegli esatti output corretti sono difficili da sapere in anticipo, e forse anche difficile da verificare dopo il fatto.