La cerca no informada és una classe d'algorismes de cerca de propòsit general que funciona amb força bruta. Els algorismes de cerca no informats no tenen informació addicional sobre l'estat o l'espai de cerca que no sigui com recórrer l'arbre, per la qual cosa també s'anomena cerca cega.
A continuació es mostren els diferents tipus d'algorismes de cerca no informats:
1. Cerca de l'amplada primer:
- La cerca en amplitud és l'estratègia de cerca més comuna per recórrer un arbre o un gràfic. Aquest algorisme cerca ample en un arbre o gràfic, per la qual cosa s'anomena cerca de l'amplada primer.
- L'algorisme BFS comença a cercar des del node arrel de l'arbre i expandeix tots els nodes successors al nivell actual abans de passar als nodes del següent nivell.
- L'algoritme de cerca en amplitud és un exemple d'algorisme de cerca de gràfics generals.
- La cerca en amplitud s'ha implementat mitjançant l'estructura de dades de la cua FIFO.
Avantatges:
- BFS proporcionarà una solució si existeix alguna solució.
- Si hi ha més d'una solució per a un problema determinat, BFS proporcionarà la solució mínima que requereixi el menor nombre de passos.
Desavantatges:
- Requereix molta memòria ja que cada nivell de l'arbre s'ha de desar a la memòria per ampliar el següent nivell.
- BFS necessita molt de temps si la solució està lluny del node arrel.
Exemple:
A l'estructura d'arbre següent, hem mostrat el recorregut de l'arbre mitjançant l'algorisme BFS des del node arrel S fins al node objectiu K. L'algoritme de cerca BFS travessa en capes, de manera que seguirà el camí que es mostra amb la fletxa puntejada i el el camí recorregut serà:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Complexitat temporal: La complexitat temporal de l'algorisme de BFS es pot obtenir pel nombre de nodes travessats en BFS fins al node més profund. On d= la profunditat de la solució més superficial i b és un node en cada estat.
T (b) = 1+b2+b3+.......+ bd= O (bd)
Complexitat espacial: La complexitat espacial de l'algorisme BFS ve donada per la mida de la memòria de la frontera que és O (bd).
Exhaustivitat: BFS està complet, el que significa que si el node d'objectiu més baix es troba a una profunditat finita, BFS trobarà una solució.
Optimitat: BFS és òptim si el cost del camí és una funció no decreixent de la profunditat del node.
2. Cerca en profunditat
- La cerca en profunditat és un algorisme recursiu per recórrer una estructura de dades d'arbre o gràfic.
- S'anomena cerca de profunditat primer perquè comença des del node arrel i segueix cada camí fins al node de profunditat més gran abans de passar al següent camí.
- DFS utilitza una estructura de dades de pila per a la seva implementació.
- El procés de l'algorisme DFS és similar a l'algorisme BFS.
Nota: el backtracking és una tècnica d'algorisme per trobar totes les solucions possibles mitjançant recursivitat.
Avantatge:
- DFS requereix molt menys memòria, ja que només necessita emmagatzemar una pila dels nodes al camí des del node arrel fins al node actual.
- Es necessita menys temps per arribar al node objectiu que l'algorisme BFS (si travessa pel camí correcte).
Desavantatge:
- Hi ha la possibilitat que molts estats es tornin a produir, i no hi ha cap garantia de trobar la solució.
- L'algorisme DFS serveix per a la cerca profunda i, en algun moment, pot anar al bucle infinit.
Exemple:
A l'arbre de cerca següent, hem mostrat el flux de cerca en profunditat i seguirà l'ordre com:
Node arrel--->Node esquerre ----> Node dret.
Començarà a cercar des del node arrel S i travessarà A, després B, després D i E, després de travessar E, tornarà a l'arbre ja que E no té cap altre successor i encara no es troba el node objectiu. Després de fer marxa enrere, travessarà el node C i després G, i aquí finalitzarà tal com va trobar el node objectiu.
Exhaustivitat: L'algorisme de cerca DFS està complet dins de l'espai d'estats finits, ja que ampliarà tots els nodes dins d'un arbre de cerca limitat.
Complexitat temporal: La complexitat temporal de DFS serà equivalent al node travessat per l'algorisme. Està donada per:
avl arbre
T(n)= 1+ n2+ n3+.........+ nm=O(nm)
On, m = profunditat màxima de qualsevol node i aquesta pot ser molt més gran que d (profunditat de solució més baixa)
Complexitat espacial: L'algorisme DFS només ha d'emmagatzemar un camí únic des del node arrel, per tant, la complexitat espacial de DFS és equivalent a la mida del conjunt de franges, que és O (bm) .
òptim: L'algorisme de cerca DFS no és òptim, ja que pot generar un gran nombre de passos o un alt cost per arribar al node objectiu.
3. Algorisme de cerca limitada per profunditat:
Un algorisme de cerca amb profunditat limitada és similar a la cerca en profunditat amb un límit predeterminat. La cerca de profunditat limitada pot resoldre l'inconvenient del camí infinit a la cerca de profunditat primer. En aquest algorisme, el node al límit de profunditat tractarà com no té nodes successors més.
La cerca limitada en profunditat es pot finalitzar amb dues condicions d'error:
- Valor de fallada estàndard: indica que el problema no té cap solució.
- Valor de fallada de tall: No defineix cap solució per al problema dins d'un límit de profunditat determinat.
Avantatges:
La cerca amb profunditat limitada és eficient amb la memòria.
Desavantatges:
- La cerca limitada en profunditat també té un desavantatge d'incompletezza.
- Pot ser que no sigui òptim si el problema té més d'una solució.
Exemple:
Exhaustivitat: L'algorisme de cerca DLS està complet si la solució està per sobre del límit de profunditat.
Complexitat temporal: La complexitat temporal de l'algorisme DLS és O (bℓ) .
Complexitat espacial: La complexitat espacial de l'algorisme DLS és O (b�ℓ) .
òptim: La cerca limitada en profunditat es pot veure com un cas especial de DFS, i tampoc és òptima encara que ℓ>d.
4. Algoritme de cerca de cost uniforme:
La cerca de cost uniforme és un algorisme de cerca utilitzat per recórrer un arbre o gràfic ponderat. Aquest algorisme entra en joc quan hi ha disponible un cost diferent per a cada vora. L'objectiu principal de la cerca de cost uniforme és trobar un camí cap al node objectiu que tingui el cost acumulat més baix. La cerca de cost uniforme expandeix els nodes segons els seus costos de ruta del node arrel. Es pot utilitzar per resoldre qualsevol gràfic/arbre on es demana el cost òptim. La cua de prioritats implementa un algorisme de cerca de cost uniforme. Dóna la màxima prioritat al cost acumulat més baix. La cerca de cost uniforme és equivalent a l'algorisme BFS si el cost del camí de totes les vores és el mateix.
Avantatges:
- La cerca uniforme de costos és òptima perquè a cada estat s'escull el camí amb el menor cost.
Desavantatges:
- No li importa el nombre de passos que implica la cerca i només es preocupa pel cost del camí. A causa del qual aquest algorisme pot quedar atrapat en un bucle infinit.
Exemple:
Exhaustivitat:
La cerca de costos uniformes està completa, com ara si hi ha una solució, UCS la trobarà.
Complexitat temporal:
Sigui C* és el cost de la solució òptima , i e és cada pas per acostar-se al node objectiu. Aleshores el nombre de passos és = C*/ε+1. Aquí hem pres +1, ja que comencem de l'estat 0 i acabem a C*/ε.
Per tant, la complexitat temporal del pitjor dels casos de la cerca de cost uniforme és O (b1 + [C*/e])/ .
Complexitat espacial:
La mateixa lògica és per a la complexitat espacial, de manera que la complexitat espacial en el pitjor dels casos de la cerca de cost uniforme és O (b1 + [C*/e]) .
òptim:
La cerca de cost uniforme és sempre òptima, ja que només selecciona un camí amb el cost més baix.
5. Aprofundiment iteratiu-primer cerca:
L'algorisme d'aprofundiment iteratiu és una combinació d'algoritmes DFS i BFS. Aquest algorisme de cerca descobreix el millor límit de profunditat i ho fa augmentant gradualment el límit fins que es troba un objectiu.
Aquest algorisme realitza una cerca en profunditat fins a un cert 'límit de profunditat' i continua augmentant el límit de profunditat després de cada iteració fins que es troba el node objectiu.
Aquest algorisme de cerca combina els avantatges de la cerca ràpida de la cerca en profunditat i l'eficiència de la memòria de la cerca en profunditat.
L'algorisme de cerca iterativa és útil per a la cerca no informada quan l'espai de cerca és gran i es desconeix la profunditat del node de l'objectiu.
Avantatges:
- Combina els avantatges de l'algoritme de cerca BFS i DFS en termes de cerca ràpida i eficiència de memòria.
Desavantatges:
- El principal inconvenient de l'IDDFS és que repeteix tot el treball de la fase anterior.
Exemple:
L'estructura d'arbre següent mostra la recerca iterativa d'aprofundiment en profunditat. L'algorisme IDDFS realitza diverses iteracions fins que no troba el node objectiu. La iteració realitzada per l'algorisme es dóna com:
1a iteració-----> A
2a iteració ----> A, B, C
3a iteració ------> A, B, D, E, C, F, G
4a iteració ------> A, B, D, H, I, E, C, F, K, G
A la quarta iteració, l'algoritme trobarà el node objectiu.
Exhaustivitat:
Aquest algorisme és complet si el factor de ramificació és finit.
Complexitat temporal:
Suposem que b és el factor de ramificació i la profunditat és d, aleshores la complexitat temporal en el pitjor dels casos és O (bd) .
Complexitat espacial:
cua de prioritats
La complexitat espacial de l'IDDFS serà O(bd) .
òptim:
L'algorisme IDDFS és òptim si el cost del camí és una funció no decreixent de la profunditat del node.
6. Algorisme de cerca bidireccional:
L'algorisme de cerca bidireccional executa dues cerques simultànies, una de l'estat inicial anomenada cerca cap endavant i una altra des del node objectiu anomenada cerca cap enrere, per trobar el node objectiu. La cerca bidireccional substitueix un únic gràfic de cerca per dos petits subgrafs en els quals un comença la cerca des d'un vèrtex inicial i l'altre comença des del vèrtex de l'objectiu. La cerca s'atura quan aquests dos gràfics es creuen.
La cerca bidireccional pot utilitzar tècniques de cerca com BFS, DFS, DLS, etc.
Avantatges:
- La cerca bidireccional és ràpida.
- La cerca bidireccional requereix menys memòria
Desavantatges:
- La implementació de l'arbre de cerca bidireccional és difícil.
Exemple:
A l'arbre de cerca següent, s'aplica l'algorisme de cerca bidireccional. Aquest algorisme divideix un gràfic/arbre en dos subgràfics. Comença a travessar des del node 1 en direcció cap endavant i comença des del node objectiu 16 en direcció enrere.
L'algorisme acaba al node 9 on es troben dues cerques.
Exhaustivitat: La cerca bidireccional és completa si fem servir BFS en ambdues cerques.
Complexitat temporal: La complexitat temporal de la cerca bidireccional amb BFS és O (bd) .
Complexitat espacial: La complexitat espacial de la cerca bidireccional és O (bd) .
òptim: La cerca bidireccional és òptima.