AI - Algoritmi di ricerca popolari

La ricerca è la tecnica universale di risoluzione dei problemi nell'IA. Ci sono alcuni giochi per giocatore singolo come giochi di tessere, sudoku, cruciverba, ecc. Gli algoritmi di ricerca ti aiutano a cercare una posizione particolare in tali giochi.

Problemi di individuazione del percorso di un singolo agente

I giochi come 3X3 a otto tessere, 4X4 a quindici tessere e 5X5 a ventiquattro tessere sono sfide per la ricerca del percorso da parte di un singolo agente. Sono costituiti da una matrice di tessere con una tessera vuota. Il giocatore è tenuto a disporre le tessere facendo scorrere una tessera verticalmente o orizzontalmente in uno spazio vuoto con l'obiettivo di raggiungere un obiettivo.

Gli altri esempi di problemi di individuazione del percorso di un singolo agente sono il problema del venditore ambulante, il cubo di Rubik e la dimostrazione di teoremi.

Terminologia di ricerca

Problem Space- È l'ambiente in cui avviene la ricerca. (Un insieme di stati e un insieme di operatori per modificare questi stati)
Problem Instance - È lo stato iniziale + lo stato dell'obiettivo.
Problem Space Graph- Rappresenta lo stato del problema. Gli stati sono mostrati dai nodi e gli operatori sono mostrati dai bordi.
Depth of a problem - Lunghezza di un percorso più breve o sequenza più breve di operatori dallo stato iniziale allo stato obiettivo.
Space Complexity - Il numero massimo di nodi archiviati in memoria.
Time Complexity - Il numero massimo di nodi che vengono creati.
Admissibility - Una proprietà di un algoritmo per trovare sempre una soluzione ottimale.
Branching Factor - Il numero medio di nodi figlio nel grafico dello spazio problema.
Depth - Lunghezza del percorso più breve dallo stato iniziale allo stato obiettivo.

Strategie di ricerca di forza bruta

Sono molto semplici, poiché non richiedono alcuna conoscenza specifica del dominio. Funzionano bene con un numero limitato di stati possibili.

Requisiti -

Descrizione dello stato
Un insieme di operatori validi
Stato iniziale
Descrizione dello stato dell'obiettivo

Ricerca in ampiezza

Inizia dal nodo radice, esplora prima i nodi vicini e si sposta verso i vicini di livello successivo. Genera un albero alla volta finché non viene trovata la soluzione. Può essere implementato utilizzando la struttura dati della coda FIFO. Questo metodo fornisce il percorso più breve alla soluzione.

Se branching factor(numero medio di nodi figli per un dato nodo) = be profondità = d, quindi numero di nodi a livello d = b ^d .

Il numero totale di nodi creati nel caso peggiore è b + b ² + b ³ +… + b ^d .

Disadvantage- Poiché ogni livello di nodi viene salvato per crearne uno successivo, consuma molto spazio di memoria. Lo spazio richiesto per memorizzare i nodi è esponenziale.

La sua complessità dipende dal numero di nodi. Può controllare i nodi duplicati.

Ricerca in profondità

È implementato in ricorsione con la struttura dati dello stack LIFO. Crea lo stesso insieme di nodi del metodo Breadth-First, solo nell'ordine diverso.

Poiché i nodi sul percorso singolo vengono archiviati in ogni iterazione dalla radice al nodo foglia, lo spazio richiesto per archiviare i nodi è lineare. Con il fattore di ramificazione b e la profondità come m , lo spazio di archiviazione è bm.

Disadvantage- Questo algoritmo potrebbe non terminare e continuare all'infinito su un percorso. La soluzione a questo problema è scegliere una profondità di taglio. Se il cut-off ideale è d , e se il cut-off scelto è minore di d , allora questo algoritmo potrebbe fallire. Se il valore limite scelto è maggiore di d , il tempo di esecuzione aumenta.

La sua complessità dipende dal numero di percorsi. Non può controllare i nodi duplicati.

Ricerca bidirezionale

Cerca in avanti dallo stato iniziale e all'indietro dallo stato obiettivo fino a quando entrambi si incontrano per identificare uno stato comune.

Il percorso dallo stato iniziale viene concatenato con il percorso inverso dallo stato obiettivo. Ogni ricerca viene eseguita solo fino alla metà del percorso totale.

Ricerca uniforme dei costi

L'ordinamento viene effettuato aumentando il costo del percorso verso un nodo. Espande sempre il nodo meno costoso. È identico alla ricerca Breadth First se ogni transizione ha lo stesso costo.

Esplora percorsi in ordine crescente di costo.

Disadvantage- Possono esserci più percorsi lunghi con il costo ≤ C *. La ricerca a costo uniforme deve esplorarli tutti.

Approfondimento iterativo Ricerca approfondita

Esegue la ricerca in profondità fino al livello 1, ricomincia, esegue una ricerca completa in profondità fino al livello 2 e continua in questo modo finché non viene trovata la soluzione.

Non crea mai un nodo finché non vengono generati tutti i nodi inferiori. Salva solo una pila di nodi. L'algoritmo termina quando trova una soluzione alla profondità d . Il numero di nodi creati alla profondità d è b ^d e alla profondità d-1 è b ^d-1.

Confronto di varie complessità di algoritmi

Vediamo le prestazioni degli algoritmi in base a vari criteri:

Criterio	Larghezza prima	Prima la profondità	Bidirezionale	Costo uniforme	Approfondimento interattivo
Tempo	b ^d	b ^m	b ^{d / 2}	b ^d	b ^d
Spazio	b ^d	b ^m	b ^{d / 2}	b ^d	b ^d
Ottimalità	sì	No	sì	sì	sì
Completezza	sì	No	sì	sì	sì

Strategie di ricerca informate (euristiche)

Per risolvere problemi di grandi dimensioni con un numero elevato di stati possibili, è necessario aggiungere conoscenze specifiche del problema per aumentare l'efficienza degli algoritmi di ricerca.

Funzioni di valutazione euristica

Calcolano il costo del percorso ottimale tra due stati. Una funzione euristica per i giochi con tessere scorrevoli viene calcolata contando il numero di mosse che ciascuna tessera fa dal suo stato obiettivo e aggiungendo questo numero di mosse per tutte le tessere.

Ricerca euristica pura

Espande i nodi nell'ordine dei loro valori euristici. Crea due elenchi, un elenco chiuso per i nodi già espansi e un elenco aperto per i nodi creati ma non espansi.

In ogni iterazione, un nodo con un valore euristico minimo viene espanso, tutti i suoi nodi figli vengono creati e inseriti nell'elenco chiuso. Quindi, la funzione euristica viene applicata ai nodi figlio e questi vengono inseriti nell'elenco aperto in base al loro valore euristico. I percorsi più brevi vengono salvati e quelli più lunghi vengono eliminati.

Una ricerca

È la forma più nota di ricerca Best First. Evita di espandere i percorsi che sono già costosi, ma espande prima i percorsi più promettenti.

f (n) = g (n) + h (n), dove

g (n) il costo (finora) per raggiungere il nodo
h (n) costo stimato per arrivare dal nodo all'obiettivo
f (n) costo totale stimato del percorso fino all'obiettivo. Viene implementato utilizzando la coda di priorità aumentando f (n).

Greedy Best First Search

Espande il nodo che si stima sia più vicino all'obiettivo. Espande i nodi in base a f (n) = h (n). Viene implementato utilizzando la coda di priorità.

Disadvantage- Può rimanere bloccato in loop. Non è ottimale.

Algoritmi di ricerca locale

Partono da una soluzione potenziale e poi passano a una soluzione vicina. Possono restituire una soluzione valida anche se viene interrotta in qualsiasi momento prima della fine.

Ricerca in salita

È un algoritmo iterativo che inizia con una soluzione arbitraria a un problema e tenta di trovare una soluzione migliore modificando in modo incrementale un singolo elemento della soluzione. Se la modifica produce una soluzione migliore, una modifica incrementale viene considerata come una nuova soluzione. Questo processo viene ripetuto fino a quando non ci sono ulteriori miglioramenti.

funzione Hill-Climbing (problema), restituisce uno stato che è un massimo locale.

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Disadvantage - Questo algoritmo non è né completo né ottimale.

Ricerca travi locali

In questo algoritmo, contiene k numero di stati in un dato momento. All'inizio, questi stati vengono generati in modo casuale. I successori di questi k stati vengono calcolati con l'aiuto della funzione obiettivo. Se uno di questi successori è il valore massimo della funzione obiettivo, l'algoritmo si ferma.

In caso contrario, gli stati (k stati iniziali ek numero di successori degli stati = 2k) vengono inseriti in un pool. Il pool viene quindi ordinato numericamente. I k stati più alti vengono selezionati come nuovi stati iniziali. Questo processo continua fino a quando non viene raggiunto un valore massimo.

funzione BeamSearch ( problema, k ), restituisce uno stato di soluzione.

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

Ricottura simulata

La ricottura è il processo di riscaldamento e raffreddamento di un metallo per cambiare la sua struttura interna per modificarne le proprietà fisiche. Quando il metallo si raffredda, la sua nuova struttura viene catturata e il metallo conserva le sue proprietà appena ottenute. Nel processo di ricottura simulata, la temperatura viene mantenuta variabile.

Inizialmente impostiamo la temperatura alta e poi lasciamo che si "raffreddi" lentamente mentre l'algoritmo procede. Quando la temperatura è alta, l'algoritmo può accettare soluzioni peggiori con alta frequenza.

Inizio

Inizializza k = 0; L = numero intero di variabili;
Da i → j, cerca la differenza di prestazioni Δ.
Se Δ <= 0 allora accetta altrimenti se exp (-Δ / T (k))> casuale (0,1) allora accetta;
Ripetere i passaggi 1 e 2 per i passaggi L (k).
k = k + 1;

Ripetere i passaggi da 1 a 4 finché i criteri non vengono soddisfatti.

Fine

Problema del commesso viaggiatore

In questo algoritmo, l'obiettivo è trovare un tour a basso costo che inizi da una città, visiti tutte le città lungo il percorso esattamente una volta e termini nella stessa città di partenza.

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end