Wie teste ich einen heuristischen Algorithmus?

Angenommen, wir haben unseren Routenfindungsalgorithmus:

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

Jetzt wollen wir dies testen:

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

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

Die Frage ist, dass wir für einen nicht heuristischen TSP-Algorithmus eine Vielzahl von Diagrammen angeben und überprüfen können, ob sie immer den absolut kürzesten Weg zurückgeben.

Aber weil ein heurtistischer Algorithmus, obwohl er noch deterministisch ist, weniger vorhersehbar ist, soll er einfach verstehen, wie der Algorithmus funktionieren soll, und diese Randfälle finden?

Für einen heuristischen Algorithmus, der nicht das Ideal, sondern eine "gut genug" -Lösung zurückgeben soll, hätten Sie verschiedene Testfälle und prüfen

1. Ist die Lösung tatsächlich gültig? Sie möchten auf jeden Fall sicherstellen, dass Ihr Routenfindungsalgorithmus keine Pfade zurückgibt, die unmöglich sind oder nicht von Anfang bis Ende führen. Sie könnten in der Lage zu beweisen , nicht , dass die Lösung ideal ist, aber man sollte zumindest zu überprüfen , die Lage sein , dass der Rückgabewert tatsächlich ist eine Lösung.
2. ist die Lösung "gut genug"? Sie sollten einige Anforderungen haben, die definieren, wie viel schlechter der Algorithmus sein kann als die ideale Lösung. Sie sollten Testfälle haben, in denen die ideale Lösung bekannt ist (oder zumindest eine Lösung, die als gut genug angesehen wird, um als Vergleichsstandard verwendet zu werden) und bestätigen, dass die vom Algorithmus bereitgestellte Lösung nicht mehr als x% schlechter ist.
3. Ist der Algorithmus schnell genug? Sie verwenden häufig einen heuristischen Ansatz, wenn Sie davon ausgehen, dass sie ihre mangelnde Präzision ausgleichen, indem sie viel schneller sind. Um dies zu überprüfen, sollten Sie ihre Laufzeit messen und sicherstellen, dass sie tatsächlich schneller sind als ein Algorithmus, der die genaue Lösung erhält. Laufzeitmessungen sind immer etwas unscharf, daher sollte das Überschreiten der erwarteten Laufzeit eine Warnung und kein Fehler sein (wenn Ihr Unit-Test-Framework zulässt, dass zwischen Warnungen und Fehlern unterschieden wird).

Die meisten Optimierungsalgorithmen (einschließlich Heuristiken) arbeiten mit einigen Konfigurationen (in Ihrem Beispiel einer Route), indem sie Operationen auf sie anwenden. Die Operationen für sich sollten sicherstellen, dass sie nur gültige Konfigurationen liefern, daher sollten zuerst Unit-Tests für jede von ihnen durchgeführt werden. Wenn Sie sicher sind, dass der Optimierungsalgorithmus nur diese Operationen verwendet, sollte normalerweise kein Gültigkeitstest für das Ergebnis des Algorithmus erforderlich sein.

Um gute Komponententests für jede Art von komplexerem Algorithmus zu erstellen, muss man den Algorithmus selbst im Detail kennen . Für einfache Heuristiken wie "Bergsteigen" können Sie normalerweise das Ergebnis für kleine Eingaben vorhersagen. Beispielsweise können Sie für anfängliche Routen mit 3 bis 5 Punkten in einer bestimmten Reihenfolge vorhersagen, was passieren wird. Dies gilt für die meisten mir bekannten deterministischen heuristischen Algorithmen. Das ist also wahrscheinlich ein guter Anfang.

Bei komplexeren Algorithmen und einer größeren Größe der Eingabe führen Sie, wenn Sie nur die Eingabe in den Algorithmus einspeisen und versuchen, die Ausgabe zu überprüfen, keinen Komponententest mehr durch, sondern einen Akzeptanz- oder Integrationstest. Der Grund, warum Sie Probleme haben, einen solchen Algorithmus zu "testen", liegt darin, dass er normalerweise aus einer Handvoll kleinerer Teile (einzelne Einheiten) besteht. Um einen solchen Algorithmus wirklich in Einheiten zu testen, müssen Sie diese Teile identifizieren und einzeln testen. Darüber hinaus können Sie Codeabdeckungs- oder Zweigabdeckungstechniken verwenden, um sicherzustellen, dass Sie über genügend Testfälle verfügen.

Wenn Sie nicht nach Unit-Tests, sondern nach automatisierten Akzeptanz- oder Integrationstests suchen, können Sie versuchen, was @Phillip unter (2) oder (3) vorgeschlagen hat .