Algoritmi di test (deterministico) con risposte corrette multiple o difficili da provare

11

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.

    
posta LinearZoetrope 24.04.2014 - 23:52
fonte

2 risposte

5

Non sono sicuro che stai provando a testare la proprietà corretta, e questo causa la tua ambiguità.

Gli algoritmi del grafico non mirano a trovare un percorso più breve (questo è un effetto collaterale), ma a minimizzare o massimizzare alcune funzioni di costo definito sul set di spigoli e vertici. Pertanto, puoi verificare la correttezza di una soluzione testando il valore finale di questa funzionalità e asserendo che il primo e l'ultimo nodo sono quelli effettivamente richiesti.

Se puoi pre-calcolare il valore della funzione di costo finale per ogni possibile percorso (di solito non realistico), devi solo verificare che il costo della soluzione fornita dall'implementazione in prova sia uguale al costo minimo tra questa serie (confronto assoluto). Se hai "solo" un algoritmo e / o implementazione gold standard, dovresti confrontare il costo del suo output con quello dell'algoritmo sotto test (confronto relativo)

Ad esempio, una configurazione di prova ingenua sarebbe:

  1. Calcola tutti i possibili percorsi tra Va e Vb nel grafico di prova con un algoritmo avido.
  2. Calcola la funzione di costo (ad esempio, la lunghezza se tutti i pesi del bordo sono pari a 1) per ciascuno di questi percorsi e trova il valore minimo.
  3. Applica l'algoritmo sotto test.
  4. Fai un'asserzione nel tuo test dell'unità che il valore di costo dell'algoritmo testato sia uguale al minimo delle soluzioni avide.

Se vuoi saperne di più sull'ottimizzazione basata sui grafici, puoi dare un'occhiata alle pubblicazioni di Yuri Boykov qui , anche se in un altro contesto (problemi di Computer Vision).

    
risposta data 29.04.2014 - 08:33
fonte
0

Penso che la risposta diretta alla tua domanda sia scegliere casi di test migliori. Mi chiedo dei casi di test che stai utilizzando. I grafici che usi possono essere grafici CANNED in cui è relativamente facile per un essere umano determinare la risposta attesa. Cerca di capire i casi "edge" che vuoi essere sicuro che il tuo algoritmo gestisca e crei un grafo in scatola per ciascuno dei casi limite che è facile da calcolare per un essere umano. Ad esempio, nel caso dell'algoritmo Djikstra, puoi probabilmente creare grafici 5x5 o 7x7 che coprono tutti i casi limite, anche se il tuo sistema reale potrebbe essere 500x500.

Quindi, come controllo di equilibrio finale, puoi creare un caso di test grafico più realistico o due. Ma in ogni caso, ritengo che sansuiso abbia ragione su dove viene indicato che è necessario essere sicuri di testare la proprietà corretta.

    
risposta data 29.04.2014 - 19:34
fonte

Leggi altre domande sui tag