Tutto sulla ricerca informata nell'intelligenza artificiale

La ricerca informata è un tipo di algoritmo di ricerca che utilizza la conoscenza specifica del dominio per guidare la sua ricerca attraverso uno spazio problematico. Dai sistemi di navigazione ai giochi, dall'elaborazione del linguaggio naturale alla gestione della catena di approvvigionamento e una ricerca più informata nell'intelligenza artificiale ha ridotto significativamente la quantità di tempo e le risorse computazionali necessarie per risolvere diversi problemi.

Utilizzando la conoscenza specifica del dominio per guidare la ricerca, gli algoritmi di ricerca informati possono eliminare rapidamente percorsi irrilevanti o meno promettenti, consentendo alla ricerca di concentrarsi sulle opzioni più promettenti. Per fare ciò, questi tipi di algoritmi di ricerca nell'IA utilizzano l'euristica per migliorare l'efficienza e la velocità della ricerca.

Iscriviti al corso di machine learning delle migliori università del mondo. Guadagna programmi Master, Executive PGP o Advanced Certificate per accelerare la tua carriera.

Questo articolo discuterà il concetto di ricerca informata nell'intelligenza artificiale, le sue funzioni euristiche, esempi di algoritmi e i loro vantaggi e svantaggi.

Funzione euristica

In termini semplici, una funzione euristica è un approccio alla risoluzione dei problemi che utilizza una regola empirica o una "ipotesi migliore" per stimare la distanza o il costo di uno stato obiettivo in un problema di ricerca. La funzione euristica stima la distanza tra lo stato dell'obiettivo e lo stato corrente, che può essere utilizzata per guidare un algoritmo di ricerca verso l'obiettivo.

Gli algoritmi di ricerca informata utilizzano queste funzioni come fonte aggiuntiva di informazioni per prendere decisioni informate sul percorso da intraprendere. Per questo motivo, le funzioni euristiche sono essenziali negli algoritmi di ricerca informata.

Esempi reali di funzione euristica

Per comprendere meglio le funzioni euristiche, ecco alcuni esempi di vita reale:

• Nel classico gioco del “puzzle a tessere scorrevoli”, una semplice funzione euristica potrebbe essere quella di contare il numero di tessere fuori posto nella configurazione attuale rispetto alla configurazione obiettivo. Più tessere sono fuori posto, più lo stato attuale è lontano dallo stato obiettivo.
• Negli scacchi, una funzione euristica potrebbe essere quella di assegnare un valore a ciascun pezzo sulla scacchiera in base alla sua forza relativa e posizione e utilizzare la somma di tali valori per stimare il vantaggio o lo svantaggio del giocatore attuale. Questa funzione euristica può essere utilizzata per guidare un algoritmo di ricerca verso mosse che potrebbero portare a una posizione migliore.

Detto questo, andiamo avanti e comprendiamo alcuni degli esempi più utilizzati di algoritmi di ricerca informati nell'intelligenza artificiale.

Esempi di algoritmi di ricerca informata

Due degli algoritmi di ricerca informata più comunemente utilizzati includono la migliore prima ricerca e la ricerca A*. Comprendiamo questi due algoritmi insieme ad alcuni esempi, vantaggi, svantaggi e la loro implementazione Python:

1. Migliore prima ricerca

La migliore prima ricerca è un algoritmo di ricerca che espande prima il nodo più promettente, secondo una funzione euristica. L'algoritmo parte dal nodo iniziale ed esamina tutti i suoi nodi figli, scegliendo il figlio con il valore euristico più basso come nodo successivo da esplorare. Questo processo continua finché non viene trovato il nodo obiettivo o tutti i nodi sono stati esplorati.

Miglior prima ricerca – un esempio illustrato

Ecco un semplice esempio per illustrare la migliore prima ricerca:

Supponiamo che tu stia cercando di trovare il percorso più breve da casa tua a un negozio di alimentari nelle vicinanze. Conosci la distanza dal negozio di alimentari da alcune località vicine, ma non conosci il percorso esatto da seguire. Per risolvere questo problema utilizzando la ricerca best-first, potresti:

1. Inizia dalla tua posizione di casa e calcola il valore euristico per ogni posizione vicina in base alla sua distanza dal negozio di alimentari.
2. Scegli la posizione vicina con il valore euristico più basso come nodo successivo da esplorare.
3. Calcola il valore euristico per ciascuna delle posizioni dei suoi figli da quella posizione vicina e scegli quella con il valore euristico più basso come nodo successivo da esplorare.
4. Ripeti questo processo fino a raggiungere il negozio di alimentari.

Migliore prima ricerca: implementazione di Python

Ecco come puoi implementare il miglior primo algoritmo di ricerca in Python:

importa heapq

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

# inizializza la frontiera e l'insieme esplorato

frontiera = [(heuristic_func(start_state, goal_state), start_state)]

esplorato = set()

# inizializza il percorso e il costo

percorso = {}

costo = {}

percorso[start_state] = Nessuno

costo[start_state] = 0

mentre frontiera:

# ottiene il nodo con il valore euristico più basso dalla frontiera

(h, stato_corrente) = heapq.heappop(frontiera)

se stato_corrente == stato_obiettivo:

# restituisce il percorso se viene raggiunto lo stato obiettivo

sentiero di ritorno

esplorato.aggiungi(stato_corrente)

# genera possibili azioni dallo stato attuale

per l'azione in actions_func(current_state):

next_state = azione(current_state)

# calcola il costo del nuovo percorso

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

se next_state non in explored e next_state non in [state for (h, state) in frontier]:

# aggiunge il nuovo stato alla frontiera

heapq.heappush(frontier, (heuristic_func(next_state, goal_state), next_state))

percorso[next_state] = current_state

costo[prossimo_stato] = nuovo_costo

# restituisce None se lo stato obiettivo non è raggiungibile

restituire Nessuno

Come puoi vedere, dovrai definire le seguenti funzioni:

• heuristic_func(current_state, goal_state): questa funzione prende lo stato corrente e lo stato obiettivo come input e restituisce una stima del costo per raggiungere lo stato obiettivo dallo stato corrente.
• actions_func(current_state): questa funzione accetta lo stato corrente come input e restituisce un elenco di azioni che possono essere intraprese dallo stato corrente.
• cost_func(current_state, action, next_state): questa funzione accetta lo stato corrente, un'azione e lo stato successivo come input e restituisce il costo dell'azione dallo stato corrente allo stato successivo.

Esempio di Best First Search

start_state = (0, 0)

obiettivo_stato = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(stato_corrente[0] – stato_obiettivo[0]) + abs(stato_corrente[1] – stato_obiettivo[1])

def azioni_func(stato_corrente):

azioni = []

se stato_corrente[0] > 0:

azioni.append(stato lambda: (stato[0]-1, stato[1]))

se stato_corrente[0] < 4:

azioni.append(stato lambda: (stato[0]+1, stato[1]))

se stato_corrente[1] > 0:

azioni.append(stato lambda: (stato[0], stato[1]-1))

se stato_corrente[1] < 4:

azioni.append(stato lambda: (stato[0], stato[1]+1))

azioni di ritorno

def cost_func(current_state, action, next_state):

ritorno 1

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

se percorso:

# costruisce il percorso dallo stato iniziale allo stato obiettivo

stato_corrente = stato_obiettivo

while stato_corrente != stato_inizio:

print(stato_corrente)

stato_corrente = percorso[stato_corrente]

stampa(start_state)

altro:

print("Lo stato obiettivo non è raggiungibile.")

Vantaggi della migliore prima ricerca

• Rispetto alla ricerca in ampiezza, la complessità temporale della ricerca best-first è inferiore.
• La migliore prima ricerca ottiene e implementa i vantaggi di entrambi gli algoritmi BFS e DFS

Svantaggi della migliore prima ricerca

• A volte può coprire una distanza maggiore di quella considerata.
• Le possibilità di rimanere bloccati in un loop sono molto probabili.

Una ricerca

Una ricerca * è un algoritmo di ricerca che utilizza sia il costo per raggiungere un nodo dal nodo iniziale sia una stima del costo rimanente per raggiungere il nodo obiettivo per guidarne la ricerca. L'algoritmo parte dal nodo iniziale ed esamina tutti i suoi nodi figli, scegliendo il figlio con il costo combinato più basso e il costo rimanente stimato come nodo successivo da esplorare. Questo processo continua finché non viene trovato il nodo obiettivo o tutti i nodi sono stati esplorati.

A* ricerca – un esempio illustrato

Rivediamo l'esempio precedente in cui cerchi di trovare il percorso più breve da casa tua a un negozio di alimentari nelle vicinanze. Ora potresti:

1. Inizia dalla tua posizione di casa e calcola il costo totale per raggiungere ogni posizione vicina come la somma della distanza da casa tua a quella posizione e il costo rimanente stimato per raggiungere il negozio di alimentari da quella posizione.
2. Scegli la posizione vicina con il costo totale più basso come nodo successivo da esplorare.
3. Da quella posizione vicina, calcola il costo totale per ciascuna delle sue posizioni secondarie come la somma della distanza da tale posizione alla posizione secondaria, il costo per raggiungere tale posizione dal nodo iniziale e il costo rimanente stimato per raggiungere il negozio di alimentari da quella posizione figlio. Scegli la località secondaria con il costo totale più basso come nodo successivo da esplorare.
4. Ripeti questo processo fino a raggiungere il negozio di alimentari.

Una cosa importante da notare qui è che A* Search è un algoritmo di ricerca ottimale che garantisce di trovare il percorso più breve per lo stato obiettivo. È efficiente nei problemi con un ampio spazio di ricerca ed è ampiamente utilizzato nei videogiochi, nella robotica e nella pianificazione del percorso. Tuttavia, richiede una funzione euristica ben definita per essere efficace. Per questo motivo, l'algoritmo può richiedere molta memoria e rallentare in problemi complessi con molti nodi.

A* search – Implementazione di Python

Ecco come implementare l'algoritmo di ricerca A* utilizzando la programmazione Python:

importa heapq

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

# inizializza la frontiera e l'insieme esplorato

frontiera = [(heuristic_func(start_state, goal_state), start_state)]

esplorato = set()

# inizializza il percorso e il costo

percorso = {}

costo = {}

percorso[start_state] = Nessuno

costo[start_state] = 0

mentre frontiera:

# ottiene il nodo con il valore f più basso dalla frontiera

(f, stato_corrente) = heapq.heappop(frontiera)

se stato_corrente == stato_obiettivo:

# restituisce il percorso se viene raggiunto lo stato obiettivo

sentiero di ritorno

esplorato.aggiungi(stato_corrente)

# genera possibili azioni dallo stato attuale

per l'azione in actions_func(current_state):

next_state = azione(current_state)

# calcola il costo del nuovo percorso

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

se next_state non in explored e next_state non in [state for (f, state) in frontier]:

# aggiunge il nuovo stato alla frontiera

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

percorso[next_state] = current_state

costo[prossimo_stato] = nuovo_costo

elif next_state in [state for (f, state) in frontier] e new_cost < cost[next_state]:

# aggiorna il costo dello stato esistente alla frontiera

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

frontiera[indice] = (new_cost + heuristic_func(next_state, goal_state), next_state)

percorso[next_state] = current_state

costo[prossimo_stato] = nuovo_costo

# restituisce None se lo stato obiettivo non è raggiungibile

restituire Nessuno

I migliori corsi di machine learning e corsi di intelligenza artificiale online

Esempio di ricerca A*

Ecco un esempio di come potresti usare la funzione astar_search con queste funzioni:

start_state = (0, 0)

obiettivo_stato = (4, 4)

def heuristic_func(current_state, goal_state):

return abs(stato_corrente[0] – stato_obiettivo[0]) + abs(stato_corrente[1] – stato_obiettivo[1])

def azioni_func(stato_corrente):

azioni = []

se stato_corrente[0] > 0:

azioni.append(stato lambda: (stato[0]-1, stato[1]))

se stato_corrente[0] < 4:

azioni.append(stato lambda: (stato[0]+1, stato[1]))

se stato_corrente[1] > 0:

azioni.append(stato lambda: (stato[0], stato[1]-1))

se stato_corrente[1] < 4:

azioni.append(stato lambda: (stato[0], stato[1]+1))

azioni di ritorno

def cost_func(current_state, action, next_state):

ritorno 1

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

se percorso:

# costruisce il percorso dallo stato iniziale allo stato finale

stato_corrente = stato_obiettivo

while stato_corrente != stato_inizio:

print(stato_corrente)

stato_corrente = percorso[stato_corrente]

stampa(start_state)

altro:

print("Lo stato obiettivo non è raggiungibile.")

Vantaggi della ricerca A*

• È una delle principali tecniche euristiche.
• La ricerca A* può essere sfruttata per risolvere problemi di ricerca complessi

Competenze di apprendimento automatico di tendenza

Svantaggi della ricerca A*

• Le prestazioni di ricerca A* dipendono fortemente dall'accuratezza degli algoritmi euristici.
• Ha una bassa efficienza di ricerca.

Blog popolari su AI e ML e corsi gratuiti

Porta via

Gli algoritmi di ricerca informati sono essenziali nell'intelligenza artificiale poiché consentono al computer di cercare uno stato obiettivo in modo efficiente ed efficace. Questi algoritmi utilizzano funzioni euristiche per stimare il costo di ogni possibile mossa e guidare il processo di ricerca verso lo stato obiettivo. Best First Search e A* Search sono esempi di algoritmi di ricerca informati ampiamente utilizzati in vari campi. Tuttavia, una funzione euristica ben definita è fondamentale per il successo degli algoritmi di ricerca informati.

Se sei interessato a saperne di più sull'intelligenza artificiale e l'apprendimento automatico, dai un'occhiata al programma upGrad's Masters in Machine Learning & Artificial Intelligence offerto dalla Liverpool John Moores University . Questo programma copre vari argomenti di apprendimento automatico e intelligenza artificiale, inclusi algoritmi come la ricerca informata. Prendendo questo programma, puoi acquisire le competenze e le conoscenze necessarie per avere successo in una varietà di carriere legate all'IA.

Puoi anche dare un'occhiata ai nostricorsi gratuitiofferti da upGrad in Management, Data Science, Machine Learning, Digital Marketing e Tecnologia.Tutti questi corsi hanno risorse di apprendimento di prim'ordine, lezioni dal vivo settimanali, incarichi di settore e un certificato di completamento del corso, il tutto gratuitamente!