Testowanie (deterministycznych) algorytmów z wieloma lub trudnymi do udowodnienia poprawnymi poprawnymi odpowiedziami

Chciałbym uprzedzić, że to pytanie jest podobne, ale moje pytanie nie dotyczy przypadkowości, tylko wybredny determinizm, więc odpowiedź „użyj znanego nasienia” tak naprawdę nie ma zastosowania. Podobnie, to pytanie jest podobne, ale znowu nie oczekuję, że algorytm kiedykolwiek zawiedzie - po prostu nie wiem, w którą stronę będzie poprawny.

To pytanie pojawiło się podczas testowania algorytmów grafowych. ale nie ogranicza się do nich. Niektóre algorytmy, takie jak A *, mogą mieć wiele poprawnych odpowiedzi. W zależności od dokładnej implementacji możesz uzyskać jedną z kilku odpowiedzi, z których każda jest jednakowo poprawna. Może to jednak utrudnić ich przetestowanie, ponieważ nie wiadomo, który z nich wypluje z wyprzedzeniem, a ręczne obliczenie odpowiedzi zajmuje dużo czasu.

W moim konkretnym przypadku udało mi się to obejść, modyfikując Floyd-Warshall, aby wypluł każdą możliwą najkrótszą ścieżkę, i spędziłem czas na testowaniu tego. Miał tę zaletę, że sam w sobie był dobrą cechą. Następnie mógłbym przetestować inne funkcje pod kątem znanych poprawnych ścieżek z FW (jeśli zwrócona ścieżka jest jedną ze ścieżek zwróconych przez FW dla tej pary początkowej / końcowej, jest poprawna). Oczywiście działa to tylko w przypadku gęstych wykresów ze względu na działanie FW, ale nadal jest przyjemne.

Jednak nie zawsze może to być wykonalne dla wszystkich algorytmów o tej charakterystyce. Jak dotąd najlepszą odpowiedzią, jaką wymyśliłem, jest sprawdzenie właściwości poprawnej odpowiedzi, a nie samej odpowiedzi. Aby wrócić do algorytmów najkrótszej ścieżki, możesz sprawdzić koszt zwróconej ścieżki w stosunku do znanego właściwego kosztu i upewnić się, że ścieżka jest poprawna.

Działa to, ale może wiązać się z ryzykiem niepoprawnej weryfikacji wszystkiego, tym więcej kryteriów poprawności istnieje, szczególnie jeśli sama weryfikacja jest złożona (np. Gdy istnieją prawidłowe algorytmy , weryfikacja minimalnego drzewa opinającego jest znanym trudnym problemem; prawdopodobnie trudniejszym niż konstruowanie samego MST), w takim przypadku musisz teraz dokładnie przetestować kod testowy. Gorzej: prawdopodobnie musisz zbudować MST, aby przetestować algorytm weryfikacji MST, więc masz teraz świetny scenariusz, w którym test MST opiera się na działającym algorytmie weryfikacji MST, a test algorytmu weryfikacji MST opiera się na działającym kodzie generowania MST.

Wreszcie istnieje „tani sposób”, który polega na obserwowaniu wyników, ręcznej weryfikacji, a następnie na twardym kodowaniu testu w celu przetestowania właśnie zweryfikowanego wyniku, ale nie jest to świetny pomysł, ponieważ może za każdym razem trzeba będzie zmieniać test zmień nieco implementację (czego powinno unikać automatyczne testowanie).

Oczywiście odpowiedź zależy od dokładnego algorytmu, który testujesz w pewnym stopniu, ale zastanawiałem się, czy istnieją jakieś „najlepsze praktyki” w zakresie weryfikacji algorytmów, które mają kilka określonych, deterministycznych „poprawnych” wyników, ale te dokładne poprawne wyniki są trudne wiedzieć z wyprzedzeniem i być może nawet trudny do zweryfikowania po fakcie.

Nie jestem pewien, czy próbujesz przetestować poprawną właściwość, a to powoduje twoją dwuznaczność.

Algorytmy grafowe nie mają na celu znalezienia najkrótszej ścieżki (jest to efekt uboczny), ale zminimalizowanie lub zmaksymalizowanie niektórych funkcji kosztów zdefiniowanych na zbiorze krawędzi i wierzchołków. W ten sposób możesz sprawdzić poprawność rozwiązania, testując końcową wartość tej funkcji i stwierdzając, że pierwszy i ostatni węzeł są tymi rzeczywiście wymaganymi.

Jeśli możesz wstępnie obliczyć końcową wartość funkcji kosztu dla każdej możliwej ścieżki (zwykle nierealistycznej), wystarczy sprawdzić, czy koszt rozwiązania dostarczonego przez testowaną implementację jest równy minimalnemu kosztowi w tym zestawie (porównanie bezwzględne ). Jeśli „po prostu” masz algorytm i / lub implementację złotego standardu, powinieneś porównać koszt jego wyniku z testowanym algorytmem (porównanie względne)

Na przykład, naiwną konfiguracją testową byłoby:

1. Obliczyć wszystkie możliwe ścieżki między Va i Vb na wykresie testowym za pomocą chciwego algorytmu.
2. Oblicz funkcję kosztu (na przykład długość, jeśli wszystkie wagi krawędzi są równe 1) dla każdej z tych ścieżek i znajdź wartość minimalną.
3. Zastosuj testowany algorytm.
4. W teście jednostkowym stwierdź, że wartość kosztu testowanego algorytmu jest równa minimum chciwych rozwiązań.

Jeśli chcesz dowiedzieć się więcej na temat optymalizacji opartej na grafach, zapoznaj się z publikacjami Jurija Bojkowa tutaj , choć w innym kontekście (problemy z widzeniem komputerowym).

Myślę, że bezpośrednią odpowiedzią na twoje pytanie jest wybór lepszych przypadków testowych. Zastanawiam się, jakich przypadków testowych używasz. Wykresy, których używasz, mogą być wykresami CANNED, w których człowiek jest stosunkowo łatwy do określenia oczekiwanej odpowiedzi. Spróbuj znaleźć przypadki „krawędzi”, które chcesz mieć pewność, że Twój algorytm sobie poradzi, i utwórz stały wykres dla każdego konkretnego przypadku krawędzi, który jest łatwy do obliczenia przez człowieka. Na przykład, w przypadku algorytmu Djikstry, prawdopodobnie możesz utworzyć wykresy 5x5 lub 7x7, które obejmują wszystkie twoje przypadki brzegowe, nawet jeśli twój rzeczywisty system może mieć wymiary 500x500.

Następnie, jako ostateczny test poczytalności, możesz stworzyć bardziej realistyczny testowy wykres lub dwa. Ale w każdym razie myślę, że sansuiso ma miejsce, w którym wskazano, że musisz upewnić się, że testujesz poprawną właściwość.