Algorytm wyszukiwania - Search algorithm

Wizualna reprezentacja tablicy mieszającej , struktury danych, która pozwala na szybkie wyszukiwanie informacji.

W informatyce , wykorzystując algorytm wyszukiwania jest algorytm (zwykle obejmujące wiele innych, bardziej specyficznych algorytmów), który rozwiązuje problemy wyszukiwarki . Algorytmy wyszukiwania działają w celu pobrania informacji przechowywanych w pewnej strukturze danych lub obliczanych w przestrzeni wyszukiwania domeny problemowej, przy użyciu wartości dyskretnych lub ciągłych .

Chociaż problemy związane z wyszukiwaniem opisane powyżej i wyszukiwanie w sieci są problemami związanymi z wyszukiwaniem informacji, są one na ogół badane jako oddzielne poddziedziny i są rozwiązywane i oceniane w różny sposób. Problemy związane z wyszukiwaniem w sieci zwykle skupiają się na filtrowaniu i znajdowaniu dokumentów, które są najbardziej odpowiednie dla zapytań ludzkich. Klasyczne algorytmy wyszukiwania są zazwyczaj oceniane na podstawie tego, jak szybko mogą znaleźć rozwiązanie i czy jest ono gwarantowane jako optymalne. Chociaż algorytmy wyszukiwania informacji muszą być szybkie, ważniejsza jest jakość rankingu oraz to, czy pominięto dobre wyniki, a uwzględniono złe wyniki.

Odpowiedni algorytm wyszukiwania często zależy od przeszukiwanej struktury danych i może również obejmować wcześniejszą wiedzę o danych. Niektóre struktury baz danych, takie jak drzewo wyszukiwania , mapa skrótów lub indeks bazy danych , są specjalnie skonstruowane w celu przyspieszenia lub zwiększenia wydajności algorytmów wyszukiwania .

Algorytmy wyszukiwania można podzielić na podstawie ich mechanizmu wyszukiwania na 3 typy algorytmów: liniowy, binarny i mieszający. Algorytmy wyszukiwania liniowego sprawdzają każdy rekord pod kątem tego, który jest powiązany z kluczem docelowym w sposób liniowy. Wyszukiwania binarne lub połówkowe , wielokrotnie celują w środek struktury wyszukiwania i dzielą przestrzeń wyszukiwania na pół. Algorytmy wyszukiwania porównawczego usprawniają wyszukiwanie liniowe poprzez sukcesywne eliminowanie rekordów opartych na porównaniach kluczy aż do znalezienia rekordu docelowego i mogą być stosowane na strukturach danych o określonej kolejności. Algorytmy wyszukiwania cyfrowego działają w oparciu o właściwości cyfr w strukturach danych wykorzystujących klucze numeryczne. Na koniec haszowanie bezpośrednio mapuje klucze do rekordów na podstawie funkcji haszującej .

Algorytmy są często oceniane na podstawie ich złożoności obliczeniowej lub maksymalnego teoretycznego czasu działania. Na przykład funkcje wyszukiwania binarnego mają maksymalną złożoność wynoszącą O (log n ) lub czas logarytmiczny. Oznacza to, że maksymalna liczba operacji potrzebnych do znalezienia celu wyszukiwania jest funkcją logarytmiczną wielkości przestrzeni wyszukiwania.

Zastosowania algorytmów wyszukiwania

Konkretne zastosowania algorytmów wyszukiwania obejmują:

Klasy

Wirtualne przestrzenie wyszukiwania

Algorytmy przeszukiwania przestrzeni wirtualnych wykorzystywane są w zagadnieniu spełniania więzów , gdzie celem jest znalezienie zbioru przypisań wartości do określonych zmiennych, które spełnią określone równania matematyczne i równania /równości. Są one również używane, gdy celem jest znalezienie przypisania zmiennej, które zmaksymalizuje lub zminimalizuje określoną funkcję tych zmiennych. Algorytmy rozwiązywania tych problemów obejmują podstawowe przeszukiwanie siłowe (nazywane również przeszukiwaniem „naiwnym” lub „niepoinformowanym”) oraz różnorodne heurystyki, które próbują wykorzystać częściową wiedzę o strukturze tej przestrzeni, takie jak relaksacja liniowa, generowanie ograniczeń, i propagacja ograniczeń .

Ważną podklasą są lokalne metody wyszukiwania , które widzą elementy przestrzeni poszukiwań jako wierzchołki grafu, z krawędziami zdefiniowanymi przez zestaw heurystyk mających zastosowanie do przypadku; i skanować przestrzeń, przechodząc od elementu do elementu wzdłuż krawędzi, na przykład zgodnie z najbardziej stromym zejściem lub kryterium „ najlepszy-pierwszy” lub metodą wyszukiwania stochastycznego . Ta kategoria obejmuje szeroką gamę ogólnych metod metaheurystycznych , takich jak symulowane wyżarzanie , przeszukiwanie tabu , zespoły A i programowanie genetyczne , które łączą w określony sposób dowolne heurystyki. Przeciwieństwem wyszukiwania lokalnego byłyby metody wyszukiwania globalnego. Ta metoda ma zastosowanie, gdy przestrzeń wyszukiwania nie jest ograniczona i wszystkie aspekty danej sieci są dostępne dla podmiotu uruchamiającego algorytm wyszukiwania.

Ta klasa zawiera również różne algorytmy wyszukiwania drzewa , które widzą elementy jako wierzchołki drzewa i przechodzą przez to drzewo w specjalnej kolejności. Przykłady tych ostatnich obejmują wyczerpujące metody, takie jak przeszukiwanie w głąb i wszerz , a także różne metody przycinania drzewa wyszukiwania oparte na heurystyce, takie jak wycofywanie oraz rozgałęzianie i ograniczanie . W przeciwieństwie do ogólnych metaheurystyk, które w najlepszym razie działają tylko w sensie probabilistycznym, wiele z tych metod przeszukiwania drzew gwarantuje znalezienie dokładnego lub optymalnego rozwiązania, jeśli zostanie im wystarczająco dużo czasu. Nazywa się to „ kompletnością ”.

Kolejną ważną podklasą są algorytmy do eksploracji drzewa gier wieloosobowych, takich jak szachy czy tryktrak , których węzły składają się ze wszystkich możliwych sytuacji w grze, które mogą wynikać z obecnej sytuacji. Celem w tych problemach jest znalezienie ruchu, który daje największą szansę na wygraną, biorąc pod uwagę wszystkie możliwe ruchy przeciwnika (przeciwników). Podobne problemy pojawiają się, gdy ludzie lub maszyny muszą podejmować kolejne decyzje, których wyniki nie są całkowicie pod kontrolą, takie jak kierowanie robotami lub planowanie strategii marketingowej , finansowej lub wojskowej . Tego rodzaju problem — wyszukiwanie kombinatoryczne — był szeroko badany w kontekście sztucznej inteligencji . Przykładami algorytmów dla tej klasy są algorytm minimax , przycinanie alfa-beta oraz algorytm A* i jego warianty.

Dla podkonstrukcji danej konstrukcji

Nazwa „wyszukiwanie kombinatoryczne” jest zwykle używana w odniesieniu do algorytmów, które szukają określonej podstruktury danej struktury dyskretnej , takiej jak graf, łańcuch , grupa skończona i tak dalej. Termin optymalizacja kombinatoryczna jest zwykle używany, gdy celem jest znalezienie podstruktury o maksymalnej (lub minimalnej) wartości jakiegoś parametru. (Ponieważ struktura podrzędna jest zwykle reprezentowana w komputerze przez zbiór zmiennych całkowitych z ograniczeniami, problemy te można postrzegać jako szczególne przypadki spełnienia ograniczeń lub optymalizacji dyskretnej; ale zwykle są one formułowane i rozwiązywane w bardziej abstrakcyjnym otoczeniu, gdzie reprezentacja wewnętrzna nie jest wyraźnie wymieniona.)

Ważną i szeroko zbadaną podklasą są algorytmy grafowe , w szczególności algorytmy przechodzenia przez grafy , służące do znajdowania określonych podstruktur na danym grafie — takich jak podgrafy , ścieżki , obwody i tak dalej. Przykłady obejmują Algorytm Dijkstry , Algorytm Kruskala , ten algorytm najbliższego sąsiada i Algorytm Prima .

Inną ważną podklasą tej kategorii są algorytmy wyszukiwania ciągów , które wyszukują wzorce w ciągach. Dwa znane przykłady to algorytmy Boyera-Moore'a i Knutha-Morrisa-Pratta oraz kilka algorytmów opartych na strukturze danych drzewa sufiksów .

Wyszukaj maksimum funkcji

W 1953 amerykański statystyk Jack Kiefer opracował wyszukiwanie Fibonacciego, które może być użyte do znalezienia maksimum funkcji unimodalnej i ma wiele innych zastosowań w informatyce.

Dla komputerów kwantowych

Istnieją również metody wyszukiwania przeznaczone dla komputerów kwantowych , takie jak algorytm Grovera , które są teoretycznie szybsze niż wyszukiwanie liniowe lub brute-force, nawet bez pomocy struktur danych lub heurystyki. Chociaż idee i zastosowania komputerów kwantowych są nadal całkowicie teoretyczne, przeprowadzono badania z użyciem algorytmów takich jak Grover, które dokładnie odtwarzają hipotetyczne fizyczne wersje systemów obliczeń kwantowych.

optymalizacja wyszukiwarki

Algorytmy wyszukiwania używane w wyszukiwarce, takiej jak Google, porządkują odpowiednie wyniki wyszukiwania na podstawie wielu ważnych czynników. Optymalizacja pod kątem wyszukiwarek (SEO) to proces, w którym każdy wynik wyszukiwania będzie działał w połączeniu z algorytmem wyszukiwania, aby organicznie uzyskać większą przyczepność, uwagę i kliknięcia w witrynie. Może to posunąć się tak daleko, jak próba dostosowania algorytmu wyszukiwarki, aby bardziej faworyzować określony wynik wyszukiwania, ale strategia obracająca się wokół SEO stała się niezwykle ważna i istotna w świecie biznesu.

Zobacz też

Kategorie:

Bibliografia

Cytaty

Bibliografia

Książki

Artykuły

Zewnętrzne linki