Hoja3-solucion - Ejercicios resueltos PDF

Preview

Summary

Ejercicios resueltos...

Description

Universidad Rey Juan Carlos

Curso 2017–2018 Hoja de Problemas Tema 3 - Soluci´ on B´ usqueda Heur´ıstica

1. Contesta a las siguientes preguntas: (a) ¿Cu´al es el objetivo de una funci´on heur´ıstica aplicada a la b´ usqueda en el espacio de estados? Soluci´ on: Estimar la adecuaci´on de un nodo para ser expandido. (b) ¿Cu´al es la definici´on de heur´ıstica consistente? Soluci´ on: Una heur´ıstica es consistente si para todo nodo ni y todo sucesor nj de ni se cumple que h∗ (ni ) − h∗ (nj ) ≤ c(ni , nj ) o sea, si h∗ subestima el coste de todos los operadores. (c) ¿Cu´al es la definici´on de heur´ıstica optimista? Soluci´ on: Una heur´ıstica es optimista si h∗ (n) ≤ h(n) donde h(n) mide el coste real desde el nodo n hasta el nodo meta m´as cercano. (d) ¿Una funci´on heur´ıstica consistente es tambi´en optimista? Soluci´ on: Si. Una heur´ıstica consistente subestima el coste de todos los operadores, por lo tanto, tambi´en subestima el coste total hacia la meta. (e) ¿Qu´e condiciones garantizan que el algoritmo A∗ sea o´ptimo? Soluci´ on: El algoritmo A∗ es o´ptimo si la funci´on heur´ıstica h∗ es optimista. 2. Dado el siguiente problema de b´usqueda: Por un gen´erico nodo (u, v), ¿cu´ales de las siguientes funciones heur´ısticas son optimistas?

P´agina 1 de 9

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

Figura 1: Red 2D regular e infinita, Estado inicial (0, 0), Estado final: (x, y) x, y ∈ Z , Movimiento entre estados directamente conectados a coste 1 Soluci´ on: (a) h∗ ((u, v)) = |u − x| + |v − y| h∗ ((u, v)) = |u − x| + |v − y| ≤ h((u, v)) = |u − x| + |v − y| (b) h∗ ((u, v)) = |u − x| ∗ |v − y | (x, y) = (1, 1) h∗ ((4, 4)) = |4 − 1| ∗ |4 − 1| = 9 ≥ h((4, 4)) = |4 − 1| + |4 − 1| = 6 (c) h∗ ((u, v)) = 2 ∗ min(|u − x|, |v − y |) supongamos que |u − x| ≤ |v − y |, entonces h∗ ((u, v)) = 2 ∗ min(|u − x|, |v − y|) = 2 ∗ |u − x| 2 ∗ |u − x| ≤ |u − x| + |v − y| ⇒ |u − x| ≤ |v − y| que concuerda con nuestra suposici´on inicial. (d) h∗ ((u, v)) = |u| + |x| + |v| + |y| (x, y) = (−1, −1) h∗ ((−2, −2)) = |−2|+ |−1|+ |−2|+ |− 1| = 6 ≥ h((−2, −2)) = |−2+1|+ |−2+1| = 2 (e) h∗ ((u, v)) =

q

(|u − x|2 + |v − y|2 )

q

h∗ ((u, v)) = (|u − x|2 + |v − y|2 ) ≤ h((u, v)) = |u − x| + |v − y| ⇒ |u − x|2 + |v − y |2 ≤ (|u − x| + |v − y |)2 = |u − x|2 + |v − y |2 + 2 ∗ |u − x| ∗ |v − y |

P´agina 2 de 9

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

3. El grafo que se muestra a continuaci´on representa un esquema de un mapa de carreteras. Los nodos est´an etiquetados con el nombre de ciudades, y los arcos con la distancia por carretera entre dichas ciudades. Inicialmente nuestro agente se encuentra en la ciudad D, y procura trasladarse por carretera a la ciudad B por el camino m´as corto. Con tal fin, puede hacer uso de su conocimiento de la regi´on, y en particular de la distancia a´erea entre ciudades. La funci´on h∗ que se muestra al lado indica la distancia a´erea entre cualquier ciudad y la ciudad de destino B .

Suponga que el programa de agente se basa en el algoritmo A∗ para resolver este problema.

P´agina 3 de 9

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

(a) Desarrolle el a´rbol de b´ usqueda que genera el algoritmo A∗ , asumiendo que se filtran ciclos simples (p.e.: D − M − D). Indique el orden en el que se expanden los nodos, as´ı como el valor de g, h∗ , y f ∗ de cada nodo del a´rbol de b´usqueda. Soluci´ on:

(b) Muestre tambi´en el estado de la lista abierta en cada paso del algoritmo. Soluci´ on: 1. 2. 3. 4. 5. 6.

(D/242) (C/280), (M/,316) (G/312), (M/316), (P/356), (R/459) (M/316), (P/356), (B/395), (R/459) (P/356), (L/389), (B/395), (R/459) (B/359), (L/389), (B/395), (R/459), (R/548)

N´otese que el algoritmo A∗ no para despu´es del paso 3, cuando el nodo meta B se a˜ nade al a´rbol de b´ usqueda (o, lo que es lo mismo, el nodo B entra en la lista abierta). Eso es as´ı porque hay nodos hoja en el a´rbol de b´usqueda con un valor f ∗ menor que el del nodo meta (por eso el nodo meta no es el primero de la lista abierta). Efectivamente, en los pasos sucesivos del algoritmo se encuentra un camino de menor coste (a trav´es de P ) al nodo meta B .

P´agina 4 de 9

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

4. El grafo que se muestra en la figura describe un problema de b´ usqueda. Suponga que A es el estado inicial y que F y E son estados meta. Los arcos est´an etiquetados con el coste real de los operadores (hasta all´ı, el problema coincide con el de la transparencia 12 del Tema 3)

(a) Asigne los valores de la funci´on heur´ıstica h∗ , de modo que resulte ser optimista y no consistente Soluci´ on: La siguiente funci´ on heur´ıstica ser´ıa optimista h∗ A 8 B 6 C 6 D 1 E 0 F 0 como se comprueba f´acilmente: h∗ (A) = 8 =< h(A) = 10

(1)

h∗ (B) = 6 =< h(B) = 7

(2)

∗

h (C ) = 6 =< h(C ) = 7

(3)

h∗ (D) = 1 =< h(D) = 3

(4)

∗

(5)

∗

(6)

h (E ) = 0 =< h(E ) = 0 h (F ) = 0 =< h(F ) = 0

Sin embargo, no es consistente, porque no subestima el coste real del operador que lleva del estado C al estado D: h∗ (C) − h∗ (D) = 6 − 1 = 5 > c(C, D) = 4

P´agina 5 de 9

(7)

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

(b) Desarrolle el a´rbol de b´ usqueda que genera el algoritmo A∗ . ¿Es el algoritmo A∗ o´ptimo en este caso? Soluci´ on:

Como se ilustra en el ejemplo, el algoritmo A∗ es o´ptimo, ya que la funci´on heur´ıstica h∗ es optim´ısta. 5. Considere el problema de los bloques cuyo estado inicial y estado meta se muestran en la siguiente figura:

Desarrolle el a´rbol de b´ usqueda que expande el algoritmo A∗ , utilizando la siguiente heur´ıstica: h∗ (n) = n´ umero de bloques descolocados Con tal fin, considere que un bloque est´a descolocado si por debajo no tiene el elemento correcto (bien el bloque deseado o bien la mesa). Filtre los ciclos simples, indique el orden de expansi´on de los estados y muestre en cada paso los valores de f ∗ , g y h∗ . Suponga que el coste de cada operador es 1.

P´agina 6 de 9

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

Soluci´ on:

N´otese que una soluci´on en la que no se hubiera expandido el nodo del paso 4 ser´ıa igualmente correcta ya que, si varios nodos hoja tienen el mismo valor de f ∗ (en este caso f ∗ = 4), el algoritmo A∗ elige uno de entre estos nodos de forma aleatoria para expandirlo. 6. Las recientes lluvias han provocado da˜ nos en la infraestructura de un municipio que deben ser reparados con urgencia. Concretamente, hay N obras por realizar y se ha pedido presupuesto a M empresas constructoras para cada una de las obras. El coste de encargar cada obra a cada empresa viene dado por una tabla como la siguiente, donde Ci,j indica el coste de encargar a la empresa Ei la obra Oj

EmpresaE1 EmpresaE2 ... EmpresaEM

Obra O1 C1,1 C2,1

Obra O2 C1,2 C2,2

CM,1

CM,2

...

Obra ON C1,N C2,N CM ,N

El Ayuntamiento ha decidido asignar una sola obra por empresa. El problema consiste en decidir qu´e obra se asignar´a a cada empresa, de modo que se minimice el coste total. Los t´ecnicos deciden utilizar el algoritmo A∗ para resolver el problema. P´agina 7 de 9

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

(a) Defina una representaci´ on “eficiente” del problema, especificando el conjunto de posibles estados, estado inicial, estados finales, as´ı como operador(es) y su coste. Soluci´ on: Se puede utilizar una lista de empresas para representar un estado en el espacio de b´ usqueda: la primera empresa de la lista es adjudicataria de la obra O1 , la segunda de la obra O2 , etc. Por ejemplo, la lista [E3 , E1 ] representa un estado en el que la obra O1 est´a adjudicada a la empresa E3 , la obra O2 a la empresa E1 , y las obras O3 hasta ON est´an todav´ıa sin adjudicar. Estado inicial: [] Estados meta: cualquier lista de longitud N que no contenga elementos (empresas) repetidos Operador: a˜ nadir un elemento (una empresa nueva) al vector, i.e. adjudicar la siguiente obra a una empresa nueva Coste de un operador: el coste de dicha adjudicaci´on (b) Defina una “buena” funci´on heur´ıstica h∗ optimista para el problema general. ¿Es su funci´on h∗ tambi´en consistente? Soluci´ on: Para un estado s, la funci´on heur´ıstica h∗ devuelve la suma de los costes m´ınimos de todas las obras no asignadas, considerando para ello u ´nicamente las empresas sin adjudicaci´on en s. Formalmente, si consideramos ob(s) el conjunto de obras asignadas en s, y emp(s) el conjunto de empresas adjudicatarias en s: h∗ (s) =

X

minEi ∈emp(s) {Ci,j } /

(8)

Oj ∈ob(s) /

Para cada obra no adjudicada en s, el coste real de su adjudicaci´on siempre es mayor o igual que el coste m´ınimo contabilizado por h∗ . Se sigue que h∗ subestima el coste real de cada operador por lo que es consistente, en consecuencia, tambi´en optimista. (c) Considere el siguiente caso particular (los costes se expresan en millones de Euros)

EmpresaE1 EmpresaE2 EmpresaE3 EmpresaE4

Obra O1 2 5 6 10

Obra O2 3 5 5 8

Obra O3 2 4 4 6

Obra O4 4 5 3 6

Desarrolle el a´rbol de b´ usqueda que genera el algoritmo A∗ (puede suponer el “mejor caso”). Indique el orden en el que se expanden los nodos, los valores de g, h∗ y f ∗ para cada nodo del a´rbol de b´ usqueda, y la evoluci´on de la lista abierta. P´agina 8 de 9

Hoja de Problemas Tema 3 - Soluci´ on

B´ usqueda Heur´ıstica

Soluci´ on:

1 [] 3

f * = 0+10 = 10

2 [E1] f * = 2+12 = 14

[E1,E3]

= 13

[E1,E4]

f * = 7+9 = 16

[E2,E3]

f * = 10+7 = 17

4 [E1,E2]

f * = 11+6 = 17

[E2,E4]

f * = 10+6 = 16

f * = 13+5 = 18

5 [E2,E1]

f * = 7+7 = 14

[E1,E2,E3]

6 [E2] f * = 5+8

7

f * = 13+3 = 16

[E2,E1,E3] f * = 12+6 = 18

[E4] f * = 10+8

= 15

= 18

[E3,E1]

[E3,E4]

f * = 9+9 = 18

f * = 14+6 = 20

[E3,E2]

f * = 8+7 = 15

[E1,E2,E4]

[E3] f * = 6+9

f * = 11+6 = 17

[E2,E1,E4] f * = 14+3 = 17

8 [E1,E2,E4,E3] f * = 16+0 = 16

Lista abierta: 1. 2. 3. 4. 5. 6. 7.

8.

([],10) ([E2],13) ([E1],14) ([E3,15]) ([E4,18]) ([E1],14) ([E2,E1],15) ([E3,15]) ([E2,E3],16) ([E2,E4],18) ([E4,18]) ([E1,E2],14) ([E2,E1],15) ([E3,15]) ([E1,E3],16) ([E2,E3],16) ([E1,E4],17) ([E2,E4],18) ([E4,18]) ([E2,E1],15) ([E3,15]) ([E1,E2,E4],16) ([E1,E3],16) ([E2,E3],16) ([E1,E2,E3],17) ([E1,E4],17) ([E2,E4],18) ([E4,18]) ([E3,15]) ([E1,E2,E4],16) ([E1,E3],16) ([E2,E3],16) ([E2,E1,E4],17) ([E1,E2,E3],17) ([E1,E4],17) ([E2,E1,E3],18) ([E2,E4],18) ([E4,18]) ([E1,E2,E4],16) ([E1,E3],16) ([E2,E3],16) ([E3,E2],17) ([E2,E1,E4],17) ([E1,E2,E3],17) ([E1,E4],17) ([E3,E1],18) ([E2,E1,E3],18) ([E2,E4],18) ([E4,18]) ([E3,E4],20) ([E1,E2,E4,E3],16) ([E1,E3],16) ([E2,E3],16) ([E3,E2],17) ([E2,E1,E4],17) ([E1,E2,E3],17) ([E1,E4],17) ([E3,E1],18) ([E2,E1,E3],18) ([E2,E4],18) ([E4,18]) ([E3,E4],20) ´ exito

P´agina 9 de 9...