Algorisme heurístic

En el món de la computació, hi ha dos objectius fonamentals, i són, trobar algorismes amb bons temps d'execució i bones solucions, usualment les òptimes. Els algorismes heurístics abandonen un o tots dos objectius, per exemple, normalment troben bones solucions, encara que no hi ha proves que la solució no pugui ser arbitràriament errònia en alguns casos, o s'executen raonablement ràpids, encara que no existeix tampoc prova que sempre serà així. Les heurístiques generalment són usades quan no hi ha una solució òptima sota les restriccions donades (temps, espai, etc.), o quan no existeix en absolut.

Sovint, poden trobar instàncies concretes del problema on l'heurística produirà resultats molt dolents o s'executarà molt lentament. Tot i això, aquestes instàncies concretes poden ser ignorades perquè no haurien de passar mai a la pràctica per ser d'origen teòric. Per tant, l'ús d'heurístiques és molt comú en el món real.

Algorismes heurístics per a trobar el camí més curt

Per problemes de recerca del camí més curt el terme té un significat més específic. En aquest cas una heurística és una funció matemàtica, $h(n)$ definida en els nodes d'un arbre de cerca , que serveix com una estimació del cost del camí més econòmic d'un node donat fins al node objectiu. Les heurístiques s'usen en els algoritmes de cerca informada com la recerca egoista. Hi egoista escollirà el node que té el valor més baix en la funció heurística. A * s'expandirà els nodes que tenen el valor més baix per $g(n)+h(n)$, on $g(n)$ és el cost (exacte) del camí des l'estat inicial al node actual. Quan $h(n)$ és admissible , això és si $h(n)$ mai sobreestima els costos de trobar l'objectiu; A * és probablement òptim.

Un problema clàssic que utilitza heurístiques és el joc del 15. Comptar el nombre de caselles mal col·locades i trobar la suma de la distància Manhattan entre cada bloc i la seva posició a l'objectiu són heurístiques utilitzades sovint per aquest problema.

Efecte dels algorismes heurístics en el rendiment computacional

En qualsevol problema de cerca on hi ha $b$ opcions en cada node i una profunditat $d$ al node objectiu, un algorisme de cerca ingenu haurà de buscar potencialment entre $b^{d}$ nodes abans de trobar la solució. Les heurístiques milloren l'eficiència dels algorismes de cerca reduint el factor de ramificació de $b$ a (idealment) una constant $b*$.

Encara que qualsevol heurística admissible retornarà una resposta òptima, una heurística que retorna un factor de ramificació més baix és computacionalment més eficient per al problema en particular. Pot demostrar-se que una heurística $h_{2}(n)$ és millor que una altra $h_{1}(n)$, si $h_{2}(n)$ domina $h_{1}(n)$, això vol dir que $h_{1}(n)<h_{2}(n)$ per a tot $n$.

Heurístiques a la Intel·ligència Artificial

Molts algorismes a la intel·ligència artificial són heurístics per naturalesa, o fan servir regles heurístiques. Un exemple recent és SpamAssassin que utilitza una àmplia varietat de regles heurístiques per determinar quan un correu electrònic és spam. Qualsevol de les regles usades de forma independent poden portar a errors de classificació, però quan s'uneixen múltiples regles heurístiques, la solució és més robusta i creïble. Això s'anomena alta credibilitat en el reconeixement de patrons (extret de les estadístiques en què es basa). Quan s'usa la paraula heurística en el processament del llenguatge basat en regles, el reconeixement de patrons o el processament d'imatges, és usada per referir-se a les regles.

Vegeu també

• Metaheurística.
• Heurística en antivirus.
• Algorisme voraç