Kiedy mówi się, że dwa algorytmy są „podobne”?

Nie pracuję w teorii, ale moja praca wymaga od czasu do czasu czytania (i rozumienia) prac teoretycznych. Kiedy zrozumiem (zestaw) wyników, omawiam je z ludźmi, z którymi pracuję, z których większość również nie działa w teorii. Podczas jednej z takich dyskusji pojawiło się następujące pytanie:

Kiedy mówi się, że dwa podane algorytmy są „podobne”?

Co rozumiem przez „podobny”? Powiedzmy, że dwa algorytmy są podobne do siebie, jeśli można złożyć jedno z poniższych oświadczeń w dokumencie bez mylenia / irytującego recenzenta (mile widziane lepsze definicje):

Twierdzenie 1. „Algorytm , który jest podobny do algorytmu B , rozwiązuje również problem X ”$A$$B$$X$

Twierdzenie 2. „Nasz algorytm jest podobny do algorytmu ”$C$

Pozwólcie, że uczynię to nieco bardziej szczegółowym. Załóżmy, że pracujemy z algorytmami graficznymi. Najpierw niektóre niezbędne warunki, aby oba algorytmy były podobne:

1. Muszą rozwiązać ten sam problem.
2. Muszą mieć ten sam intuicyjny pomysł na wysokim poziomie.

Na przykład, mówiąc o przejściu przez wykres, przejściu przez pierwszą szerokość i głębokość pierwsze spełniają powyższe dwa warunki; dla obliczeń najkrótszej ścieżki, szerokość i algorytm Dijkstry spełniają powyższe dwa warunki (oczywiście na nieważonych grafach); itp.

Czy te warunki są wystarczające? Mówiąc dokładniej, załóżmy, że dwa algorytmy spełniają niezbędne warunki, aby być podobne. Czy rzeczywiście nazwałbyś ich podobnie?

1. mają inną asymptotyczną wydajność?
2. dla szczególnej klasy wykresy, jeden algorytm wymaga czas, podczas gdy drugi wymaga O ( n 1 / 3 ) czas?$\Omega(n)$$O(n^{1/3})$
3. mają różne warunki zakończenia? (pamiętaj, rozwiązują ten sam problem)
4. etap wstępnego przetwarzania różni się w dwóch algorytmach?
5. złożoność pamięci jest różna w dwóch algorytmach?

Edycja: Pytanie wyraźnie zależy od kontekstu i jest subiektywne. Miałem nadzieję, że powyższe pięć warunków pozwoli na uzyskanie pewnych sugestii. Z przyjemnością zmodyfikuję pytanie i podam więcej szczegółów, jeśli zajdzie potrzeba uzyskania odpowiedzi. Dzięki!

Trudno jest podać nawet spójną definicję „Algorytmu A jest podobny do algorytmu B”. Po pierwsze, nie uważam, że „muszą rozwiązać ten sam problem” jest warunkiem koniecznym. Często, gdy ktoś mówi w artykule, że „algorytm z Twierdzenia 2 jest podobny do algorytmu B w Twierdzeniu 1 ”, algorytm A faktycznie rozwiązuje inny problem niż ten z B , ale ma pewne drobne modyfikacje, aby poradzić sobie z nowym problemem .$A$$2$$B$$1$$A$$B$

Ciekawym i trudnym problemem jest nawet próba ustalenia, co to znaczy, że dwa algorytmy są takie same . Zobacz artykuł „Kiedy dwa algorytmy są takie same?” http://research.microsoft.com/~gurevich/Opera/192.pdf

Częściej niż nie oznacza to, że „nie chcę szczegółowo zapisywać algorytmu B, ponieważ wszystkie interesujące szczegóły są prawie identyczne jak te w algorytmie A i nie chcę przekraczać limitu 10 stron, a mimo to termin przesyłania jest za trzy godziny. ”

Jeśli masz na myśli „podobny” w znaczeniu potocznym, myślę, że odpowiedź Jeffa wyraża to, co mają na myśli niektórzy ludzie.

W sensie technicznym zależy to od tego, na czym ci zależy. Jeśli zależy Ci na asymptotycznej złożoności czasu, różnica między rekurencją a iteracją może nie mieć znaczenia. Jeśli zależy ci na obliczalności, różnica między zmienną licznika a stosem jednego symbolu nie ma znaczenia.

Aby porównać algorytmy, pierwszym krokiem byłoby doprecyzowanie pojęcia równoważności. Intuicyjnie pozwolić się przestrzeń algorytmów i M jest przestrzeń obiektów matematycznych i s e m : → M być kodowanie funkcja y e m ( P ), to znaczy algorytmu P . Przestrzeń M może zawierać wszystko, od liczby zmiennych w algorytmie, po wykres stanu lub złożoność czasową. Nie wierzę, że istnieje absolutne pojęcie, czym może być M. Biorąc pod uwagę M.$A$$M$$\mathit{sem}: A \to M$$\mathit{sem}(P)$$P$$M$$M$$M$możemy jednak powiedzieć, że dwa algorytmy są równoważne, jeżeli jest równe s e m ( Q ) . Dodam, że uważam, że każde z pięciu wspomnianych kryteriów można sformalizować matematycznie w ten sposób.$\mathit{sem}(P)$$\mathit{sem}(Q)$

Jeśli chcemy mówić o algorytmie bardziej ogólnym niż inny (lub algorytmie udoskonalającym inny), nadałbym większą strukturę. Wyobraź sobie, że ( M , ⊑ ) jest zbiorem częściowo uporządkowanym, a kolejność x ⊑ y koduje, że x jest bardziej zdefiniowanym obiektem niż y . Na przykład, jeżeli M zawiera zestaw śladów algorytmu i ⊑ jest ustawiony integracji, a e m ( P ) ⊑ s e m ( P ) oznacza, że każdy ślad $M$$(M, \sqsubseteq)$$x \sqsubseteq y$$x$$y$$M$$\sqsubseteq$$\mathit{sem}(P) \sqsubseteq \mathit{sem}(Q)$$P$jest śladem . Możemy interpretować to jak mówienie, że P jest bardziej deterministyczna niż Q .$Q$$P$$Q$

Następnie możemy zapytać, czy możliwe jest oszacowanie, jak blisko są dwa algorytmy. W tym przypadku wyobrażam sobie, że musi być wyposażony w miarę. Następnie możemy zmierzyć odległość między obiektami matematycznymi reprezentowanymi przez dwa algorytmy. Dalsze możliwości to mapowanie algorytmów do pomiaru przestrzeni lub przestrzeni prawdopodobieństwa i porównywanie ich przy użyciu innych kryteriów.$M$

Mówiąc bardziej ogólnie, zapytam - na czym Ci zależy (w kategoriach intuicyjnych), jakie są matematyczne obiekty reprezentujące te intuicyjne właściwości, jak mogę mapować z algorytmów na te obiekty i jaka jest struktura tej przestrzeni? Zapytałbym także, czy przestrzeń obiektów ma wystarczającą strukturę, aby przyjąć pojęcie podobieństwa. Takie podejście przyjąłbym z perspektywy semantyki języka programowania. Nie jestem pewien, czy uważasz to podejście za atrakcyjne, biorąc pod uwagę bardzo różne kultury myśli w informatyce.

Zgodnie z odpowiedzią Jeffa dwa algorytmy są podobne, jeśli autor jednego z nich spodziewa się, że autor drugiego z nich może recenzować jej artykuł.

Ale żartując na bok, w społeczności teoretycznej powiedziałbym, że jaki problem algorytm A rozwiązuje, jest raczej styczny do tego, czy jest „podobny” do algorytmu B, który może rozwiązać zupełnie inny problem. A jest podobny do B, jeśli „działa” z powodu tej samej głównej idei teoretycznej. Na przykład, czy główna idea obu algorytmów polega na tym, że można rzutować dane do przestrzeni o znacznie mniejszych wymiarach, zachować normy za pomocą lematu Johnsona-Lindenstraussa, a następnie przeprowadzić wyszukiwanie siłowe? Twój algorytm jest podobny do innych algorytmów, które to robią, bez względu na to, jaki problem rozwiązujesz. Istnieje niewielka liczba ciężkich technik algorytmicznych, które można zastosować do rozwiązania wielu różnych problemów, i sądzę, że techniki te tworzą centroidy wielu zestawów „podobnych” algorytmów.

Bardzo interesujące pytanie i bardzo fajny papier Ryan!

Zdecydowanie zgadzam się z pomysłem, że ocena ogólnego podobieństwa między algorytmami jest głównie subiektywną oceną wartości. Podczas gdy z technicznego punktu widzenia istnieje wiele cech, które są ściśle obserwowane, aby decydować o podobieństwie algorytmów, ostatecznie jest to również kwestia osobistego gustu. Postaram się opisać znaczenie obu stron tej samej monety, odnosząc się do poszczególnych punktów twojego pytania:

Z technicznego punktu widzenia:

1. Ryan wskazał już, że oba algorytmy muszą rozwiązać ten sam problem . Można pójść jeszcze dalej i uogólnić to pojęcie, mówiąc, że zwykle wystarczy udowodnić, że istnieje wielomianowa transformacja tej samej instancji, która jest zrozumiała dla algorytmu A, aby algorytm B mógł sobie z tym poradzić. Byłoby to jednak bardzo słabe. Wolę myśleć o podobieństwie w silniejszym znaczeniu.
2. Jednak nigdy nie spodziewałbym się, że dwa równoważne algorytmy będą miały ten sam intuicyjny pomysł --- jednak znowu jest to definicja, która nie jest łatwa do uchwycenia. Co więcej, często zdarza się, że algorytmy uważane za podobne nie są zgodne z głównym uzasadnieniem. Rozważmy na przykład niektóre algorytmy sortowania, które powstały jednak na różne sposoby, zgodnie z różnymi pomysłami. Jako skrajny przykład rozważ algorytmy genetyczne, które są zwykle rozpatrywane przez społeczność matematyczną, podobnie jak procesy stochastyczne (i dlatego są one równoważne ich zdaniem), które są następnie modelowane i analizowane w zupełnie inny sposób.
3. $N$$^*$$(N^2-1)$bazy danych wzorców addytywnych faktycznie rozszerzyłyby tę samą liczbę węzłów w dokładnie tej samej kolejności, co sprawia, że ​​oba algorytmy (i ich heurystyka) są ściśle równoważne w bardzo silnym znaczeniu, podczas gdy pierwsze podejście nie ma wstępnego przetwarzania, a drugie ma znaczny narzut przed rozpoczęciem rozwiązywania konkretnej instancji. Jednak gdy tylko bazy danych wzorców rozważą bardziej symulowane interakcje, istnieje ogromna różnica w wydajności między nimi, tak że są to zdecydowanie różne pomysły / algorytmy.
4. W rzeczywistości uważam, że większość ludzi ocenia algorytmy pod kątem ich celu i wydajności . Dlatego asymptotyczna wydajność jest dobrym miernikiem uzasadniającym podobieństwo między programami. Należy jednak pamiętać, że ta wydajność niekoniecznie jest typowym przypadkiem, więc jeśli dwa algorytmy mają tę samą wydajność asymptotyczną, ale zachowują się inaczej w praktyce, prawdopodobnie doszedłbyś do wniosku, że są one różne. Mocnym dowodem w tym względzie byłoby to, że oba algorytmy mają tę samą wydajność zarówno pod względem czasu, jak i pamięci (a to, jak powiedział Suresh, sprawia, że ​​DFS i BFS wyglądają inaczej). Jeśli to stwierdzenie nie wydaje ci się przekonujące, zapoznaj się z doskonałą (i bardzo zalecaną) książką: Programowanie wszechświataautor: Seth Lloyd. Na stronie 189 odwołuje się do listy o ponad 30 miarach złożoności, których można użyć do uznania algorytmów za różne.

Co sprawia, że ​​algorytmy są podobne / różne? Moim zdaniem (i to jest wyłącznie spekulatywne) główna różnica dotyczy tego, co ci sugerują. Wiele, wiele (wiele!) Algorytmów różni się tylko kilkoma szczegółami technicznymi, gdy służą do tego samego celu, tak że typowy przypadek jest inny dla różnych zakresów danych wejściowych. Jednak największa ze wszystkich różnic jest (moim zdaniem) tym, co sugerują. Algorytmy mają różne możliwości, a zatem swoje mocne i słabe strony. Jeśli dwa algorytmy wyglądają na takie same, ale mogą być rozszerzone na różne sposoby, aby poradzić sobie z różnymi przypadkami, wyciągnę wniosek, że są one różne. Często jednak dwa algorytmy wyglądają tak samo, abyś uważał je za takie same ... dopóki ktoś nie przybędzie, dokonując kluczowego rozróżnienia i nagle zupełnie się różnią!

Przepraszam, moja odpowiedź była tak długa ...

Twoje zdrowie,

Wszelkie wzmianki o podobieństwie bez zdefiniowania miary podobieństwa nie są dobrze zdefiniowane. Istnieje wiele sposobów, w jakie dwa algorytmy mogą być podobne:

Quicksort i Mergesort rozwiązują bardzo podobne problemy, ale używają do tego różnych algorytmów. Mają podobną złożoność algorytmiczną (chociaż ich najgorsze wyniki i użycie pamięci mogą się różnić). Quicksort i Mergesort są podobne do Bubblesort, jednak Bubblesort ma bardzo różne wskaźniki wydajności. Jeśli zignorujesz statystyki złożoności, Quicksort, Mergesort i Bubblesort są w tej samej klasie równoważności. Jeśli jednak zależy ci na złożoności algorytmicznej, Quicksort i Mergesort są znacznie bardziej do siebie podobne niż Bubblesort.

Programowanie dynamiczne Smitha-Watermana i porównanie sekwencji HMM próbuje rozwiązać problem wyrównywania dwóch sekwencji. Biorą jednak różne dane wejściowe. Smith-Waterman przyjmuje dwie sekwencje jako dane wejściowe, a porównania sekwencji HMM przyjmują HMM i sekwencję jako dane wejściowe. Oba wyrównania sekwencji wyjściowych. Pod względem motywujących pomysłów oba są podobne do odległości edycyjnej Levenshteina , ale tylko na bardzo wysokim poziomie.

Oto kilka kryteriów, według których dwa algorytmy można nazwać podobnymi:

1. Typy wejść / wyjść
2. Złożoność algorytmiczna / pamięci
3. Założenia dotyczące rodzajów danych wejściowych (np. Tylko liczby dodatnie lub stabilność zmiennoprzecinkowa)
4. Zagnieżdżone relacje (np. Niektóre algorytmy są specjalnymi przypadkami innych)

Krytyczna decyzja dotycząca znaczenia podobieństwa pozostaje. Czasami zależy Ci na złożoności algorytmu, czasem nie. Ponieważ definicja podobieństwa zależy od kontekstu dyskusji, termin „podobny algorytm” nie jest dobrze zdefiniowany.