• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Heurystyka - informatyka

    Przeczytaj także...
    Pogoda – stan atmosfery w konkretnym miejscu i czasie; w szerszym ujęciu – warunki meteorologiczne na danym obszarze kuli ziemskiej. Ogół zjawisk pogodowych na danym obszarze w okresie wieloletnim (przynajmniej 30 lat) określany jest jako klimat.Dokument – w uogólnionej definicji rzeczowe świadectwo jakiegoś zjawiska sporządzone w formie właściwej dla danego czasu i miejsca.
    Język grecki, greka (starogr. dialekt attycki Ἑλληνικὴ γλῶττα, Hellenikè glõtta; nowogr. Ελληνική γλώσσα, Ellinikí glóssa lub Ελληνικά, Elliniká) – język indoeuropejski z grupy helleńskiej, w starożytności ważny język basenu Morza Śródziemnego. W cywilizacji Zachodu zaadaptowany obok łaciny jako język terminologii naukowej, wywarł wpływ na wszystkie współczesne języki europejskie, a także część pozaeuropejskich i starożytnych. Od X wieku p.n.e. zapisywany jest alfabetem greckim. Obecnie, jako język nowogrecki, pełni funkcję języka urzędowego w Grecji i Cyprze. Jest też jednym z języków oficjalnych Unii Europejskiej. Po grecku mówi współcześnie około 15 milionów ludzi. Język grecki jest jedynym językiem z helleńskich naturalnych, który nie wymarł.

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

    Algorytm genetyczny - rodzaj algorytmu przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych.Zapytanie (niekiedy zwane kwerendą, z łac. quaerenda) – czynność polegająca na zbieraniu lub poszukiwaniu informacji w aktach, bibliotekach, a przede wszystkim bazach danych.

    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.

    Hipoteza (gr. hypóthesis – przypuszczenie) – osąd, który podlega weryfikacji lub falsyfikacji. Zdanie, które stwierdza spodziewaną relację między jakimiś zjawiskami, propozycja twierdzenia naukowego, które zakłada możliwą lub oczekiwaną w danym kontekście sytuacyjnym naturę związku.Informacja (łac. informatio – przedstawienie, wizerunek; informare – kształtować, przedstawiać) – termin interdyscyplinarny, definiowany różnie w różnych dziedzinach nauki; najogólniej – właściwość pewnych obiektów, relacja między elementami zbiorów pewnych obiektów, której istotą jest zmniejszanie niepewności (nieokreśloności).

    Algorytm dokładny a heurystyka[ | edytuj kod]

    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.

    Wyszukiwanie wyczerpujące (ang. exhaustive search), metoda siłowa (ang. brute force) – metoda polegająca na analizie wszystkich potencjalnych rozwiązań zadania w celu wybrania tego, które spełnia warunki zadania.Problem komiwojażera (TSP - ang. travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.

    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 relewantnych przy minimalnej liczbie operacji w procesie wyszukiwania.

    W teorii złożoności obliczeniowej problem NP-trudny (NPH) to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

    Dwie naczelne zasady heurystyki informacyjnej to:

    1. zasada wyczerpania (kompletności)
    2. zasada właściwego doboru materiału (relewantnoś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ą relewantności jest jej subiektywny charakter, jest to jednak podstawowa cecha każdej informacji, która nie może istnieć bez odbiorcy.

    Złośliwe oprogramowanie, malware (z ang. malicious software) – wszelkie aplikacje, skrypty itp. mające szkodliwe, przestępcze lub złośliwe działanie w stosunku do użytkownika komputera.Optymalizacja - metoda wyznaczania najlepszego (optymalnego) rozwiązania (poszukiwanie ekstremum funkcji) z punktu widzenia określonego kryterium (wskaźnika) jakości (np. kosztu, drogi, wydajności).

    Przykład[ | edytuj kod]

    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ą taka 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:

    Algorytm A* – algorytm heurystyczny znajdowania najkrótszej ścieżki w grafie ważonym z dowolnego wierzchołka do wierzchołka spełniającego określony warunek zwany testem celu. Algorytm jest zupełny i optymalny, w tym sensie, że znajduje ścieżkę, jeśli tylko taka istnieje, i przy tym jest to ścieżka najkrótsza. Stosowany głównie w dziedzinie sztucznej inteligencji do rozwiązywania problemów i w grach komputerowych do imitowania inteligentnego zachowania.
    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[ | edytuj kod]

    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ę relewantnych 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 relewantnych. 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.



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.016 sek.