Please enable JavaScript.
Coggle requires JavaScript to display documents.
Búsqueda - Coggle Diagram
Búsqueda
-
-
CONCEPTOS ADICIONALES
Búsqueda Local:
No guarda los caminos, solo se preocupa por encontrar el mejor estado actual (ej. Escalada/Hill-climbing).
Heurística Consistente:
Una propiedad más fuerte que la admisibilidad que cumple con la desigualdad triangular; si h es consistente, f(n) nunca disminuye a lo largo de un camino.
-
ESTRATEGIAS DE BÚSQUEDA
-
INFORMADAS O HEURÍSTICA
Utilizan conocimiento específico del problema a través de una función heurística h(n), que estima el costo desde el nodo n hasta la meta
Búsqueda Primero el Mejor (PEM/Greedy):
Expande el nodo que parece estar más cerca de la meta (mínimo h(n))
. Es eficiente pero no es óptima.
A*:
Es la forma más común de búsqueda informada. Utiliza la función f(n)=g(n)+h(n), donde g(n) es el costo ya pagado y h(n) lo que falta estimadamente
. Es completa y óptima siempre que la heurística sea admisible (que nunca sobreestime el costo real).
Algoritmos Genéticos (Metaheurística):
Es una búsqueda local inspirada en la selección natural que evoluciona una población de soluciones mediante selección, cruce y mutación
. Se usa en problemas muy complejos (NP-duros) donde los métodos exactos tardarían demasiado