Busques no informades
En ciències de la computació, els métodos de busca no informats o cegos són estratègies de busca en les quals s'evalua el següent estat sense conéixer a priori si este és millor o pijor que l'anterior.
Busca informada vs no informada
[editar | editar còdic]Un problema típic de l'inteligència artificial consistix en buscar un estat concret entre un conjunt determinat, al que se li crida espai d'estats. Imaginem, per eixemple, una habitació en baldosines en la que hi ha un llibre. Un robot es desija desplaçar per l'habitació en la finalitat d'aplegar a dit llibre. ¿De quina manera ho farà? En este punt és a on entren en joc les estratègies i els algoritmes de busca.
Quan el sistema agent (en este cas, el robot) posseïx algun tipo d'informació del mig, s'utilisen tècniques de busques informades; no obstant, si carix de coneiximent algun, es deuran amprar algoritmes de busca no informades. En el nostre eixemple, i per a este últim cas, podem imaginar un robot que no posseïxca cap tipo de visió artificial, que únicament siga capaç de moure's en horisontal o vertical d'un baldosín a un atre i detectar si en el baldosín es troba el llibre.
En general els algoritmes cegos són més ineficientes en temps i memòria que atres métodos, tals com els heurístics o la busca en adversari:
- Algoritmes heurístics: destaquen les Busques Primer el Millor (Algoritme voraç o Greedy i Algoritme de busca A*) i de Millora Iterativa (Algoritme Escalada Simple -Hill Climbing- i Escalada per Màxima Pendent)
- Algoritmes de Busca en adversari: destaquen el Minimax i el Poda alfa-beta.
Representació de l'espai d'estats
[editar | editar còdic]El conjunt d'estats que l'agent (en el nostre eixemple, el robot) deu recórrer, generalment es representa per mig d'un grafo, encara que en alguns casos concrets utilisarem arbres. Seguint en el nostre eixemple, cada nodo del grafo representarà a un dels baldosines de l'habitació, i dos nodos seran adjacents si també ho són els seus baldosines corresponents.
El grafo del dibuix en la part inferior representa el tauler de manera parcial, i cada nodo és identificat per un número. Suponem que la posició inicial del robot és el baldosín marcat en el número 1. En este grafo s'aplica una correspondència entre els nodos del mateix i els baldosines numerats d'igual forma. Com es pot observar en el tauler, per eixemple, el baldosín 1 és adjacent al 2 i al 5, i este fet queda plasmat en el dibuix mostrat.
Vore també
[editar | editar còdic]- Arbre (estructura de senyes)
- Busca en esgambi
- Busca en profunditat
- Inteligència artificial
- Coa (estructura de senyes)
- Pila (estructura de senyes)
- Este artícul conté una traducció derivada de «Búsquedas no informadas» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.