Come faccio a testare unitamente un algoritmo euristico?

Question

Come faccio a testare unitamente un algoritmo euristico?

#1 da (10 voti)
#2 da (3 voti)

9

Supponiamo di avere l'algoritmo di individuazione dei percorsi:

def myHeuristicTSP(graph):
    /*implementation*/
    return route

Ora vogliamo testare questo:

class TestMyHeuristicTSP:
    def testNullGraphRaiseValueError(self):
        self.assertRaises(ValueError, myHueristicTSP(None))

    def testSimpleTwoNodeGraphReturnsRoute:
        self.assertEquals(expectedResult, myHeuristicTSP(input))

La domanda è, per un algoritmo TSP non euristico, possiamo fornire una varietà di grafici e verificare che restituiscano sempre il percorso più breve.

Ma perché un algoritmo heurtistic, mentre è ancora deterministico, è meno prevedibile, sono semplicemente pensati per capire come deve funzionare l'algoritmo e trovare quei casi limite?

unit-testing heuristics

posta dwjohnston 01.01.2015 - 05:12

fonte

2 risposte

3

La maggior parte degli algoritmi di ottimizzazione (inclusa l'euristica) funzionano su alcune configurazioni (nell'esempio un percorso) applicando le operazioni su di esse. Le operazioni per sé dovrebbero garantire di fornire solo configurazioni valide, quindi prima di tutto dovrebbero esserci test unitari per ciascuno di essi. Quando sai con certezza che l'algoritmo di ottimizzazione utilizza solo quelle operazioni, in genere non è necessario un test di validità del risultato dell'algoritmo.

Per creare buoni test unitari per qualsiasi tipo di algoritmo più complesso, è necessario conoscere l'algoritmo stesso in dettaglio . Per euristiche semplici come "hill climbing", in genere è possibile prevedere il risultato per piccoli input. Ad esempio, per i percorsi iniziali da 3 a 5 punti, se assegnati in un determinato ordine, puoi prevedere cosa accadrà. Questo rimarrà vero per la maggior parte degli algoritmi euristici deterministici che conosco, quindi è probabilmente un buon punto di partenza.

Per algoritmi più complessi e dimensioni maggiori dell'input, quando inserisci l'input nell'algoritmo e provi a controllare l'output, non stai più facendo un test unitario, stai facendo test di accettazione o integrazione. Il motivo per cui si hanno problemi a "testare l'unità" come un algo è perché in genere consiste in una manciata di parti più piccole (singole unità). Quindi per un vero test unitario di un tale algoritmo, dovrai identificare quelle parti e testarle individualmente. Inoltre, puoi utilizzare la copertura del codice o le tecniche di copertura delle filiali per assicurarti di avere abbastanza casi di test.

Se non stai cercando test unitari, ma test di accettazione o integrazione automatici, puoi provare ciò che @Phillip suggerito sotto (2) o (3) .

risposta data 01.01.2015 - 10:55

fonte

Leggi altre domande sui tag unit-testing heuristics

Uso di "this" in Golang Perché si chiama Software Configuration Management (SCM)?

score 10 · Accepted Answer

Per un algoritmo euristico che non dovrebbe restituire l'ideale ma una soluzione "abbastanza buona", avresti vari casi di test e controllo

la soluzione è effettivamente valida? Sicuramente vuoi assicurarti che il tuo algoritmo di individuazione dei percorsi non restituisca percorsi che sono impossibili o che in realtà non portano dall'inizio alla fine. Potresti non essere in grado di dimostrare che la soluzione è ideale, ma dovresti almeno essere in grado di verificare che il valore di ritorno sia una soluzione.
la soluzione è "abbastanza buona"? Dovresti avere alcuni requisiti che definiscono quanto peggio può essere l'algoritmo della soluzione ideale. Dovresti avere casi di test in cui è nota la soluzione ideale (o almeno una soluzione che è considerata abbastanza buona da essere utilizzata come standard di confronto) e confermare che la soluzione fornita dall'algoritmo non è superiore al x% peggio.
L'algoritmo è abbastanza veloce? Spesso usi un approccio euristico quando presumi di compensare la loro mancanza di precisione essendo molto più veloce. Per verificare ciò è necessario misurare il loro runtime e assicurarsi che siano effettivamente più veloci di un algoritmo che ottiene la soluzione esatta. Le misure di runtime sono sempre un po 'confuse, quindi il superamento del runtime atteso dovrebbe essere un avvertimento, non un errore (quando il framework di test dell'unità consente di distinguere tra avvisi ed errori).