Heurystyka (informatyka)

Heurystyka (gr. heuresis „odnaleźć, odkryć”, heureka „znalazłem”) – metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy wykrywaniu szkodliwego oprogramowania w systemach komputerowych). Metoda służy także do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. To ostatnie zastosowanie dotyczy przede wszystkim przypadków, kiedy heurystyka jest wykorzystywana do nakierowywania pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyć czas działania programu w typowym przypadku bez poświęcania jakości rozwiązania (np. algorytm A*).

Wyszukiwaniem informacji nazywamy proces przeszukiwania określonego zbioru dokumentów odnoszących się do tematu czy przedmiotu wskazanego w zapytaniu lub zawierających konieczne dla użytkownika fakty. Proces ten nie został jednak precyzyjnie i skończenie określony przez wzory, normy czy algorytmy i w dużej mierze opiera się na heurystykach w tym wypadku definiowanych jako zbiór reguł oraz wskazówek, które mogą, lecz nie muszą, prowadzić do właściwego rozwiązania.

Algorytm dokładny a heurystyka

Heurystyka stanowi algorytm, podobnie jak wszystko, co potrafi wykonać komputer. Zasadnicza różnica między poszukiwaniem rozwiązań za pomocą algorytmów dokładnych a heurystycznych polega na tym, że pierwsze podejście zwraca optymalne rozwiązanie (choć czas oczekiwania na rozwiązanie może być dowolnie długi, lecz skończony), podczas gdy podejście heurystyczne pozwala znaleźć rozwiązanie przybliżone, a jedynie w szczególnym przypadku dokładne. Ze względu na to metody algorytmiczne stosowane są najczęściej w przypadku zbadanych, znanych już problemów, heurystyczne natomiast wszędzie tam, gdzie nie są znane algorytmy pozwalające na wystarczająco szybkie znalezienie rozwiązań dokładnych.

Heurystyka informacyjna dotyczy tego, jak szybko i efektywnie wyszukać dokładnie tę informację, której użytkownik potrzebuje oraz tego, z jakich narzędzi, pamięci lub sprzętów służących do procesu poszukiwawczego będzie korzystał. Optymalne dotarcie do rozwiązania określa szybkość oraz cenę dostępu do właściwego wyniku, czyli odnalezienie dokumentów odpowiednich przy minimalnej liczbie operacji w procesie wyszukiwania.

Dwie naczelne zasady heurystyki informacyjnej to:

1. zasada wyczerpania (kompletności)
2. zasada właściwego doboru materiału (adekwatności)

Pożądany stopień trafności i kompletności zależy w dużej mierze od przeznaczenia wykorzystania informacji, tzn. do czego informacja jest w rzeczywistości potrzebna. Nie zawsze użytkownikowi zależy w jednakowym stopniu na osiągnięciu dużej trafności i kompletności wyszukiwania, tym bardziej że podniesienie jednego wskaźnika powoduje z reguły obniżenie drugiego, tj. zwiększenie trafności obniża kompletność i odwrotnie. Przy ustalaniu zdolności potrzeb informacyjnych pamiętać należy, że istotną cechą adekwatności jest jej subiektywny charakter, jest to jednak podstawowa cecha każdej informacji, która nie może istnieć bez odbiorcy.

Przykład

W szczególności metody heurystyczne są stosowane kiedy nie jest znany algorytm rozwiązujący ogólny problem, ale chcemy rozwiązać pewną mniejszą klasę problemów zawartych w ogólny, o pewnych specyficznych cechach. Przykładem może tu być, problem komiwojażera – znaleźć trasę pomiędzy miastami, przechodzącą przez wszystkie miasta i będąc przy tym najkrótszą możliwą taką trasą. Ogólnie postawiony problem jest NP-trudny, i wydaje się, że nie istnieje algorytm działający wiele szybciej niż algorytm typu brute-force, sprawdzający wszystkie możliwości, co limituje jego zastosowanie do grafów o małej wielkości (rzędu 15 miast). Jednakże pożytki, jakie by dało znalezienie takiego algorytmu, w praktyce powoduje, że szuka się rozwiązań tego problemu wystarczająco blisko rozwiązania, co pozwala zwiększyć liczbę miast (miejsc) znacznie. Takimi heurezami może być na przykład użycie takich znanych faktów, jak:

1. Miasta i drogi leżą na płaszczyźnie (w przypadku ogólnego problemu nie jest to prawda, nie każdy graf jest planarny),
2. Miasta są rozłożone mniej więcej równomiernie na pewnym obszarze,
3. Miasta mają tendencję do klastrowania (miasta skupiają się w grupy. Co sugeruje, żeby rozwiązać problem komiwojażera dla klastrów w całości, używając dróg szybkiego ruchu, a następnie mniejsze i niezależne problemy komiwojażera w klastrach),
4. Da się szybko oszacować odległość pomiędzy dowolnymi miastami, poprzez długość w linii prostej,
5. Wydaje się, że trasa nie powinna się krzyżować sama ze sobą,
6. Na pewno niepożądane jest, aby trasa zawierała odcinki, które mają charakter jazdy „tam i z powrotem”, szczególnie na duże odległości,
7. Powinniśmy zacząć podróż na brzegu obszaru i starać się go okrążać systematycznie, nie zaś przemieszczać się chaotycznie,
8. Inne które być może w ogólności nie są prawdziwe, ale jedynie mamy przekonanie że pomogą rozwiązać problem,
9. Często pomaga sprawdzenie kilku przypadkowych kombinacji i wybieranie ich najlepszych cech (zobacz algorytm genetyczny)

Wiele z takich heurez można znaleźć poprzez obserwację jak ludzie rozwiązują problem (w sposób przybliżony) „ręcznie” – wystarczy wydrukować wiele kopii różnych map i przeprowadzić eksperymenty na ludziach, obserwując sposób, w jaki łączą oni miasta ołówkiem (czy poprawiają trasy), albo poruszają gałkami ocznymi. Eksperymenty takie też pozwalają znaleźć przypadki kiedy heurezy nie działają, oraz pozwalają na oszacowanie czasu ile zajmuje znalezienie rozwiązania.

Innym przykładem, może być użycie heurezy w celu optymalizacji najczęstszych przypadków, z jakimi będzie borykał się program (popartych najczęściej wcześniejszym profilowaniem). Umożliwia to na podstawie jakiegoś kryterium (np. rozmiar wejścia), rozwiązywanie kilkoma algorytmami do wyboru, i w razie niemożności rozwiązania algorytmem specyficznym, powrót do ogólnego algorytmem zapasowym, który wiadomo, że zwróci poprawny wynik.

Strategia wyszukiwawcza

Dwie wymienione wyżej zasady obligują do przyjęcia określonej, optymalnej strategii wyszukiwawczej, tzn. takiego formułowania instrukcji wyszukiwawczej i ustalania kolejności poszukiwań, aby zidentyfikować maksymalną liczbę adekwatnych dokumentów pochodnych istniejących w zbiorze przy minimalnej liczbie operacji identyfikowania, czyli przekształcania zbioru. Inaczej mówiąc, jest to plan układu i kolejności stawiania pytań przez przeszukującego w trakcie realizacji określonego zapotrzebowania na informację.

Zgodnie z czterema podstawowymi heurystykami wyszukiwania informacji należy:

1. wybraną strategię traktować jako hipotezę, próbę odgadnięcia sposobu zaindeksowania poszukiwanego tematu,
2. początkowo uzyskane wyniki przeglądać pod kątem odnalezienia innych niż przyjęte możliwości wyszukiwawcze,
3. wykorzystywać wszelkie alternatywne strategie wyszukiwania,
4. nie zakładać, iż dane w bazie danych są indeksowane w sposób optymalny dla użytkownika.

Ze strategią wyszukiwawczą związane są inne pojęcia:

• Kwerenda informacyjna – pytanie w języku naturalnym skierowane do systemu informacyjnego w celu otrzymania potrzebnej informacji. Jest to inaczej zapytanie informacyjne.
• Instrukcja wyszukiwawcza – treść zapytania informacyjnego użytkownika wyrażona w języku informacyjnym w celu wyszukania ze zbioru informacyjnego dokumentów adekwatnych. Inaczej mówiąc, instrukcję wyszukiwawczą pytania stanowi tekst języka informacyjno-wyszukiwawczego wyspecjalizowany w funkcji wyszukiwawczej odwzorowującej treść zapytania informacyjnego.
• Charakterystyka wyszukiwawcza – opis dokumentu wyrażony w języku informacyjnym, charakteryzujący podstawową treść dokumentów lub inne cechy konieczne do odszukania tych dokumentów według instrukcji wyszukiwawczej.

Co ciekawe, heurystyka pozwala też wykrywać zachowania aplikacji, bez konieczności ich otwierania. Wiele rozwiązań antywirusowych korzysta z tego typu wykrywania zagrożeń, aby móc wykrywać nowe, jeszcze nieznane zagrożenia. Niektóre antywirusy korzystają z heurystyki rozszerzonej — pozwala wykrywać na podstawie algorytmów heurystycznych, a nie na wykrywaniu zachowań podobnych do złośliwego oprogramowania.