_-¯ W dzisiejszym wpisie chciałbym przybliżyć P.T. Czytelnikom mało znaną klasę algorytmów, określanych jako ,,algorytmy a-moralne''. Ojcem tej dziedziny jest zapewne doskonale znana Państwu postać profesora Erwina Donalda Charapa, który szczegółowo opisał ją w swoim dziele ,,The Art of A-moral Computer Programming''. Miałem niewątpliwą przyjemność uczestniczyć w tworzeniu wspomnianej pozycji, a teraz - korzystając z nadarzającej się okazji - chciałbym rozpocząć cykl artykułów poświęconych właśnie a-moralistyce (jak w skrócie określa się algorytmikę a-moralną).

_-¯ Na wstępie kilka słów wyjaśnienia, czym właściwie są algorytmy a-moralne? Główną właściwością tej grupy algorytmów jest ich całkowita nieprzydatność do rozwiązywania danego problemu, czy nawet wręcz szkodliwość. Algorytmy a-moralne nie tylko nie prowadzą do rozwiązania zadania, ale wręcz to rozwiązanie utrudniają. Najprostszym przykładem takiego algorytmu jest ,,a-moral algorithm for optical character recognition'', z sukcesem wykorzystywany w systemach captcha.


Umieszczony powyżej obrazek to przykład, jak zastosowany algorytm wpływa na postać danych wejściowych (oryginalny tekst znajduje się w nawiasach kwadratowych). Jak widać efektem działania jest nie tylko nie wyprodukowanie poprawnie rozpoznanego tekstu, ale jeszcze zmodyfikowanie danych wejściowych tak, by były możliwie nieużywalne dla innych systemów OCR. Jeden z najbardziej znanych algorytmów tego typu, znany pod nazwą CPW (od nazwisk twórców: Charap-Pratt-Whitney) nie tylko przekształca źródło danych, lecz dodatkowo wysyła obraźliwe e-maile lub stara się tak odcyfrować tekst by ułożyć obraźliwy wierszyk. Dla przykładu z powyższego obrazka zamiast spodziewanego słowa ,,captcha'' wyjściem był następujący tekst:

Na górze róże
Na dole fiołki
Charyzjusz Chakier
Jest głupi jak but i śmierdzi mu z butów!!!111jedenjedenjeden
Złożoność obliczeniowa algorytmu CPW wynosi O(n*log(k*n)), gdzie k jest liczbą słów generowanego wierszyka, zaś n stałą większą 1.5 raza od t, gdzie t jest czasem który użytkownik jest w stanie czekać na wyniki działania programu. Jak widać algorytm jest wysoce wydajny i prowadzi do irytacji zarówno samego użytkownika, jak i jego otoczenia. Jako ciekawostkę dodam fakt, że CPW często używa powtórzeń wyrazów w tej samej, lub w sąsiadujących frazach, w celu spotęgowania wrażenia - zatem zwrot ,,głupi jak but i śmierdzi mu z butów'' wcale nie jest przypadkowy, choć zapewne mniej wydajne algorytmy użyłyby ,,głupi jak but i śmierdzą mu stopy'', co jednak nie jest aż tak niedobre jak w przypadku CPW.

_-¯ Dzisiaj jednak chciałem omówić inny algorytm a-moralny, dotyczący znajdowania bicyklu Hamiltona w grafie. Na wejściu pojawia się spójny graf, zaś algorytm ma znaleźć w nim taki bicykl, na którym Hamilton byłby w stanie objechać wszystkie wierzchołki, odwiedzając każdy dokładnie jeden raz. Rozwinięciem problemu bicyklu Hamiltona jest bicykl komiwojażera, gdy dany jest skierowany graf ważony, zaś komiwojażer ma osiągnąć na swoim bicyklu czas nie gorszy od każdego innego osiągniętego przez Hamiltona na dowolnym znalezionym przez siebie bicyklu. Oczywiście nie należy również dopuścić do tego, by Hamilton wziął bicykl komiwojażera. Oto jak należałoby się do tego zabrać z punktu widzenia a-moralistyki:
1. Napisać algorytm który w pierwszym kroku kradnie pierwszy napotkany bicykl.
2. Używając tego bicyklu ucieka przed Hamiltonem, zachowując na n-tej krawędzi grafu prędkość co najmniej v_n, które to v_n jest minimalną prędkością potrzebną do przybycia do k-tego wierzchołka zanim Hamilton
osiągnie wierzchołek k-1. W k-tym wierzchołku algorytm porzuca bicykl spuściwszy z jego opon powietrze i kradnie następny.
3. Punkt drugi powtarzany jest tak długo, aż ze wszystkich opon wszystkich bicykli w grafie zostanie spuszczone powietrze.
Przykładem zastosowania w/w algorytmu było wprowadzenie go do komputerów teamu McLarena podczas treningu przed Grand Prix Japonii.
_-¯ Jak wspomniałem, rozwinięciem problemu poszukiwania bicyklu Hamiltona jest problem komiwojażera. Normalne rozwiązanie polega na wyznaczeniu bicyklu na którym komiwojażer w najkrótszym czasie przejedzie przez wszystkie miasta/wierzchołki grafu. Kiedy do problemu zastosowałem ,,a-moral algorithm for traveling salesman problem'' mój komputerowy komiwojażer najpierw zapomniał wziąć ze sobą towaru, potem udał się nie do tych miast które miał odwiedzić, na końcu zaś został napadnięty w pociągu przez szalikowców, pobity i okradziony. Nie tylko więc nie odwiedził żadnego z wyznaczonych punktów, ale również stracił cały dorobek życia (wirtualnego, ale jednak).

_-¯ Na szczęście istnieje prosta metoda posługiwania się algorytmami a-moralnymi tak, by służyły zamiast szkodzić. Wystarczy po prostu używać ich do rzeczy wręcz przeciwnych niż te, których dotyczą, np. ,,a-moral algorithm for picture distorting'' znakomicie nadaje się do rozpoznawania tekstów i obrazów. Ale o tym napiszę w kolejnym wpisie...

PS: Czytelników serdecznie zapraszam do zapoznania się z opowiadaniem Zgrzytanie, pierwszym fan-ficowym utworem o mnie :D