Content

• Gràfic de comparació
• Definició de cerca informada
• Primera cerca de fons heurístic
• Definició de cerca sense informació
• Profunditat Primera cerca
• Conclusió

La cerca és un procés de cerca d'una seqüència de passos necessària per resoldre qualsevol problema. La diferència prèvia entre la cerca informada i la no informada és que la cerca informada proporciona els consells sobre on i com trobar la solució. Per contra, la cerca sense informació no proporciona informació addicional sobre el problema, tret de la seva especificació.

No obstant això, entre tècniques de cerca tant informades com informades, la cerca informada és més eficient i rendible.

1. 1. Gràfic de comparació
   2. Definició
   3. Diferències claus
   4. Conclusió

Gràfic de comparació

Bases per a la comparació	Cerca Informada	Cerca desinformada
Bàsic	Utilitza coneixements per trobar els passos cap a la solució.	Cap ús del coneixement
Eficiència	Altament eficient ja que consumeix menys temps i cost.	L’eficiència és mediadora
Cost	baix	Comparativament alt
Rendiment	Troba la solució més ràpidament	La velocitat és més lenta que la cerca informada
Algorismes	Profunditat heurística primera i amplada primera cerca i A * cerca	Primera recerca en profunditat, primera cerca d'amplada i primera cerca de cost més baix

Definició de cerca informada

La tècnica de cerca informada utilitza coneixements específics del problema per donar una pista sobre la solució del problema. Aquest tipus d'estratègia de cerca impedeix que els algoritmes es trobin amb l'objectiu i la direcció cap a la solució. La cerca informada pot resultar avantatjosa quant al cost on s’obté l’optimitat a menors costos de cerca.

Per cercar un cost de ruta òptim en un gràfic implementant una estratègia de cerca informada, els nodes més prometedors s’insereixen a la funció heurística h (n). A continuació, la funció retorna un nombre real no negatiu que és un cost de ruta aproximat calculat des del node n al node de destinació.

Aquí la part més important de la tècnica informada és la funció heurística que facilita la impartició del coneixement addicional del problema a l'algorisme. Com a resultat, ajuda a trobar el camí cap a l'objectiu a través dels diversos nodes veïns. Hi ha diversos algoritmes basats en la cerca informada, com ara la recerca en primer lloc en profunditat heurística, la cerca heurística d’amplada primera, la cerca A *, etcètera. Entenem ara la primera recerca heurística en profunditat.

Primera cerca de fons heurístic

Semblant al mètode de cerca en profunditat detallat a sota de la cerca heurística, la primera cerca tria una ruta, però recorre tots els camins del camí seleccionat abans de triar un altre. Tot i això, tria el millor camí a nivell local. En els casos en què el valor heurístic més petit és la prioritat per a la frontera, es coneix com a millor cerca.

Un altre algorisme de cerca informada és A * search que fusiona el concepte de primer cost més baix i les millors primeres cerques. Aquest mètode té en compte tant el cost de ruta com la informació heurística en el procés de cerca i selecció del camí a ampliar. Un cost total estimat de ruta usat per a cada ruta que resideix a la frontera des del principi fins al node de destinació. Per tant, utilitza dues funcions alhora - cost (p) és el cost de la ruta descoberta i h (p) és el valor estimat del cost de ruta des del node inicial fins al node objectiu.

Definició de cerca sense informació

La cerca sense informació és diferent de la cerca informada de la manera que només proporciona la definició del problema, però no és un pas més per trobar la solució al problema. L’objectiu principal de la cerca sense informació és diferenciar entre l’estat objectiu i l’estat no objectiu, i ignora totalment la destinació a la qual s’orienta al camí fins que descobreixi l’objectiu i en informi el successor. Aquesta estratègia també es coneix com a cerca a cegues.

Hi ha diversos algoritmes de cerca d’aquesta categoria com ara la primera cerca en profunditat, la cerca uniforme de costos, la primera recerca d’amplada, etc. Entenem ara el concepte que hi ha darrere de la cerca sense informació amb l’ajuda de la primera cerca en profunditat.

Profunditat Primera cerca

A la primera cerca en profunditat, s'utilitza una pila Last in first out per afegir i eliminar nodes. Només s’afegeix o es treu un node alhora i el primer element eliminat de la frontera de la pila seria l’últim element afegit a la pila. Si s'utilitza una pila en els resultats de la frontera per cercar els camins, es va procedir a fons en primer lloc. Quan es busca un camí més curt i òptim mitjançant la primera cerca en profunditat, el camí creat pels nodes adjacents es completa primer, encara que no sigui el desitjat. A continuació, es busca el camí alternatiu a través del retrocés.

Dit d'una altra manera, l'algoritme tria la primera alternativa a cada node, després es retrocedeix amb una altra alternativa fins que hagi recorregut tots els camins des de la primera selecció. Això també planteja un problema en què la cerca pot deixar d’aturar-se a causa de bucles infinits (cicles) presents al gràfic.

1. L'antiga tècnica de cerca informada utilitza coneixements per trobar la solució. D'altra banda, aquesta última tècnica de cerca no informada no utilitza coneixements. En termes més senzills, no es proporciona informació addicional sobre la solució.
2. L’eficiència de la cerca informada és millor que la cerca sense informació.
3. La cerca sense informació consumeix més temps i cost, ja que no té idea sobre la solució en comparació amb la cerca informada.
4. La primera cerca en profunditat, la primera recerca d'amplada i la primera cerca de cost més baix són els algorismes que es troben dins de la categoria de cerca sense informació. En contraposició, la cerca informada cobreix els algoritmes com ara la recerca en primer lloc heurística, la primera cerca heurística d’amplada i la cerca A *.

Conclusió

La cerca informada proporciona la direcció de la solució, mentre que a la cerca sense informació, no es dóna cap suggeriment sobre la solució. Això fa que la cerca sense informació sigui més llarga quan s’implementa l’algorisme.