Inteligencia Artificial
Clase # 5
Búsqueda Heurística
Dr. Wladimir Rodríguez
Postgrado de Computación
ULA
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-1
BUSQUEDA HEURISTICA O
INFORMADA
Usan algún método para controlar o guiar la búsqueda
¿Para que son utilizadas las heurísticas?
 Para ordenar la búsqueda (busqueda plausible) ver primero
los nodos mas prometedores
 Para controlar el ancho de la búsquedaprobar más en
profundidad que a lo ancho
Tipos de Heurística:
 Dirigidas por las metas conociendo que es lo que se quiere
alcanzar
 Dirigidas por el conocimiento usando conocimiento
especifico del dominio para reducir la búsqueda
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-2
BUSQUEDA EL MEJOR
PRIMERO
Selecciona de la lista de nodos para su expansión el
“mejor nodo”
Requiere de una función de evaluación f la cual
determinara numericamente que tan “bueno” es un nodo
dado. (asumir que valores mayores de f indican un mejor
nodo).
Garantia de encontrar una solución debido a que todos
los nodos sucesores de un nodo son agregados tal como
en la búsqueda a lo ancho. Sin embargo, no garantiza una
respuesta óptima a menos que la función de evaluación
sea escogida correctamente.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-3
ALGORITMO DEL MEJOR
PRIMERO
Poner nodo inicial en la lista.
Si nodo inicial es la meta, fin.
Si la lista está vacía, no hay solución.
De lo contrario: Seleccionar nodo de la
lista tal que f(nodo) sea máximo.
Si nodo seleccionado es la meta, fin.
De lo contrario: Expandir el nodo
seleccionado y agregar todos los
sucesores a la lista.
Repetir.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-4
BUSQUEDA EL MEJOR
PRIMERO
También conocida como búsqueda avara, cuando f(n)
es una función heurística h(n) usada para estimar el costo
para alcanzar la meta desde el nodo actual. Mientras que
f no es necesariamente dirigida a la meta, h si lo es.
Para el 8-puzzle, f(n) podría ser el número de piezas en
la posición correcta. A mayor número de piezas correctas
en algún estado, mejor será el nodo que representa ese
estado.
También podría ser la distancia “manhattan” para que
todas las piezas estén en la posición correcta.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-5
8-PUZZLE
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-6
BUSQUEDA EL MEJOR
PRIMERO
Mejoras:
 Computar f para cada sucesor en el momento de
la expansión, y almacenarlo con el nodo. Esto
significa que f es computada solamente una vez
por nodo.
 Ordenar la lista para agregar los sucesores en la
posición adecuada. Esto implica no tener que
seleccionar el mínimo cada vez.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-7
EJEMPLO
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-8
EJEMPLO
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-9
Búsqueda Avara
Es una búsqueda “mejor el primero” con
f(nodo)=h(nodo).
 Función heurística (h)
h(nodo)=coste estimado del camino más
corto desde un nodo hasta el objetivo.
 Todas las funciones heurísticas deben cumplir
al menos:
• h(n)>=0, para todo nodo n
• h(n)=0, si “n” es un nodo objetivo
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-10
Navegación del Robot
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-11
Navegación del Robot
f(N) = h(N), con h(N) = distancia Manhattan a la meta
8
7
7
6
5
4
5
4
3
3
2
6
7
6
8
7
Semestre A-2003
3
2
3
4
5
6
5
1
0
1
2
4
5
6
5
4
3
2
3
Dr. Wladimir Rodríguez - ULA
4
5
6
Inteligencia Artificial 4-12
Navegación del Robot
f(N) = h(N), con h(N) = distancia Manhattan a la meta
8
7
7
6
5
4
5
4
3
3
2
6
77
6
8
7
Semestre A-2003
3
2
3
4
5
6
5
1
00
1
2
4
¿Qué paso?
5
6
5
4
3
2
3
Dr. Wladimir Rodríguez - ULA
4
5
6
Inteligencia Artificial 4-13
Búsqueda más Informada
La meta no es minimizar la distancia desde
el último nodo en el camino hasta la meta,
lo que queremos es minimizar el largo
global del camino a la meta.
Dado g(N) como el costo del mejor camino
encontrado hasta el momento entre el nodo
inicial y N
 f(N) = g(N) + h(N)
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-14
Navegación del Robot
f(N) = g(N)+h(N), con h(N) = distancia Manhattan a la meta
8+3
8 7+4
7 6+3
6+5
6 5+6
5 4+7
4 3+8
3 2+9
2 3+10
3 4
7+2
7
6+1
6
5
5+6
5 4+7
4 3+8
3
3 2+9
2 1+10
1 0+11
0 1
5
2
4
7+0
7 6+1
6
5
8+1
8 7+2
7 6+3
6 5+4
5 4+5
4 3+6
3 2+7
2 3+8
3 4
Semestre A-2003
6
Dr. Wladimir Rodríguez - ULA
5
6
Inteligencia Artificial 4-15
BUSQUEDA EN ASCENSO DE
CIMA
 Seguir el camino que parece estar mejorando más
rápidamente.
 Continuar mientras que el camino siga mejorando.
 Necesita de una función local que indique que tan
bueno es el camino, conocida como función de
evaluación (similar al f en el mejor primero).
 Nunca retrocede.
 Rápido, pero no garantiza encontrar una solución.
 La solución encontrada no es necesariamente óptima.
 Funciona si el camino a la solución es monotónico.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-16
BUSQUEDA ASCENSO A LA
CIMA
Es similar a la búsqueda el primero mejor, pero los
nodos son agregados en forma diferente.
El Mejor Primero:
 Escoger para expandir el nodo con el valor de f mínimo.
Ascenso a la Cima:
 Escoger el nodo de la lista de sucesores del último nodo
expandido con el valor mínimo de f (una vez que se decide
expandir un nodo, solo considere sus sucesores y nunca trate
un camino alternativo).
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-17
BUSQUEDA ASCENSO A LA
CIMA
Problemas:
 puede parase en
mínimos locales.
 Planicies, no hay
mejoría local en f,
por lo que puede
andar sin rumbo.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-18
COMPARACION
AS C E N S O A LA
C IM A
E L M E JO R
P R IM E R O
C O S TO
U N IF O R M E
G aran tiza u n a
solu ción
No
S i (fin ito)
S i (fin ito)
S iem p re p ara
Si
Si
Si
O p tim o
No
D ep en d e d e f
Si
C u an d o falla
M ín im os locales
E ficien cia
++
+
+
R eq u erim ien tos
esp ecoales
F u n ción d e
evalu ación
F u n c ión d e
evalu ación
N ecesita con o cer el costo d el
arco
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-19
ENDURECIMIENTO SIMULADO
 Un método de descenso de gradiente como el ascenso
a la cima.
 Usa aleatoriedad para remover los problemas de
mínimos locales.
 Similar al proceso metalúrgico de endurecimiento.
 La temperatura es disminuida en el tiempo: a mayor T,
mayor la aleatoriedad de la selección del sucesor.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-20
BUSQUEDA A*
 Búsqueda óptima para solución
óptima
 Parecida a el mejor primero, con:
 f(n) = g(n) + h(n)
 donde:
 g(n) = costo mínimo del camino desde
el nodo inicial al nodo n.
 f(n) = costo mínimo estimado desde el
nodo n al nodo meta.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-21
BUSQUEDA A*
 f, g, h son aproximaciones a los verdaderos
valores de f*, g*, h*, respectivamente.
 Requiere conocer el costo de cada uno de los
movimentos, tal como en el costo uniforme,
para calcular g.
 Requiere de una función de evaluación
heurística para juzgar que tan díficil es llegar
desde el nodo actual al nodo final.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-22
Notas sobre g
g se calcula a partir del costo actual del camino
recorrido hasta ese momento.
g se conoce exactamente mediante la suma de
todos costo del camino desde el inicip hasta el
nodo actual (como en el costo uniforme)
Si el espacio de búsqueda es un árbol, g = g*,
debido a que solo hay un camino desde el nodo
inicial al nodo actual.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-23
Notas sobre g
 En general, el espacio de búsqueda será un
grafo. En este caso, g >= g*, esto es, g nunca
puede ser menor que el costo del camino
óptimo. Solo puede sobreestimar el costo.
 g puede ser = g* en un grafo si es escogida
apropiadamente.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-24
Notas sobre h
 h es una información heurística que representa una
aproximación a que tan díficil es llegar desde el nodo actual
hasta el nodo meta.
 Para que el algoritmo A* encuentre la solución de costo
mínimo:
 h(n) debe ser >= 0.
 h(n) debe ser <= h*(n), esto es, h nunca debe sobreestimar el
costo actual para alcanzar la meta desde el nodo actual.
Esto es conocido como la CONDICION DE AMSIBILIDAD.
(Si un algoritmo garantiza encontrar un camino solución de
costo mínimo (si existe), entonces el es ADMISIBLE.)
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-25
Más notas sobre h
Si h = h* (heurística perfecta), nunca se expandirán
nodos innecesarios.
Si h = 0, entonces A* se reduce al algoritmo de
búsqueda ciega de costo uniforme.
Meta: hacer h tan cercana como sea posible a h* sin
sobreestimar h.
 Si h* >= h1(n) > h2(n),
 h1 es más “informada” que h2.
La condición de admisibilidad podría ser relajada para
lograr mayor eficiencia, pero aunque se encontrará una
solución esta puede ser no óptima.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-26
EJEMPLO A*
Usar la menor distancia Euclidiana en línea
recta como heurística para h (admisible).
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-27
Neamt
Oradea
71
Zerind
87
75
Iasi
151
Arad
La ruta optima es (140+80+97+101) = 418 millas
140
92
Vaslui
118
Sibiu
Timisoara
99
Faragas
142
80
111
Lugoj
211
Rimnicu
70
Urziceni
97
146
75
101
Bucharest
138
Dobreta
120
Semestre A-2003
Hirsova
86
Pitesti
Mehadia
98
86
90
Craiova
Dr. Wladimir Rodríguez
Giurgui - ULA
Inteligencia ArtificialEforie
4-28
Distancia en Línea Recta a Bucharest
Ciudad
DLR
Ciudad
DLR
Arad
366
Mehadai
241
Bucharest
0
Neamt
234
Craiova
160
Oradea
380
Dobreta
242
Pitesti
98
Eforie
161
Rimnicu
193
Fagaras
178
Sibiu
253
Giurgiu
77
Timisoara
329
Hirsova
151
Urziceni
80
Iasi
226
Vaslui
199
Lugoj
244
Zerind
374
Se puede usar la distancia en línea recta como una heurística admisible ya que ella nunca
sobre estimará el costo hasta la meta. Debido a que no hay una distancia más corta entre
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-29
dos ciudades que la distancia en línea recta.
Zerind
Oradea
F= 75 + 374
F= 449
F= 291 + 380
F= 671
F= 0 + 366
Arad
F= 366
Fagaras
Sibiu
F= 239 + 178
F= 417
F= 140 + 253
F= 118 + 329
F= 447
F= 220 + 193
F= 413
Timisoara
Bucharest(2)
F= 393
F= 450 + 0
Rimnicu
F= 450
Bucharest
F= 418 + 0
Pitesti
Craiova
F= 418
F= 317 + 98
F= 415
F= 366 + 160
Semestre A-2003
F= 526
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-30
Mapa de Rumania mostrando los contornos a f = 380, f = 400 and f = 420, con
Arad como estado inicial. Nota: Nodos dentro de un contorno dado tienen costos
de f menor que el valor del contorno.
Zerind
Oradea
420
400
Arad
380
Sibiu
Timisoara
Fagaras
Rimnicu
Bucharest
Pitesti
Craiova
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-31
ALGORITMO A*
1) N lista de todos los nodos iniciales.
2) Si N esta vacío, no hay solución.
3) Selecione n en N tal que f(n) = g(n) + h(n)
es minimo.
4) Si n es un nodo meta, fin meta encontrada.
5) De lo contrario, remueva n de N, y agregue
todos los hijos de n a N y vaya al paso 3.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-32
A* con Profundidad Iterativa
Usar f(N) = g(N) + h(N) con una h
admisible y consistente
Cada iteración es búsqueda en profundidad
con un corte (cutoff) con el valor de f de los
nodos expandidos.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-33
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=4
6
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-34
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=4
4
6
Semestre A-2003
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-35
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=4
Semestre A-2003
4
5
6
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-36
8-Puzzle
5
f(N) = g(N) + h(N)
con h(N) = número de
fichas fuera de lugar
4
Cutoff=4
Semestre A-2003
4
5
6
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-37
8-Puzzle
6
5
4
5
6
6
f(N) = g(N) + h(N)
con h(N) = número de
fichas fuera de lugar
4
Cutoff=4
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-38
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=5
6
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-39
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=5
4
6
Semestre A-2003
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-40
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=5
Semestre A-2003
4
5
6
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-41
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=5
4
5
7
6
Semestre A-2003
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-42
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=5
5
4
5
7
6
Semestre A-2003
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-43
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=5
5
4
5
5
7
6
Semestre A-2003
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-44
8-Puzzle
f(N) = g(N) + h(N)
con h(N) = número de fichas fuera de lugar
4
Cutoff=5
5
4
5
5
7
6
Semestre A-2003
6
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-45
JUEGOS
Crear programas en el computador para jugar
Emular el razonamiento humano en el computador
Construir sistemas que sean capaces de tomar
decisiones en un entorno adverso
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-46
JUEGOS: Características y Ejemplos
Características de los juegos que vamos a estudiar:
 Juegos bipersonales.
 Los jugadores mueven alternativamente.
 La ventaja para un jugador es desventaja para el otro.
 Los jugadores poseen toda la información sobre el estado del
juego.
 Hay un número finito de estados y decisiones
 No interviene el azar (dados, cartas).
Ejemplos de juegos validos:
 Ajedrez, damas, go, otelo, 3 en raya, nim, …
Ejemplos de juegos que no son validos
 Backgammon, poker, bridge.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-47
EJEMPLO DE JUEGO: NIM
Situación inicial:
Una pila con N
fichas.
Jugadas: Coger 1, 2
ó 3 fichas de la pila.
Objetivo: Obligar al
adversario a coger la
última ficha.
Desarrollo completo
del juego con 4
piezas:
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-48
Estrategia ganadora: NIM
Estrategia ganadora:
El movimiento que,
haga lo que haga el
adversario, nos
lleve a una situación
ganadora o a la que
nos favorezca más.
Estrategia ganadora
en el NIM
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-49
Desarrollo Incompleto
Función de
evaluación estática
 Límites inferior y
superior
Valores
programados,
máximo y mínimo.
Desarrollo del NIM
con valores
programados.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-50
Ejemplo de poda alfa-beta: NIM 4
Principio alfa-beta: si se tiene una buena
(mala) idea, no perder tiempo en averiguar
lo buena (mala) que es.
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-51
Ejemplo de poda alfa-beta: NIM 7
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-52
Complejidad de minimax y alfa-beta
Complejidad:
 R : factor de ramificación.
 P : profundidad de la búsqueda.
 Complejidad en tiempo de minimax: O(rp).
 Complejidad en tiempo de minimax con poda alfabeta, en el mejor caso: O(rp/2).
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-53
Complejidad de minimax y alfa-beta
 Aplicación al ajedrez
 Factor de ramificación : 35
 Número de movimientos en una partida media: 50
 Numero de nodos analizados por minimax: 35100 ≈
10154
 Numero de nodos analizados por minimax con
poda alfa-beta : 3550 ≈ 1077
 Número de posiciones legales: 1040
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-54
Complejidad en el NIM
Estados evaluados:
 Empezando la máquina,
 Con profundidad 20 y
 Eligiendo el humano siempre 1.
Minimax
Minimax-a-b
8
12
16
192
16
2223
67
25472 291551
294
1023
Tiempo y espacio para orden 16
tiempo
Minimax
14.55 sec.
Minimax-a-b
0.23 sec
Semestre A-2003
20
espacio
3245720 bytes
69812 bytes
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-55
3 en raya: Evaluación
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-56
Ejemplo Alpha-Beta
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-57
Ejemplo Alpha-Beta
0
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-58
Ejemplo Alpha-Beta
0
0
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-59
Ejemplo Alpha-Beta
0
0
-3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-60
Ejemplo Alpha-Beta
0
0
-3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-61
Ejemplo Alpha-Beta
0
0
0
-3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-62
Ejemplo Alpha-Beta
0
0
0
-3
3
3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-63
Ejemplo Alpha-Beta
0
0
0
-3
3
3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-64
Ejemplo Alpha-Beta
0
0
0
0
0
-3
3
3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-65
Ejemplo Alpha-Beta
0
0
0
0
0
-3
3
3
5
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-66
Ejemplo Alpha-Beta
0
0
0
0
0
-3
3
3
2
2
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-67
Ejemplo Alpha-Beta
0
0
0
0
0
-3
3
3
2
2
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-68
Ejemplo Alpha-Beta
0
0
0
0
0
-3
2
2
3
3
2
2
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-69
Ejemplo Alpha-Beta
0
0
0
0
0
-3
2
2
3
3
2
2
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-70
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
3
3
2
2
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-71
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
3
3
2
2
5
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-72
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
3
3
2
2
1
1
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-73
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
3
3
2
2
1
1
-3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-74
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
3
3
2
2
1
1
-3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-75
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
1
3
3
1
2
2
1
1
-3
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-76
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
1
3
3
1
2
2
1
1
-3
-5
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-77
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
1
3
3
1
2
2
1
1
-3
-5
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-78
Ejemplo Alpha-Beta
0
0
0
0
0
0
-3
2
2
1
3
3
1
2
2
1
-5
1
-5
-3
-5
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-79
Ejemplo Alpha-Beta
1
0
0
0
0
0
-3
2
2
1
3
3
1
2
2
1
-5
1
-5
-3
-5
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-80
Ejemplo Alpha-Beta
1
0
1
0
0
0
0
-3
2
2
1
3
3
1
2
2
1
-5
1
-5
-3
-5
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-81
Ejemplo Alpha-Beta
1
0
1
0
0
0
0
-3
2
2
2
1
3
3
1
2
2
1
-5
2
1
-5
2
-3
-5
2
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-82
Ejemplo Alpha-Beta
1
0
1
0
0
0
0
-3
2
2
2
1
3
3
1
2
2
1
-5
2
1
-5
2
-3
-5
2
0 5 -3 3 3 -3 0 Dr.
2 Wladimir
-2 3 5 2
5 -5 0 - ULA
1 5 1 -3 0 Inteligencia
-5 5 -3 3 Artificial
2
Semestre A-2003
Rodríguez
4-83
¿Qué ganamos?
1
Tamaño del árbol = O(bh)
0
• En el peor de los casos todos
los nodos deben ser examinados
0
2
• En el mejor de los casos, solo
O(bh/2) nodos deben
0 ser 2
examinados
0
0
-3
3
3
1
1
1
2
2
2
1
-5
2
1
-5
2
-3
-5
2
0 5 -3 3 3 -3 0 2 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2
Semestre A-2003
Dr. Wladimir Rodríguez - ULA
Inteligencia Artificial 4-84
Descargar

0 - Ceidis