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

11

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.

LinearZoetrope
źródło
3
Jeśli język na to pozwala można udowodnić prawidłowość zamiast testowania go
miniBill
Jest dużo tekstu, ale nie ma wątpliwości. O co dokładnie pytasz?
BЈовић
@ BЈовић „Jak powinienem testować implementacje algorytmów z wieloma i / lub trudnymi do zweryfikowania poprawnymi danymi wyjściowymi?” Przepraszam, nie jestem pewien, jak to wyjaśnić. Przyznaję, że można go uznać za nieco szeroki w zależności od twojej perspektywy, ale nie sądzę, że jest niezdefiniowany.
LinearZoetrope
Nadal nie rozumiem. Twój algorytm nie zależy od losowości, a mimo to może generować różne wyniki. To w ogóle nie ma sensu. Każdy algorytm dla ustawionych danych wejściowych musi mieć takie same dane wyjściowe. I to jest zrobione i przetestowane w testach jednostkowych. Nawet algorytm w dokumencie, który połączyłeś.
BЈовић
@ BЈовић Oczywiście, jest deterministyczny, ale jest również bardzo wrażliwy, np. Na kolejność, w jakiej wykres zwraca następców węzła. Może powodować efekt motyla. To, czy wypchniesz wierzchołek A na stos przed wierzchołkiem B, doprowadzi do innego wyjścia, jeśli oba doprowadzą do najkrótszej ścieżki. Korzystanie z funkcji bibliotecznych, takich jak sortowanie niestabilne lub minimalne sterty, tylko pogarsza problem.
LinearZoetrope

Odpowiedzi:

5

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).

sansuiso
źródło
Głosowałem, ale poczekam chwilę na zaakceptowanie. Jest to „test cech poprawnej odpowiedzi”, o którym wspomniałem w pytaniu. Problem zawsze polega na upewnieniu się, że weryfikujesz właściwą rzecz. Na przykład od razu sprawdzałem zwracany koszt i upewniłem się, że ścieżka jest poprawna. Oczywiście ścieżka była ważna! To był tylko węzeł początkowy! Musiałem więc zmodyfikować testy, aby upewnić się, że sama ścieżka rzeczywiście zwróciła prawidłowy koszt. Głupi błąd, jasne, ale im więcej interakcji ma ten wynik, tym bardziej prawdopodobne.
LinearZoetrope
@Jsor, z mojego punktu widzenia, jest to korzyść z ciągłego doskonalenia testowania: na początku nie można ustalić wszystkich właściwości poprawności rozwiązania, a potem popaść w błąd, poprawić test i tak dalej.
sansuiso
Ta odpowiedź zaleca testowanie pod kątem cech poprawnej odpowiedzi, ale ważne jest, aby wybrać, które cechy są dobrym testem. W tym przykładzie sprawdzenie, czy odpowiedź jest ścieżką od A do B i czy funkcja kosztu jest równa wartości minimalnej, daje dwa kryteria, które spełnią wszystkie poprawne odpowiedzi, a żadne nieprawidłowe odpowiedzi nie spełnią obu kryteriów. Gdyby ta odpowiedź nie została już udzielona, ​​zaleciłbym coś podobnego. Trzeba przyznać, że często nie jest łatwo ustalić, które cechy należy przetestować.
David K
0

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ść.

Maczać
źródło