czyli czego się możecie ode mnie nauczyć
Bicykl Hamiltona 2010-10-22 19:10
 Oceń wpis
   
_-¯ 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.

captcha_banner

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 vn, które to vn 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
 
 


Najnowsze komentarze
 
2017-06-21 16:10
Iwona Brzeszkiewicz do wpisu:
Jak się włamać na konto pocztowe
Czesc, kochanie. Czy wciaz szukasz pomocy. Nie szukaj dalej, poniewaz senator Walter chce i[...]
 
2017-06-15 14:20
kelvin smith do wpisu:
Jak się włamać na konto pocztowe
Brak zabezpieczenia społecznego i brak kontroli kredytowej, 100% gwarancji. Wszystko, co musisz[...]
 
2017-06-13 06:20
Gregs Walker do wpisu:
Jak się włamać na konto pocztowe
Uwaga: Jest to BOOST CAPITAL CENTRAL TRUST FINANCE LIMITED. Oferujemy wszelkiego rodzaju[...]
 
2017-06-13 06:09
Gregs Walker do wpisu:
Jak się włamać na konto pocztowe
Uwaga: Jest to BOOST CAPITAL CENTRAL TRUST FINANCE LIMITED. Oferujemy wszelkiego rodzaju[...]
 
2017-06-09 16:42
George cover.. do wpisu:
Jak się włamać na konto pocztowe
Witamy w programie Fba loaninvestment Czasami potrzebujemy gotówki w nagłych wypadkach i[...]
 
2017-06-08 05:05
Mr David do wpisu:
Jak się włamać na konto pocztowe
Witam drodzy cenni klienci, Witamy pana posła Davida Johna, czy szukasz pożyczki, aby[...]
 
2017-06-05 23:40
barrett buck do wpisu:
Jak się włamać na konto pocztowe
Czy potrzebujesz pożyczki @ 2%, jeśli tak skontaktuj się z nami na wszystkie rodzaje kredytów[...]
 
2017-06-03 00:26
Collins James do wpisu:
Jak się włamać na konto pocztowe
Damat Financial Corporation, Inc.   Jesteśmy prywatnymi kredytodawcami międzynarodowymi.[...]
 



 
Chakier, Charyzjusz. Q2hhcnl6anVzeiBDaGFraWVyCg== chakier[at]vp.pl