Tuttavia, tra tecniche di ricerca informate e disinformate, la ricerca informata è più efficiente ed economica.
Grafico comparativo
| Base per il confronto | Ricerca informata | Ricerca non informata |
|---|---|---|
| Di base | Usa la conoscenza per trovare i passaggi per la soluzione. | Nessun uso della conoscenza |
| Efficienza | Altamente efficiente poiché consuma meno tempo e costi. | L'efficienza è mediatica |
| Costo | Basso | Relativamente alto |
| Prestazione | Trova la soluzione più rapidamente | La velocità è più lenta della ricerca informata |
| algoritmi | Ricerca per profondità, ricerca per ampiezza e ricerca per il costo più basso | Profondità euristica prima e ricerca per ampiezza e ricerca A * |
Definizione di ricerca informata
La tecnica di ricerca informata utilizza la conoscenza specifica del problema per dare un indizio alla soluzione del problema. Questo tipo di strategia di ricerca impedisce effettivamente agli algoritmi di inciampare sull'obiettivo e sulla direzione della soluzione. La ricerca informata può essere vantaggiosa in termini di costo in cui l'ottimalità viene raggiunta a costi di ricerca inferiori.
Per cercare un costo di percorso ottimale in un grafico implementando la strategia di ricerca informata, i nodi più promettenti n vengono inseriti nella funzione euristica h (n). Quindi la funzione restituisce un numero reale non negativo che è un costo approssimativo del percorso calcolato dal nodo n al nodo di destinazione.
Qui la parte più importante della tecnica informata è la funzione euristica che facilita l'apprendimento della conoscenza aggiuntiva del problema all'algoritmo. Di conseguenza, aiuta a trovare la strada verso l'obiettivo attraverso i vari nodi vicini. Esistono vari algoritmi basati sulla ricerca informata come ricerca euristica in profondità, ricerca euristica in ampiezza, ricerca A *, eccetera. Ora comprendiamo la ricerca euristica di profondità.
Profondità euristica Prima ricerca
Simile al metodo di ricerca in profondità prima sotto la profondità euristica, la prima ricerca sceglie un percorso ma attraversa tutti i percorsi dal percorso selezionato prima di scegliere un altro percorso. Tuttavia, sceglie il percorso migliore localmente. Nei casi in cui il più piccolo valore euristico è la priorità per la frontiera, allora è noto come la migliore prima ricerca.
Un altro algoritmo di ricerca informato è la ricerca A * che unisce il concetto di costo più basso alla prima e migliore prima ricerca. Questo metodo considera sia il costo del percorso che le informazioni euristiche nel processo di ricerca e selezione del percorso da espandere. Un costo totale stimato del percorso utilizzato per ciascun percorso che si trova sulla frontiera dall'inizio al nodo di destinazione. Pertanto utilizza due funzioni contemporaneamente: costo (p) è il costo del percorso rilevato e h (p) è il valore stimato del costo del percorso dal nodo iniziale al nodo obiettivo.
Definizione di ricerca non pubblicata
La ricerca non informata è diversa dalla ricerca informata nel modo in cui fornisce solo la definizione del problema, ma senza ulteriori passaggi per trovare la soluzione al problema. L'obiettivo principale della ricerca non informata è di distinguere tra lo stato target e non target e ignora totalmente la destinazione verso cui si sta dirigendo nel percorso fino a quando non scopre l'obiettivo e segnala il successore. Questa strategia è anche conosciuta come ricerca cieca.
Esistono vari algoritmi di ricerca in questa categoria, come la ricerca in profondità, la ricerca uniforme dei costi, la ricerca in ampiezza e così via. Vediamo ora il concetto alla base della ricerca disinformata con l'aiuto della ricerca approfondita.
Profondità prima ricerca
Nella prima ricerca approfondita, viene utilizzato uno stack Last in first out per aggiungere e rimuovere i nodi. Solo un nodo viene aggiunto o rimosso alla volta e il primo elemento rimosso dalla frontiera dello stack sarà l'ultimo elemento aggiunto allo stack. Impiegando la pila nella frontiera, i risultati nella ricerca dei percorsi procedevano in profondità nella prima maniera. Quando si ricerca un percorso più breve e ottimale utilizzando la ricerca in profondità, il percorso creato dai nodi adiacenti viene completato per primo anche se non è quello desiderato. Quindi il percorso alternativo viene cercato attraverso il backtracking.
In altre parole, l'algoritmo sceglie la prima alternativa su ciascun nodo, quindi torna indietro a un'altra alternativa finché non ha attraversato tutti i percorsi dalla prima selezione. Ciò solleva anche un problema in cui la ricerca potrebbe cessare di arrestarsi a causa di cicli infiniti (cicli) presenti nel grafico.
Differenze chiave tra ricerca informata e non informata
- La precedente tecnica di ricerca informata utilizza la conoscenza per trovare la soluzione. D'altra parte, quest'ultima tecnica di ricerca non informata non usa la conoscenza. In termini più semplici non sono fornite ulteriori informazioni sulla soluzione.
- L'efficienza della ricerca informata è migliore della ricerca non informata.
- La ricerca non informata consuma più tempo e costi in quanto non ha idea della soluzione rispetto alla ricerca informata.
- La ricerca approfondita, la ricerca in ampiezza e la ricerca con il minor costo sono gli algoritmi che rientrano nella categoria della ricerca non informata. In confronto, la ricerca informata copre gli algoritmi come la ricerca euristica di profondità prima, euristica e A *.
Conclusione
La ricerca informata fornisce la direzione per quanto riguarda la soluzione mentre nella ricerca non informata non viene fornito alcun suggerimento riguardo alla soluzione. Ciò rende la ricerca non informato più lunga quando viene implementato l'algoritmo.
