Wszystko o Wyszukiwaniu Informowanym w Sztucznej Inteligencji

Wyszukiwanie świadome to rodzaj algorytmu wyszukiwania, który wykorzystuje wiedzę specyficzną dla domeny do kierowania przeszukiwaniem przestrzeni problemowej. Od systemów nawigacji po gry, przetwarzanie języka naturalnego po zarządzanie łańcuchem dostaw i bardziej świadome wyszukiwanie w sztucznej inteligencji znacznie zmniejszyło ilość czasu i zasobów obliczeniowych wymaganych do rozwiązywania różnych problemów.

Wykorzystując wiedzę specyficzną dla domeny do kierowania wyszukiwaniem, dobrze poinformowane algorytmy wyszukiwania mogą szybko eliminować nieistotne lub mniej obiecujące ścieżki, umożliwiając wyszukiwanie skoncentrowane na najbardziej obiecujących opcjach. Aby to zrobić, tego typu algorytmy wyszukiwania w sztucznej inteligencji wykorzystują heurystykę w celu poprawy wydajności i szybkości wyszukiwania.

Zapisz się na kurs uczenia maszynowego z najlepszych uniwersytetów na świecie. Zdobądź Master, Executive PGP lub Advanced Certificate Programs, aby przyspieszyć swoją karierę.

W artykule omówiona zostanie koncepcja świadomego wyszukiwania w sztucznej inteligencji, jej funkcje heurystyczne, przykłady algorytmów oraz ich zalety i wady.

Funkcja heurystyczna

Mówiąc prościej, funkcja heurystyczna to podejście do rozwiązywania problemów, które wykorzystuje praktyczną regułę lub „najlepsze przypuszczenie” do oszacowania odległości lub kosztu do stanu docelowego w problemie wyszukiwania. Funkcja heurystyczna szacuje, jak daleko stan docelowy znajduje się od stanu bieżącego, co można wykorzystać do poprowadzenia algorytmu wyszukiwania w kierunku celu.

Świadome algorytmy wyszukiwania wykorzystują te funkcje jako dodatkowe źródło informacji do podejmowania świadomych decyzji dotyczących wyboru ścieżki. Z tego powodu funkcje heurystyczne są niezbędne w świadomych algorytmach wyszukiwania.

Przykłady funkcji heurystycznych z życia wzięte

Aby lepiej zrozumieć funkcje heurystyczne, oto kilka przykładów z życia wziętych:

• W klasycznej grze typu „układanka przesuwanych kafelków” prostą funkcją heurystyczną może być policzenie liczby płytek nie na miejscu w bieżącej konfiguracji w porównaniu z konfiguracją celu. Im więcej płytek nie jest na swoim miejscu, tym dalej stan obecny znajduje się od stanu docelowego.
• W szachach funkcja heurystyczna może polegać na przypisaniu wartości każdej figurze na szachownicy w oparciu o jej względną siłę i pozycję oraz wykorzystaniu sumy tych wartości do oszacowania przewagi lub wady obecnego gracza. Tej funkcji heurystycznej można użyć do kierowania algorytmem wyszukiwania w kierunku ruchów, które prawdopodobnie doprowadzą do uzyskania lepszej pozycji.

Mając to ustalone, przejdźmy teraz do przodu i poznajmy niektóre z najczęściej używanych przykładów świadomych algorytmów wyszukiwania w sztucznej inteligencji.

Przykłady algorytmów wyszukiwania świadomego

Dwa z najczęściej używanych algorytmów wyszukiwania opartego na informacjach to najlepsze pierwsze wyszukiwanie i wyszukiwanie A*. Przyjrzyjmy się tym dwóm algorytmom wraz z kilkoma przykładami, zaletami i wadami oraz ich implementacją w Pythonie:

1. Najlepsze pierwsze wyszukiwanie

Najlepsze pierwsze wyszukiwanie to algorytm wyszukiwania, który najpierw rozwija najbardziej obiecujący węzeł, zgodnie z funkcją heurystyczną. Algorytm rozpoczyna się w węźle początkowym i sprawdza wszystkie jego węzły potomne, wybierając węzeł potomny z najniższą wartością heurystyczną jako następny węzeł do eksploracji. Proces ten trwa do momentu znalezienia węzła docelowego lub zbadania wszystkich węzłów.

Najlepsze pierwsze wyszukiwanie – ilustrowany przykład

Oto prosty przykład ilustrujący najlepsze pierwsze wyszukiwanie:

Załóżmy, że próbujesz znaleźć najkrótszą trasę z domu do pobliskiego sklepu spożywczego. Znasz odległość do sklepu spożywczego z kilku pobliskich lokalizacji, ale nie znasz dokładnej trasy. Aby rozwiązać ten problem za pomocą wyszukiwania od najlepszego, możesz:

1. Zacznij od swojej lokalizacji domowej i oblicz wartość heurystyczną dla każdej pobliskiej lokalizacji na podstawie jej odległości do sklepu spożywczego.
2. Wybierz pobliską lokalizację z najniższą wartością heurystyczną jako następny węzeł do eksploracji.
3. Oblicz wartość heurystyczną dla każdej z jego lokalizacji podrzędnych z tej pobliskiej lokalizacji i wybierz tę z najniższą wartością heurystyczną jako następny węzeł do eksploracji.
4. Powtarzaj ten proces, aż dotrzesz do sklepu spożywczego.

Najlepsze pierwsze wyszukiwanie – implementacja Pythona

Oto jak możesz zaimplementować najlepszy pierwszy algorytm wyszukiwania w Pythonie:

sterta importu

def best_first_search(stan_początkowy, stan_celu, funkcja_heurystyczna, funkcja_działania, funkcja_kosztu):

# zainicjuj zestaw graniczny i eksplorowany

granica = [(funkcja_heurystyczna(stan_początkowy, stan_celu), stan_początkowy)]

zbadane = zestaw()

# zainicjuj ścieżkę i koszt

ścieżka = {}

koszt = {}

ścieżka [stan_początkowy] = Brak

koszt[stan_początkowy] = 0

podczas gdy granica:

# pobierz węzeł o najniższej wartości heurystycznej z granicy

(h, obecny_stan) = stertaq.heappop(granica)

jeśli obecny_stan == stan_celu:

# zwróć ścieżkę, jeśli stan docelowy został osiągnięty

ścieżka powrotna

odkryto.add(bieżący_stan)

# generować możliwe akcje z bieżącego stanu

dla akcji wactions_func(current_state):

następny_stan = akcja(bieżący_stan)

# obliczyć koszt nowej ścieżki

nowy_koszt = koszt[stan_obecny] + funkcja_kosztu(stan_obecny, akcja, stan_następny)

jeśli następny_stan nie znajduje się w zbadanym i następny_stan nie znajduje się w [stan dla (h, stan) na granicy]:

# dodaj nowy stan do granicy

heapq.heappush(granica, (funkcja_heurystyczna(stan_następny, stan_celu), stan_następny))

ścieżka [stan_następny] = stan_bieżący

koszt[stan_następny] = nowy_koszt

# zwracaj Brak, jeśli stan docelowy nie jest osiągalny

powrót Brak

Jak widać, będziesz musiał zdefiniować następujące funkcje:

• heuristic_func(current_state, goal_state): Ta funkcja przyjmuje stan bieżący i stan docelowy jako dane wejściowe i zwraca oszacowanie kosztu osiągnięcia stanu docelowego ze stanu bieżącego.
• actions_func(current_state): Ta funkcja pobiera bieżący stan jako dane wejściowe i zwraca listę działań, które można wykonać na podstawie bieżącego stanu.
• cost_func(bieżący_stan, akcja, następny_stan): Ta funkcja pobiera bieżący stan, akcję i następny stan jako dane wejściowe i zwraca koszt podjęcia działania ze stanu bieżącego do następnego.

Przykład najlepszego pierwszego wyszukiwania

stan_początkowy = (0, 0)

stan_celu = (4, 4)

def heuristic_func(bieżący_stan, stan_celu):

return abs(obecny_stan[0] – stan_celu[0]) + abs(obecny_stan[1] – stan_celu[1])

defactions_func(bieżący_stan):

akcje = []

jeśli stan_bieżący[0] > 0:

akcje.append(stan lambda: (stan[0]-1, stan[1]))

jeśli stan_bieżący [0] < 4:

akcje.append(stan lambda: (stan[0]+1, stan[1]))

jeśli stan_bieżący[1] > 0:

akcje.append(stan lambda: (stan[0], stan[1]-1))

jeśli stan_bieżący [1] < 4:

akcje.append(stan lambda: (stan[0], stan[1]+1))

akcje zwrotne

def cost_func(bieżący_stan, akcja, następny_stan):

powrót 1

ścieżka = najlepsze_pierwsze_wyszukiwanie(stan_początkowy, stan_celu, funkcja_heurystyczna, funkcja_działań, funkcja_kosztu)

jeśli ścieżka:

# skonstruuj ścieżkę od stanu początkowego do stanu docelowego

obecny_stan = stan_celu

podczas gdy aktualny_stan != stan_początkowy:

print(bieżący_stan)

stan_bieżący = ścieżka [stan_bieżący]

print(stan_początkowy)

w przeciwnym razie:

print("Stan celu jest nieosiągalny.")

Zalety najlepszego pierwszego wyszukiwania

• W porównaniu z przeszukiwaniem wszerz złożoność czasowa przeszukiwania od najlepszego pierwszego jest mniejsza.
• Najlepsze pierwsze wyszukiwanie uzyskuje i implementuje zalety algorytmów BFS i DFS

Wady najlepszego pierwszego wyszukiwania

• Czasami może obejmować większą odległość, niż rozważano.
• Prawdopodobieństwo utknięcia w pętli jest bardzo prawdopodobne.

Wyszukiwanie

Wyszukiwanie A* to algorytm wyszukiwania, który wykorzystuje zarówno koszt dotarcia do węzła z węzła początkowego, jak i oszacowanie pozostałego kosztu dotarcia do węzła docelowego, aby kierować wyszukiwaniem. Algorytm zaczyna się od początkowego węzła i sprawdza wszystkie jego węzły potomne, wybierając jako następny węzeł potomny o najniższym łącznym koszcie i szacowanym pozostałym koszcie. Proces ten trwa do momentu znalezienia węzła docelowego lub zbadania wszystkich węzłów.

Wyszukiwanie A* – ilustrowany przykład

Przyjrzyjmy się ponownie poprzedniemu przykładowi, w którym próbujesz znaleźć najkrótszą trasę z domu do pobliskiego sklepu spożywczego. Teraz możesz:

1. Zacznij od swojej lokalizacji domowej i oblicz całkowity koszt dotarcia do każdej pobliskiej lokalizacji jako sumę odległości z domu do tej lokalizacji i szacowanego pozostałego kosztu dotarcia do sklepu spożywczego z tej lokalizacji.
2. Wybierz pobliską lokalizację o najniższym całkowitym koszcie jako następny węzeł do eksploracji.
3. Na podstawie tej pobliskiej lokalizacji oblicz całkowity koszt dla każdej z jej lokalizacji podrzędnych jako sumę odległości z tej lokalizacji do lokalizacji podrzędnej, koszt dotarcia do tej lokalizacji z węzła początkowego oraz szacowany pozostały koszt dotarcia do sklepu spożywczego z tej lokalizacji podrzędnej. Wybierz lokalizację podrzędną o najniższym całkowitym koszcie jako następny węzeł do eksploracji.
4. Powtarzaj ten proces, aż dotrzesz do sklepu spożywczego.

Ważną rzeczą, na którą należy zwrócić uwagę, jest to, że A* Search jest optymalnym algorytmem wyszukiwania, który gwarantuje znalezienie najkrótszej ścieżki do stanu docelowego. Jest skuteczny w problemach z dużą przestrzenią wyszukiwania i jest szeroko stosowany w grach wideo, robotyce i planowaniu tras. Jednak wymaga dobrze zdefiniowanej funkcji heurystycznej, aby była skuteczna. Z tego powodu algorytm może wymagać dużej ilości pamięci i spowalniać w złożonych problemach z wieloma węzłami.

A* search – implementacja Pythona

Oto jak można zaimplementować algorytm wyszukiwania A* przy użyciu programowania w języku Python:

sterta importu

def astar_search(stan_początkowy, stan_celu, funkcja_heurystyczna, funkcja_działania, funkcja_kosztu):

# zainicjuj zestaw graniczny i eksplorowany

granica = [(funkcja_heurystyczna(stan_początkowy, stan_celu), stan_początkowy)]

zbadane = zestaw()

# zainicjuj ścieżkę i koszt

ścieżka = {}

koszt = {}

ścieżka [stan_początkowy] = Brak

koszt[stan_początkowy] = 0

podczas gdy granica:

# pobierz węzeł z najniższą wartością f od granicy

(f, obecny_stan) = sterta.heappop(granica)

jeśli obecny_stan == stan_celu:

# zwróć ścieżkę, jeśli stan docelowy został osiągnięty

ścieżka powrotna

odkryto.add(bieżący_stan)

# generować możliwe akcje z bieżącego stanu

dla akcji wactions_func(current_state):

następny_stan = akcja(bieżący_stan)

# obliczyć koszt nowej ścieżki

nowy_koszt = koszt[stan_obecny] + funkcja_kosztu(stan_obecny, akcja, stan_następny)

jeśli następny_stan nie jest eksplorowany i następny_stan nie znajduje się w [stan dla (f, stan) na granicy]:

# dodaj nowy stan do granicy

heapq.heappush(frontier, (new_cost + heuristic_func(następny_stan, cel_stan), następny_stan))

ścieżka [stan_następny] = stan_bieżący

koszt[stan_następny] = nowy_koszt

elif stan_następny w [stan dla (f, stan) na granicy] i nowy_koszt < koszt [stan_następny]:

# zaktualizować koszt istniejącego stanu na granicy

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

granica[indeks] = (nowy_koszt + funkcja_heurystyczna(stan_następny, stan_celu), stan_następny)

ścieżka [stan_następny] = stan_bieżący

koszt[stan_następny] = nowy_koszt

# zwracaj Brak, jeśli stan docelowy nie jest osiągalny

powrót Brak

Najlepsze kursy uczenia maszynowego i kursy AI online

Przykład wyszukiwania A*

Oto przykład, jak możesz użyć funkcji astar_search z tymi funkcjami:

stan_początkowy = (0, 0)

stan_celu = (4, 4)

def heuristic_func(bieżący_stan, stan_celu):

return abs(obecny_stan[0] – stan_celu[0]) + abs(obecny_stan[1] – stan_celu[1])

defactions_func(bieżący_stan):

akcje = []

jeśli stan_bieżący[0] > 0:

akcje.append(stan lambda: (stan[0]-1, stan[1]))

jeśli stan_bieżący [0] < 4:

akcje.append(stan lambda: (stan[0]+1, stan[1]))

jeśli stan_bieżący[1] > 0:

akcje.append(stan lambda: (stan[0], stan[1]-1))

jeśli stan_bieżący [1] < 4:

akcje.append(stan lambda: (stan[0], stan[1]+1))

akcje zwrotne

def cost_func(bieżący_stan, akcja, następny_stan):

powrót 1

ścieżka = astar_search(stan_początkowy, stan_celu, funkcja_heurystyczna, funkcja_działań, funkcja_kosztu)

jeśli ścieżka:

# skonstruuj ścieżkę od stanu początkowego do stanu docelowego

obecny_stan = stan_celu

podczas gdy aktualny_stan != stan_początkowy:

print(bieżący_stan)

stan_bieżący = ścieżka [stan_bieżący]

print(stan_początkowy)

w przeciwnym razie:

print("Stan celu jest nieosiągalny.")

Zalety wyszukiwania A*

• Jest to jedna z wiodących technik heurystycznych.
• Wyszukiwanie* można wykorzystać do rozwiązywania złożonych problemów związanych z wyszukiwaniem

Trendy w umiejętnościach uczenia maszynowego

Wady wyszukiwania A*

• Wydajność wyszukiwania A* w dużym stopniu zależy od dokładności algorytmów heurystycznych.
• Ma niską skuteczność wyszukiwania.

Popularne blogi AI i ML oraz bezpłatne kursy

Na wynos

Świadome algorytmy wyszukiwania są niezbędne w sztucznej inteligencji, ponieważ pozwalają komputerowi na wydajne i skuteczne wyszukiwanie stanu docelowego. Algorytmy te wykorzystują funkcje heurystyczne do oszacowania kosztu każdego możliwego ruchu i kierują procesem wyszukiwania w kierunku stanu docelowego. Best First Search i A* Search to przykłady świadomych algorytmów wyszukiwania szeroko stosowanych w różnych dziedzinach. Jednak dobrze zdefiniowana funkcja heurystyczna ma kluczowe znaczenie dla sukcesu świadomych algorytmów wyszukiwania.

Jeśli chcesz dowiedzieć się więcej o sztucznej inteligencji i uczeniu maszynowym, zapoznaj się z programem upGrad's Masters in Machine Learning & Artificial Intelligence oferowanym przez Liverpool John Moores University . Ten program obejmuje różne tematy dotyczące uczenia maszynowego i sztucznej inteligencji, w tym algorytmy, takie jak wyszukiwanie informacji. Biorąc udział w tym programie, możesz zdobyć umiejętności i wiedzę potrzebne do odniesienia sukcesu w różnych karierach związanych ze sztuczną inteligencją.

Możesz również sprawdzić naszebezpłatne kursyoferowane przez upGrad w zakresie zarządzania, nauki o danych, uczenia maszynowego, marketingu cyfrowego i technologii.Wszystkie te kursy mają najwyższej klasy zasoby do nauki, cotygodniowe wykłady na żywo, zadania branżowe i certyfikat ukończenia kursu - wszystko bezpłatnie!