Totul despre căutarea informată în inteligența artificială

Căutarea informată este un tip de algoritm de căutare care utilizează cunoștințele specifice domeniului pentru a-și ghida căutarea printr-un spațiu problematic. De la sistemele de navigație la jocuri, procesarea limbajului natural la managementul lanțului de aprovizionare și căutarea mai informată în inteligența artificială a redus semnificativ timpul și resursele de calcul necesare pentru a rezolva diferite probleme.

Folosind cunoștințele specifice domeniului pentru a ghida căutarea, algoritmii de căutare informați pot elimina rapid căile irelevante sau mai puțin promițătoare, permițând căutării să se concentreze asupra celor mai promițătoare opțiuni. Pentru a face acest lucru, aceste tipuri de algoritmi de căutare în AI folosesc euristica pentru a îmbunătăți eficiența și viteza căutării.

Înscrieți-vă la cursul de învățare automată de la cele mai bune universități din lume. Câștigă programe de master, Executive PGP sau Advanced Certificate pentru a-ți accelera cariera.

Acest articol va discuta conceptul de căutare informată în inteligența artificială, funcțiile sale euristice, exemple de algoritmi și avantajele și dezavantajele acestora.

Funcția euristică

În termeni simpli, o funcție euristică este o abordare de rezolvare a problemelor care folosește o regulă generală sau o „cel mai bună presupunere” pentru a estima distanța sau costul până la o stare de obiectiv într-o problemă de căutare. Funcția euristică estimează cât de departe este starea obiectivului de starea curentă, care poate fi folosită pentru a ghida un algoritm de căutare către obiectiv.

Algoritmii de căutare informați folosesc aceste funcții ca o sursă suplimentară de informații pentru a lua decizii informate cu privire la calea pe care să o ia. Din acest motiv, funcțiile euristice sunt esențiale în algoritmii de căutare informați.

Exemple din viața reală de funcție euristică

Pentru a înțelege mai bine funcțiile euristice, iată câteva exemple din viața reală:

• În jocul clasic „puzzle cu plăci glisante”, o funcție euristică simplă ar putea fi numărarea numărului de piese din configurația curentă în comparație cu configurația obiectivului. Cu cât mai multe piese nu sunt la locul lor, cu atât starea curentă este mai departe de starea obiectivului.
• În șah, o funcție euristică ar putea fi atribuirea unei valori fiecărei piese de pe tablă pe baza puterii și poziției sale relative și de a folosi suma acelor valori pentru a estima avantajul sau dezavantajul jucătorului curent. Această funcție euristică poate fi folosită pentru a ghida un algoritm de căutare către mișcări care ar putea duce la o poziție mai bună.

Odată rezolvată, haideți să mergem mai departe și să înțelegem unele dintre cele mai utilizate exemple de algoritmi de căutare informată în inteligența artificială.

Exemple de algoritmi de căutare informată

Doi dintre cei mai des utilizați algoritmi de căutare informată includ cea mai bună primă căutare și căutarea A*. Să înțelegem acești doi algoritmi împreună cu câteva exemple, avantaje, dezavantaje și implementarea lor Python:

1. Cea mai bună prima căutare

Cea mai bună primă căutare este un algoritm de căutare care extinde mai întâi cel mai promițător nod, conform unei funcții euristice. Algoritmul începe de la nodul inițial și examinează toate nodurile sale copii, alegând copilul cu cea mai mică valoare euristică ca următorul nod de explorat. Acest proces continuă până când nodul obiectiv este găsit sau toate nodurile au fost explorate.

Cea mai bună primă căutare – un exemplu ilustrat

Iată un exemplu simplu pentru a ilustra cea mai bună primă căutare:

Să presupunem că încerci să găsești cea mai scurtă rută de la casa ta la un magazin alimentar din apropiere. Știți distanța până la magazin alimentar din câteva locații din apropiere, dar nu știți traseul exact pe care să îl urmați. Pentru a rezolva această problemă utilizând cea mai bună căutare, ați putea:

1. Începeți de la locația dvs. de acasă și calculați valoarea euristică pentru fiecare locație din apropiere, pe baza distanței acesteia până la magazinul alimentar.
2. Alegeți locația din apropiere cu cea mai mică valoare euristică ca următorul nod de explorat.
3. Calculați valoarea euristică pentru fiecare dintre locațiile copiilor săi din acea locație din apropiere și alegeți-o pe cea cu cea mai mică valoare euristică ca următorul nod de explorat.
4. Repetați acest proces până ajungeți la magazin.

Cea mai bună primă căutare – implementarea Python

Iată cum puteți implementa cel mai bun algoritm de primă căutare în Python:

import heapq

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# inițializați setul de frontieră și explorat

frontier = [(functie_euristica(start_start, goal_state), start_state)]

explorat = set()

# inițializați calea și costul

cale = {}

cost = {}

cale[start_state] = Nici unul

cost[star_start] = 0

în timp ce frontieră:

# obțineți nodul cu cea mai mică valoare euristică de la frontieră

(h, starea_actuală) = heapq.heappop(frontieră)

dacă starea_actuală == starea_golului:

# returnează calea dacă este atinsă starea obiectivului

calea de intoarcere

explored.add(starea_actuală)

# genera acțiuni posibile din starea curentă

pentru acțiune în action_func(current_state):

următoarea_stare = acțiune(starea_actuală)

# calculați costul noii căi

cost_nou = cost[starea_actuală] + funcția_cost(starea_actuală, acțiune, starea_următoare)

dacă next_state nu este explorat și next_state nu este în [state for (h, state) in frontier]:

# adăugați noul stat la frontieră

heapq.heappush(frontieră, (functură_euristică(starea_următoare, starea_gol), starea_următoare))

cale[next_state] = stare_actuală

cost[next_state] = cost_nou

# return None dacă starea obiectivului nu este accesibilă

return Niciunul

După cum puteți vedea, va trebui să definiți următoarele funcții:

• heuristic_func(current_state, goal_state): Această funcție ia starea curentă și starea obiectivului ca intrări și returnează o estimare a costului atingerii stării obiectiv din starea curentă.
• actions_func(current_state): Această funcție ia starea curentă ca intrare și returnează o listă de acțiuni care pot fi luate din starea curentă.
• cost_func(current_state, action, next_state): Această funcție preia starea curentă, o acțiune și următoarea stare ca intrări și returnează costul acțiunii din starea curentă în starea următoare.

Exemplu de cea mai bună primă căutare

start_state = (0, 0)

stare_gol = (4, 4)

def heuristic_func(stare_actuală, stare_gol):

return abs(starea_actuală[0] – starea_gol[0]) + abs(starea_actuală[1] – starea_gol[1])

def action_func(stare_curenta):

acțiuni = []

dacă starea_actuală[0] > 0:

actions.append(starea lambda: (stare[0]-1, stare[1]))

dacă starea_actuală[0] < 4:

actions.append(stare lambda: (stare[0]+1, stare[1]))

dacă starea_actuală[1] > 0:

actions.append(starea lambda: (stare[0], stare[1]-1))

dacă starea_actuală[1] < 4:

actions.append(starea lambda: (stare[0], stare[1]+1))

acțiuni de returnare

def cost_func(stare_actuală, acțiune, stare_următoare):

întoarce 1

cale = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

dacă calea:

# construiți calea de la starea de început până la starea de obiectiv

stare_actuală = stare_gol

în timp ce starea_actuală != stare_început:

print(starea_actuala)

stare_actuală = cale[stare_actuală]

print(start_start)

altceva:

print(„Starea obiectivului nu este accesibilă.”)

Avantajele Best First Search

• În comparație cu căutarea pe lățimea întâi, complexitatea de timp a căutării cel mai bun primul este mai mică.
• Cea mai bună căutare primă obține și implementează avantajele atât ale algoritmilor BFS, cât și ale DFS

Dezavantajele Best First Search

• Uneori poate acoperi mai multă distanță decât este considerat.
• Șansele de a rămâne blocat într-o buclă sunt foarte probabile.

O cautare

Căutarea A* este un algoritm de căutare care utilizează atât costul de a ajunge la un nod de la nodul de pornire, cât și o estimare a costului rămas pentru a ajunge la nodul obiectiv pentru a ghida căutarea acestuia. Algoritmul începe de la nodul inițial și examinează toate nodurile sale secundare, alegând copilul cu cel mai mic cost combinat și costul rămas estimat ca următorul nod de explorat. Acest proces continuă până când nodul obiectiv este găsit sau toate nodurile au fost explorate.

Căutare A* – un exemplu ilustrat

Să ne uităm din nou la exemplul anterior în care încercați să găsiți cel mai scurt traseu de la casa dvs. la un magazin alimentar din apropiere. Acum, ai putea:

1. Începeți din locația dvs. de acasă și calculați costul total pentru a ajunge la fiecare locație din apropiere ca suma distanței de la casa dvs. până la acea locație și costul estimat rămas pentru a ajunge la magazinul alimentar din acea locație.
2. Alegeți locația din apropiere cu cel mai mic cost total ca următorul nod de explorat.
3. Din locația respectivă din apropiere, calculați costul total pentru fiecare dintre locațiile copiilor săi ca suma distanței de la acea locație la locația copilului, costul pentru a ajunge la acea locație de la nodul de pornire și costul estimat rămas pentru a ajunge la magazinul alimentar. din locația respectivă a copilului. Alegeți locația copilului cu cel mai mic cost total ca următorul nod de explorat.
4. Repetați acest proces până ajungeți la magazin.

Un lucru important de remarcat aici este că A* Search este un algoritm de căutare optim care garantează găsirea celei mai scurte căi către starea obiectivului. Este eficient în probleme cu un spațiu mare de căutare și este utilizat pe scară largă în jocuri video, robotică și planificarea rutelor. Cu toate acestea, necesită o funcție euristică bine definită pentru a fi eficient. Din acest motiv, algoritmul poate consuma multă memorie și poate încetini în probleme complexe cu multe noduri.

Căutare A* – implementare Python

Iată cum puteți implementa algoritmul de căutare A* folosind programarea Python:

import heapq

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# inițializați setul de frontieră și explorat

frontier = [(functie_euristica(start_start, goal_state), start_state)]

explorat = set()

# inițializați calea și costul

cale = {}

cost = {}

cale[start_state] = Nici unul

cost[star_start] = 0

în timp ce frontieră:

# obțineți nodul cu cea mai mică valoare f de la frontieră

(f, starea_actuală) = heapq.heappop(frontieră)

dacă starea_actuală == starea_golului:

# returnează calea dacă este atinsă starea obiectivului

calea de intoarcere

explored.add(starea_actuală)

# genera acțiuni posibile din starea curentă

pentru acțiune în action_func(current_state):

următoarea_stare = acțiune(starea_actuală)

# calculați costul noii căi

cost_nou = cost[starea_actuală] + funcția_cost(starea_actuală, acțiune, starea_următoare)

dacă next_state nu este explorat și next_state nu este în [state for (f, state) in frontier]:

# adăugați noul stat la frontieră

heapq.heappush(frontieră, (new_cost + heuristic_func(next_state, goal_state), next_state))

cale[next_state] = stare_actuală

cost[next_state] = cost_nou

elif next_state în [state for (f, state) in frontier] și new_cost < cost[next_state]:

# actualizați costul statului existent la frontieră

index = [i pentru (i, (f, stare)) în enumerate(frontieră) dacă stare == următoarea_stare][0]

frontier[index] = (new_cost + heuristic_func(next_state, goal_state), next_state)

cale[next_state] = stare_actuală

cost[next_state] = cost_nou

# return None dacă starea obiectivului nu este accesibilă

return Niciunul

Top cursuri de învățare automată și cursuri AI online

Exemplu de căutare A*

Iată un exemplu despre cum puteți utiliza funcția astar_search cu aceste funcții:

start_state = (0, 0)

stare_gol = (4, 4)

def heuristic_func(stare_actuală, stare_gol):

return abs(starea_actuală[0] – starea_gol[0]) + abs(starea_actuală[1] – starea_gol[1])

def action_func(stare_curenta):

acțiuni = []

dacă starea_actuală[0] > 0:

actions.append(starea lambda: (stare[0]-1, stare[1]))

dacă starea_actuală[0] < 4:

actions.append(stare lambda: (stare[0]+1, stare[1]))

dacă starea_actuală[1] > 0:

actions.append(starea lambda: (stare[0], stare[1]-1))

dacă starea_actuală[1] < 4:

actions.append(starea lambda: (stare[0], stare[1]+1))

acțiuni de returnare

def cost_func(stare_actuală, acțiune, stare_următoare):

întoarce 1

cale = astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

dacă calea:

# construiți calea de la starea de început până la starea de obiectiv

stare_actuală = stare_gol

în timp ce starea_actuală != stare_început:

print(starea_actuala)

stare_actuală = cale[stare_actuală]

print(start_start)

altceva:

print(„Starea obiectivului nu este accesibilă.”)

Avantajele Căutării A*

• Este una dintre tehnicile euristice de vârf.
• Căutarea A* poate fi folosită pentru a rezolva probleme complexe de căutare

Abilități de învățare automată în tendințe

Dezavantajele Căutării A*

• Performanța căutării A* se bazează în mare măsură pe acuratețea algoritmilor euristici.
• Are o eficiență scăzută de căutare.

Bloguri populare AI și ML și cursuri gratuite

La pachet

Algoritmii de căutare informați sunt esențiali în inteligența artificială, deoarece permit computerului să caute o stare de obiectiv în mod eficient și eficient. Acești algoritmi folosesc funcții euristice pentru a estima costul fiecărei mișcări posibile și pentru a ghida procesul de căutare către starea obiectivului. Best First Search și A* Search sunt exemple de algoritmi de căutare informați utilizați pe scară largă în diverse domenii. Cu toate acestea, o funcție euristică bine definită este esențială pentru succesul algoritmilor de căutare informați.

Dacă sunteți interesat să aflați mai multe despre inteligența artificială și învățarea automată, consultați programul de master upGrad în învățare automată și inteligență artificială oferit de Universitatea John Moores din Liverpool . Acest program acoperă diverse subiecte de învățare automată și AI, inclusiv algoritmi precum căutarea informată. Urmând acest program, puteți dobândi abilitățile și cunoștințele de care aveți nevoie pentru a reuși într-o varietate de cariere legate de AI.

De asemenea, puteți consultacursurile noastre gratuiteoferite de upGrad în management, știința datelor, învățare automată, marketing digital și tehnologie.Toate aceste cursuri au resurse de învățare de top, prelegeri live săptămânale, sarcini din industrie și un certificat de absolvire a cursului - totul gratuit!