L'Heurística

En aquesta entrada us vull parlar d'un pilar molt important dins la intel·ligència artificial: es tracta de l'heurística( Newell,Shaw i Simon el 1963). Molts algoritmes en IA són heurístics per naturalesa, o almenys, n'utilitzen. Qualsevol de les regles utilitzades de forma independent poden portar a errors de classificació, però quan s'uneixen varies regles heurístiques, la solució és més robusta i creïble.
Abans d'entrar en matèria permeteu-me que us expliqui una realitat molt simple: la capacitat heurística és un tret característic dels humans. Consisteix en la capacitat de realitzar innovacions positives per aconseguir els fins que es busquen. És a dir, tenim problemes les solucions dels quals les descobrim per avaluació del progrés aconseguit durant la recerca del resultat final.

Per a tots els lectors més joves (o no), heu de saber que és molt utilitzada en jocs on es preveuen i s'avancen els moviments als de l'usuari basant-se en l'experiència i els passos que ha seguit en les passades ocasions.
 Un altre exemple serien els programes que detecten si un correu és o no spam basant-se a partir d'experiències passades.

El principal problema de l'heurística, com haureu detectat amb el que he explicat, és que compleix a dues definicions: Dins la recerca, en MILLORAR L'EFICIÈNCIA i en NO GARANTIR EN TROBAR UN RESULTAT.

I entrant finalment en matèria, l'heurística dins la intel·ligència artificial es defineix com 

MÈTODE DE CERCA

 I tota la informació que se'ns proporciona per resoldre el problema ho denominarem com heurístiques.

La següent idea consisteix en concentrar tota la informació donada prèviament en una única funció que es denomina funció d'avaluació heurística. Tracta d'associar a cada estat del mapa d'estats, una quantitat numèrica que avalua d'alguna manera, com de bo és accedir a aquell estat. L'anomenarem funció h(e). A partir d'aquí, depenent de qui programi l'algorisme, normalment seran preferibles els canvis d'estat on els valors siguin mínims com el temps o els km (però en alguns casos ens interessarà que siguin màxims).

Un dels problemes més famosos de cerca heurística és el del Viatjant. Un Viatjant V vol anar des de un origen A fins a un destí B, però hi ha varies maneres d'arribar-hi. Ens imaginarem un mapa ple de ciutats i carreteres. Aquells que heu fet grafs, imagineu-vos les ciutats com vèrtexs i les carreteres com arestes. El nostre viatjant haurà d'arribar d'A a B passant per vàries ciutats on les carreteres tinguin valor mínim: trigui menys.  

Valor del camí total = valor del tram(x) + Valor del camí total fins ara

El nostre algoritme s'encarregarà d'això, però no ens assegura que tingui solució: pot ser que no hi hagi manera d'arribar d'A a B.

En aquests sentit, pot ser que el graf ja el tingui el nostre agent intel·ligent o que no: que es vagi generant a mesura que pren decisions.

Llavors definirem dos tipus de cerques: Irrevocable ( NO podem tirar enrere en els nostres passos) o Temptatiu (SÍ que podem tornar sobre els nostres passos).

Per entendre més el món de l'heurística, ens veiem a la pròxima entrada sobre els algoritmes A* i els arbres de cerca.