TechCodeview

Els algorismes de cerca són una de les àrees més importants de la Intel·ligència Artificial. Aquest tema explicarà tot sobre els algorismes de cerca en IA.

Agents de resolució de problemes:

En intel·ligència artificial, les tècniques de cerca són mètodes universals de resolució de problemes. Agents racionals o Agents de resolució de problemes en IA utilitzava principalment aquestes estratègies o algorismes de cerca per resoldre un problema específic i proporcionar el millor resultat. Els agents de resolució de problemes són els agents basats en objectius i utilitzen la representació atòmica. En aquest tema, aprendrem diversos algorismes de cerca per resoldre problemes.

Terminologies d'algorisme de cerca:

Cerca:La cerca és un procediment pas a pas per resoldre un problema de cerca en un espai de cerca determinat. Un problema de cerca pot tenir tres factors principals:
Espai de cerca:L'espai de cerca representa un conjunt de possibles solucions, que pot tenir un sistema.Estat inicial:És un estat des d'on comença l'agent la recerca .Prova d'objectius:És una funció que observa l'estat actual i retorna si s'aconsegueix o no l'estat objectiu.
Arbre de cerca:Una representació en arbre del problema de cerca s'anomena arbre de cerca. L'arrel de l'arbre de cerca és el node arrel que correspon a l'estat inicial.Accions:Ofereix la descripció de totes les accions disponibles a l'agent.Model de transició:Una descripció del que fa cada acció es pot representar com un model de transició.Cost del camí:És una funció que assigna un cost numèric a cada camí.Solució:És una seqüència d'acció que condueix des del node inicial fins al node meta.Solució òptima:Si una solució té el cost més baix entre totes les solucions.

Propietats dels algorismes de cerca:

A continuació es mostren les quatre propietats essencials dels algorismes de cerca per comparar l'eficiència d'aquests algorismes:

Exhaustivitat: Es diu que un algorisme de cerca està complet si garanteix retornar una solució si almenys existeix alguna solució per a qualsevol entrada aleatòria.

Optimitat: Si es garanteix que una solució trobada per a un algorisme és la millor solució (cost del camí més baix) entre totes les altres solucions, es diu que aquesta solució és la solució òptima.

Complexitat temporal: La complexitat del temps és una mesura del temps perquè un algorisme completi la seva tasca.

Complexitat espacial: És l'espai d'emmagatzematge màxim requerit en qualsevol moment de la cerca, com la complexitat del problema.

Tipus d'algorismes de cerca

A partir dels problemes de cerca podem classificar els algorismes de cerca en algorismes de cerca no informada (cerca cega) i de cerca informada (cerca heurística).

Cerca desinformada/cega:

La cerca no informada no conté cap coneixement del domini com ara la proximitat, la ubicació de l'objectiu. Funciona de manera bruta, ja que només inclou informació sobre com recórrer l'arbre i com identificar els nodes de fulla i objectiu. La cerca no informada aplica una manera en què es cerca l'arbre de cerca sense cap informació sobre l'espai de cerca com els operadors d'estat inicial i la prova de l'objectiu, per la qual cosa també s'anomena cerca cega. Examina cada node de l'arbre fins que aconsegueix el node objectiu.

Es pot dividir en cinc tipus principals:

• Cerca de l'amplada primer
• Cerca uniforme de costos
• Cerca en profunditat primer
• Recerca iterativa en profunditat primer
• Cerca bidireccional

Cerca informada

Els algorismes de cerca informats utilitzen el coneixement del domini. En una cerca informada, hi ha informació del problema disponible que pot guiar la cerca. Les estratègies de cerca informades poden trobar una solució de manera més eficient que una estratègia de cerca no informada. La cerca informada també s'anomena cerca heurística.

Una heurística és una manera que potser no sempre es garanteix per obtenir les millors solucions, però garanteix trobar una bona solució en un temps raonable.

La cerca informada pot resoldre problemes molt complexos que no es podrien resoldre d'una altra manera.

Un exemple d'algoritmes de cerca informada és un problema de venedor ambulant.

1. Cerca cobdiciosa
2. A* Cerca