Informatica

Búsqueda
Busquen primeramente el reino de Dios y su
justicia porque el resto viene como ipegüe.
Jesucristo
1

Por qué buscar?
• Idea principal: La búsqueda permite explorar
alternativas
••
•
•

Antecedentes
Informada (heurística) vs. No informada (ciega)
Cualquier camino vs. El camino óptimo
Implementación y desempeño
2

Árboles y grafos
raíz
Árbol

A
B

Conector
Nodo(vértice)

C
Terminal
(hoja)

3

Árboles y grafos
raíz
Árbol

B es padre de C
C es hijo de B
A es ancestro de C
C es descendiente d A

A
B

Conector
Nodo
(vértice)

CTerminal
(hoja)

4

Árboles y grafos
raíz
Árbol

B es padre de C
C es hijo de B
A es ancestro de C
C es descendiente d A

A
B

Conector
Nodo
(vértice)

C
Terminal
(hoja)

Grafodirigido
(calles de una vía)
5

Árboles y grafos
raíz
Árbol

B es padre de C
C es hijo de B
A es ancestro de C
C es descendiente d A

A
B

Conector

C

Nodo
(vértice)

Grafodirigido
(calles de una vía)

Terminal
(hoja)
Grafo no
dirigido

6

Ejemplos de grafos
México
Tegucigalpa

Rutas de avión

Guatemala
Managua
San Salvador

7

Ejemplos de grafosMéxico
Tegucigalpa

Rutas de avión

Guatemala
Managua
San Salvador

Planeando
acciones
(grafo de
posibles
estados del
mundo)

Poner
C en A

A

B

C
A B

Poner C en A

C
PonerC en B

Poner
B en C

A

C
B

Poner
A en C

B
C
A
A
C
B
8

Paradigma para resolver problemas
•

¿Que son los estados(los aspectos relevantes del
problema)?
• Organizaciónde piezas ( un plan de montaje)
• Ubicación de camiones(plan de distribución de
paquetes)
• Ciudad(plan de un viaje)
• Conjunto de datos (ej. Para probar un teorema de
geometría)

9Paradigma para resolver problemas
•

¿Que son los estados(los aspectos relevantes del
problema)?
• Organización de piezas ( un plan de montaje)
• Ubicación de camiones(plan de distribución de...