Powiedzmy, że mamy nasz algorytm znajdowania trasy:
def myHeuristicTSP(graph):
/*implementation*/
return route
Teraz chcemy to przetestować jednostkowo:
class TestMyHeuristicTSP:
def testNullGraphRaiseValueError(self):
self.assertRaises(ValueError, myHueristicTSP(None))
def testSimpleTwoNodeGraphReturnsRoute:
self.assertEquals(expectedResult, myHeuristicTSP(input))
Pytanie brzmi: w przypadku nieheurystycznego algorytmu TSP możemy podać różnorodne wykresy i sprawdzić, czy zawsze zwracają absolutnie najkrótszą trasę.
Ale ponieważ algorytm heurtystyczny, mimo że jest deterministyczny, jest mniej przewidywalny, ma po prostu zrozumieć, w jaki sposób algorytm ma działać, i znaleźć te przypadki brzegowe?
unit-testing
heuristics
dwjohnston
źródło
źródło
Odpowiedzi:
W przypadku algorytmu heurystycznego, który ma nie zwracać idealnego, ale „wystarczająco dobrego” rozwiązania, masz różne przypadki testowe i sprawdzasz
źródło
Większość algorytmów optymalizacyjnych (w tym heurystyk) działa w niektórych konfiguracjach (w twoim przykładzie na trasie) poprzez zastosowanie na nich operacji. Operacje same w sobie powinny gwarantować, że dostarczają tylko prawidłowe konfiguracje, więc najpierw powinny być testy jednostkowe dla każdej z nich. Gdy wiesz na pewno, że algorytm optymalizacji korzysta tylko z tych operacji, zazwyczaj nie powinno być potrzeby sprawdzania poprawności wyniku algorytmu.
Aby utworzyć dobre testy jednostkowe dla każdego rodzaju bardziej złożonego algorytmu, jeden rzeczywiście musi znać algorytm sam w szczegółach . W przypadku prostych heurystyk, takich jak „wspinaczka pod górę”, zwykle można przewidzieć wynik dla niewielkich nakładów. Na przykład dla początkowych tras od 3 do 5 punktów, jeśli podane w określonej kolejności, możesz przewidzieć, co się stanie. To pozostanie prawdziwe w przypadku większości deterministycznych algorytmów heurystycznych, które znam, więc prawdopodobnie jest to dobre miejsce na rozpoczęcie.
W przypadku bardziej złożonych algorytmów i większego rozmiaru danych wejściowych, po prostu wprowadzasz dane wejściowe do algorytmu i próbujesz sprawdzić dane wyjściowe, w rzeczywistości nie wykonujesz już testów jednostkowych, przeprowadzasz test akceptacyjny lub integracyjny. Powodem, dla którego masz problemy z „testowaniem jednostki” takiego algo, jest to, że zazwyczaj składa się on z garści mniejszych części (pojedynczych jednostek). Tak więc, aby naprawdę przetestować taki algorytm, będziesz musiał zidentyfikować te części i przetestować je indywidualnie. Ponadto można użyć technik pokrycia kodu lub technik pokrycia gałęzi, aby upewnić się, że masz wystarczającą liczbę przypadków testowych.
Jeśli nie szukasz testów jednostkowych, ale automatycznych testów akceptacyjnych lub integracyjnych, możesz wypróbować sugestie @Phillip pod (2) lub (3) .
źródło