Problema IA
Problema IA
Problema IA
ligncia Artificial
CURS 2014/2015 2Q
Col.lecci de Problemes
ndice general
2. Cerca Heurstica
3. Cerca Local
15
4. Jocs
31
5. Satisfacci de restriccions
41
51
59
73
127
NDICE GENERAL
En lelaboraci de la col.lecci de problemes dIA han participat els professors:
Ma Teresa Abad Soriano
Javier Bjar Alonso
Nria Castell Ario
Juan Manuel Gimeno Illa
Miquel Snchez i Marr
Jordi Turmo Borrs
Javier Vzquez Salceda
Responsable de la publicaci: Javier Bjar (bejar@cs.upc.edu)
Creative Commons,
559 Nathan Abbott Way, Stanford,
California 94305,
USA.
En cada esquina tenemos un caballo de ajedrez, dos caballos negros y dos blancos. Deseamos intercambiar los caballos negros con los blancos.
a) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades
ha de cumplir. Estima el tamao del espacio de estados.
b) Define las caractersticas de los operadores para realizar la bsqueda (condiciones de aplicabilidad
y funcin de transformacin), evala cual sera el factor de ramificacin (aproximadamente).
c) Importa el camino o slo el estado final?la solucin ha de ser ptima?
2. Dispones de dos jarras de agua, una de 4 litros y otra de 3 litros. Tiene un grifo que te permite llenar
totalmente las jarras de agua, necesitas obtener exactamente 2 litros en la jarra de cuatro litros
a) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades
ha de cumplir. Estima el tamao del espacio de estados.
b) Define las caractersticas de los operadores para realizar la bsqueda (condiciones de aplicabilidad
y funcin de transformacin), evala cual sera el factor de ramificacin (aproximadamente).
c) Importa el camino o slo el estado final?la solucin ha de ser ptima?
3. Si recuerdas el procedimiento de validacin por resolucin en lgica de enunciados, puedes validar
cualquier razonamiento a partir de la transformacin de sus premisas y la negacin de la conclusin a
forma normal conjuntiva. El algoritmo mas sencillo (pero no muy eficiente) de validar un razonamiento
es aplicar la regla de la resolucin (desempolva tus apuntes de ILO) sistemticamente entre las clusulas
hasta conseguir derivar una contradiccin.
a) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades
ha de cumplir. Estima el tamao del espacio de estados.
b) Define las caractersticas de los operadores para realizar la bsqueda (condiciones de aplicabilidad
y funcin de transformacin), evala cual sera el factor de ramificacin (aproximadamente).
c) Importa el camino o slo el estado final?la solucin ha de ser ptima?
d) Piensa en el mecanismo de resolucin lineal y vuelve a responder a los apartados a y b
4. Si piensas en el juego del tetris, este consiste en cubrir la mxima rea de un rectngulo de NxM sin
dejar huecos (o dejando los mnimos posibles) utilizando un conjunto ordenado de piezas con todas
las posibles formas construibles utilizando cuatro cuadrados (siete piezas distintas)
a) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades
ha de cumplir. Estima el tamao del espacio de estados.
b) Define las caractersticas de los operadores para realizar la bsqueda (condiciones de aplicabilidad
y funcin de transformacin), evala cual sera el factor de ramificacin (aproximadamente).
c) Importa el camino o slo el estado final?la solucin ha de ser ptima?
1
3
quieres que haya mas de k cursos de un nivel cada da Generaliza el problema suponiendo que tienes
g grupos de cada curso y a aulas y no quieres que haya dos cursos iguales a la misma hora Supn que
tienes que hacer tu horario cuatrimestral y dispones de m asignaturas, cada una de ellas con n grupos
y quieres elegir un subconjunto k de ellas (k<m) sin que se solapen sus horarios
a) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades
ha de cumplir, estima el tamao del espacio de estados. Piensa que puede haber diferentes formas
de plantear el problema.
b) Define las caractersticas de los operadores para realizar la bsqueda (condiciones de aplicabilidad
y funcin de transformacin), evala cual sera el factor de ramificacin (aproximadamente).
9. El problema del club de golf. Tenemos un club de golf con 32 jugadores, todos ellos juegan una vez a
la semana en grupos de 4 personas. Queremos obtener los emparejamientos para el mayor numero de
semanas de manera que un jugador no este en el mismo grupo que otro jugador mas de una vez.
a) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades
ha de cumplir, estima el tamao del espacio de estados. Piensa que puede haber diferentes formas
de plantear el problema.
b) Define las caractersticas de los operadores para realizar la bsqueda (condiciones de aplicabilidad
y funcin de transformacin), evala cual sera el factor de ramificacin (aproximadamente).
2. Cerca Heurstica
1. El problema del coloreado de grafos consiste en etiquetar con un color cada vrtice del grafo, de forma
que no haya dos vrtices adyacentes con el mismo color. Este problema se puede resolver por medio
de bsqueda.
a) Describe los pasos que seguira un algoritmo A* para encontrar una solucin al coloreado del
siguiente grafo:
v1
{A,V}
{A,R}
v2
v4
v3
{V,R,A}
{V}
en donde los vrtices son V1, V2, V3 y V4 y los colores posibles para cada vrtice se indican entre
llaves (A:azul, R:rojo, V:verde). El estado inicial tiene todos los vrtices sin color asignado. Un
estado S es sucesor de otro S si S contiene la asignacin de colores de S ms la asignacin de un
color al vrtice ms pequeo sin colorear de S (es decir, los vrtices se instancian en el orden V1
V4). La funcin heurstica es:
h(s) = nmero de vrtices sin color en s + 2 nmero de vrtices adyacentes con el mismo color
en s
b) Es admisible la funcin heurstica? Razona la respuesta.
c) Sugiere otro algoritmo que solucione este problema de forma ms eficiente que A*
2. Dado el siguiente grafo, donde cada arco indica su coste, y la tabla que indica la estimacin del coste
h hasta la solucin, indica cual sera el rbol de bsqueda que se obtendra mediante el algoritmo de
A e IDA para encontrar el camino entre el nodo A y el nodo H. Haz la generacin de los nodos
siguiendo el orden alfabtico e indica claramente las reexpansiones de los nodos y los cambios de coste
que aparezcan. Es la funcin heurstica admisible?
B
1
E
2
2
1
1
2
Nodo
h(nodo)
D
1
A
4
G
3
B
4
C
3
D
3
E
2
F
3
G
2
H
0
3. Aplicar lalgoritme A* per a trobar un cam soluci del graf descrit a la taula:
5
a
b
c
d
e
c
4
10
12
h
3
4
12
0
4
on els nodes de les files sn els nodes-pares i els nodes de les columnes els nodes-fills. El node a s linicial
i el final s d. Cada casella de la taula indica el cost de larc que uneix els dos nodes corresponents.
La darrera columna indica el valor de la funci heurstica (h).
a) Mostrar larbre de cerca generat per lalgoritme, indicant lordre dexpansi dels nodes, reopertures de nodes tancats, etc. Quin s el cam trobat? Quin s el seu cost? s lptim?
b) Es verifiquen les condicions dadmissibilitat? Justifiqueu la resposta.
c) Fer el mateix amb lalgoritme IDA*.
4. Disponemos de un casillero con cuatro monedas colocadas de la siguiente forma:
A
El anverso de la moneda est representado por A y el reverso por R. Son posibles los siguientes
movimientos:
Desplazamiento (coste=1): Una moneda puede ser desplazada a la casilla contigua si sta se
encuentra vaca.
Giro (coste=1): Cualquier moneda puede ser girada sin ninguna condicin adicional. Slo una
cada vez.
Salto (coste=2): Una moneda puede saltar sobre su vecina si a continuacin hay una casilla
vaca, es decir, slo es posible saltar por encima de una moneda. Cuando una moneda salta, cae
realizando un giro. Un ejemplo de salto (coste=2) es pasar del estado AR_RA al estado ARRR_
Deseamos obtener la situacin final siguiente:
R
El anverso de la moneda est representado por A y el reverso por R. Se considera un movimiento (de
coste 1) el dar la vuelta a dos monedas contiguas.
Deseamos obtener la situacin final siguiente:
7
R
1er paso
A
H1
H1
H1
B
H2
H2
C
H3
H3
H2
2o paso
A
H2
H2
H2
B
H1
H1
C
H3
H1
3
1
1
1
J
1
M
1
1
2
N
3
2
2
H
Nodo
h(nodo)
A
6
B
5
C
6
D
6
E
3
F
5
G
5
H
4
I
8
O
J
3
K
2
L
1
M
5
N
1
O
0
8. Dado el siguiente grafo, donde cada arco indica su coste, y la tabla que indica la estimacin del coste
h hasta la solucin, indica cual sera el rbol de bsqueda que se obtendra mediante el algoritmo de
A e IDA para encontrar el camino entre el nodo A y el nodo H. Haz la generacin de los nodos
siguiendo el orden alfabtico e indica claramente las reexpansiones de los nodos y los cambios de coste
que aparezcan. Es la funcin heurstica admisible?
1
B
2
1
1
A
6
B
4
1
3
C
Nodo
h(nodo)
E
2
1
4
C
3
D
3
E
2
F
3
H
G
2
H
0
9. Deseamos hallar la ruta que ha de seguir un robot para recoger un conjunto de objetos en un orden
especfico en una habitacin. La situacin es la que se presenta en la figura. El robot slo se puede
desplazar en vertical y en horizontal. En cada movimiento slo se desplaza una casilla. Cada vez que
el robot llega a la casilla donde hay un objeto lo recoge y lo lleva consigo.
N
R
O O1
O3 E
O2
S
9
a) Utiliza el algoritmo del A* para hallar el camino que permite al robot recoger los 3 objetos en
orden usando la funcin heurstica:
h1 (n) =
drj
Donde drj es la distancia en movimientos del robot al objeto j. Considera que, cuando el robot
recoge un objeto, su distancia pasa a ser 0 y que el objeto se mueve con el robot una vez recogido.
Para hacer la expansin de los nodos utiliza el orden N-S-E-O tal como se indica en la figura.
Indica el orden de expansin de los nodos. El camino encontrado es ptimo?
b) Supn que el heurstico es:
h2 (n) = dr1 + d12 + d23
Donde dr1 es la distancia en movimientos del robot al objeto O1, d12 es la distancia en pasos
del objeto O1 al objeto O2 y d23 es la distancia del objeto O2 al objeto O3. Utiliza de nuevo el
algoritmo del A* para hallar la solucin. Para hacer la expansin de los nodos utiliza el orden
N-S-E-O tal como se indica en la figura. Indica el orden de expansin de los nodos. El camino
encontrado es ptimo?
c) Los heursticos usados son admisibles? Podemos afirmar que uno es ms informado que el otro?
Razona las respuestas.
d) Haz de nuevo la bsqueda utilizando el algoritmo del IDA* y el heurstico h1 . Indica el orden de
expansin de los nodos. El camino encontrado es ptimo?
10. Dado el siguiente grafo, donde cada arco indica su coste, y la tabla que indica la estimacin del coste
h hasta la solucin, indica cual sera el rbol de bsqueda que se obtendra mediante el algoritmo de
A e IDA para encontrar el camino entre el nodo A y el nodo H. Haz la generacin de los nodos
siguiendo el orden alfabtico e indica claramente las reexpansiones de los nodos y los cambios de coste
que aparezcan. Es la funcin heurstica admisible?
B
1
1
2
D
1
A
4
B
4
H
2
G
4
Nodo
h(nodo)
C
3
D
3
E
2
F
3
G
2
H
0
10
y disponemos de una nica regla, dos fichas se pueden intercambiar si estn adyacentes, considerando
que los dos extremos son adyacentes (es un tablero circular).
El objetivo es obtener la siguiente configuracin:
B
11
b) Resuelve el mismo problema aplicando el algoritmo del IDA*. Indica el orden expansin de los
nodos y la gestin de duplicados, si procede.
c) Es admisible el heurstico? Por qu?
14. Dado el siguiente grafo donde cada arco indica su coste y la tabla que indica la estimacin del coste
h hasta la solucin, indica cual sera el rbol de bsqueda que se obtendra mediante el algoritmo de
A e IDA para encontrar el camino entre el nodo A y el nodo G. Haz la generacin de los nodos
siguiendo el orden alfabtico e indica claramente las reexpansiones de los nodos y los cambios de coste
que aparezcan. Es la funcin heurstica admisible?
Nodo
h(nodo)
A
3
B
4
C
3
D
4
E
3
F
3
G
0
donde hay dos piezas negras (N), dos blancas (B) y una posicin vaca, y teniendo en cuenta las
siguientes reglas:
(i) Una pieza puede moverse a la posicin adyacente vaca con coste 1.
(ii) Una pieza puede saltar per encima de otra (slo una) para colocarse en la posicin vaca con coste
1. Si la pieza que salta es de distinto color que la saltada, esta ltima cambia de color.
Queremos conseguir que todas las piezas del tablero sean negras. La posicin final de la casilla vaca
es indiferente.
a) Muestra el rbol de bsqueda generado por el algoritmo A* indicando el orden de expansin de
los nodos, el tratamiento de los duplicados, la solucin encontrada y el coste de la misma. Utiliza
como heurstico: h(n) = nmero de piezas blancas
b) Justifica la admisibilidad o no del heurstico utilizado.
c) Considera ahora el siguiente heurstico: h2 (n) = nmero de piezas blancas - c donde c vale 1 si
el espacio es adyacente a una pieza blanca y vale 0 en caso contrario. Justifica su admisibilidad
o no.
d) Razona si h2 (n) es ms informado que h(n).
16. Dado el siguiente grafo donde cada arco indica su coste y la tabla que indica la estimacin del coste
h hasta la solucin, indica cual sera el rbol de bsqueda que se obtendra mediante el algoritmo de
A e IDA para encontrar el camino entre el nodo A y el nodo O. Haz la generacin de los nodos
siguiendo el orden alfabtico e indica claramente las reexpansiones de los nodos y los cambios de coste
que aparezcan. Es la funcin heurstica admisible?
12
1
E
4
1
C
Nodo
h(nodo)
A
6
C
6
E
3
F
5
G
5
I
8
J
3
K
2
L
1
O
1
H
4
D
6
F
B
5
N
M
5
N
1
O
0
17. Dado el siguiente grafo, donde cada arco indica su coste, y la tabla que indica la estimacin del coste
h hasta la solucin, indica cual sera el rbol de bsqueda que se obtendra mediante el algoritmo de
A e IDA para encontrar el camino entre el nodo A y el nodo H. Haz la generacin de los nodos
siguiendo el orden alfabtico e indica claramente las reexpansiones de los nodos y los cambios de coste
que aparezcan. Es la funcin heurstica admisible?
2
B
1
Nodo
h(nodo)
G
1
A
6
C
B
4
H
1
E
1
C
4
D
4
E
4
F
3
G
3
H
0
18. Dado el rbol de bsqueda que aparece en la figura indica cual sera el recorrido que hara el algoritmo
A* e IDA* la funcin heurstica es admisible?
En el rbol la funcin heurstica esta descompuesta en la g y la h. Cuando en un nodo aparecen dos
valores el orden corresponde a la rama por la que se ha llegado al nodo.
A
0+6
1+5
2+5
3+4
3+5|2+5
5+3|4+3
6+2
2+6
3+5|2+5
3+5
3+4
4+4
3+4
5+2
5+2
6+0
1+5
13
19. Dado el rbol de bsqueda que aparece en la figura indica cual sera el recorrido que hara el algoritmo
A* e IDA* la funcin heurstica es admisible?
En el rbol la funcin heurstica esta descompuesta en la g y la h. Cuando en un nodo aparecen dos
valores el orden corresponde a la rama por la que se ha llegado al nodo.
A
0+6
1+5
2+4
3+3|2+3
3+3
4+3
4+2
5+2
3+3
4+2
6+1
5+1
6+1
7+1
7+0
20. Dado el rbol de bsqueda que aparece en la figura indica cual sera el recorrido que hara el algoritmo
A* e IDA* la funcin heurstica es admisible?
En el rbol la funcin heurstica esta descompuesta en la g y la h. Cuando en un nodo aparecen dos
valores el orden corresponde a la rama por la que se ha llegado al nodo.
0+6
4+2
5+2
1+5
2+3
2+4
3+3
4+3
3+3|2+3|3+3
5+2
6+2
7+0
2+4
14
3. Cerca Local
1. Existen problemas en los que dado el tamao de su espacio de bsqueda es imposible plantearse
encontrar la solucin ptima. Para este tipo de problemas se han diseado algoritmos de bsqueda
local (hill-climbing, simulated annealing, algoritmos genticos)
Estos son ejemplos de este tipo de problemas:
a) El viajante de comercio:
Un viajante de comercio desea visitar un conjunto de ciudades partiendo de una dada y acabando
en sta, sin repetir ninguna y recorriendo el mnimo de distancia (se supone que se dispone de un
mapa que indica las conexiones entre ciudades y sus distancias)
b) Mnimo k-rbol de expansin mnima:
Dado un grafo en el que cada arista tiene un peso, se trata de encontrar el subgrafo sin ciclos
(rbol) que contenga k aristas y que tenga el mnimo peso
c) Mnimo rbol de Steiner:
Dado un grafo completo (todos los vrtices estn conectados con todos), donde cada arco tiene
un peso, y un subconjunto de vrtices del grafo, obtener el grafo de coste mnimo que contenga
el conjunto de vrtices (el grafo puede contener mas vrtices, la gracia es conectar unos vrtices
especficos con el mnimo coste)
d) Bin packing en una dimensin:
Disponemos de un conjunto de contenedores y un conjunto de paquetes que colocar en ellos. Los
contenedores son todos iguales y se pueden llenar hasta cierta altura. Los paquetes tienen las
mismas dimensiones en su base que los contenedores, pero diferentes alturas, siempre por debajo
de la altura de los contenedores. El problema consiste en: dado un conjunto de paquetes saber
cual es el mnimo conjunto de contenedores necesario para transportarlos.
e) Knapsack problem:
Tambin conocido como el problema de la mochila. Dado un conjunto de objetos con cierto
volumen y cierto valor y un contenedor con una capacidad fija, hallar el conjunto de objetos que
nos debemos llevar para maximizar la ganancia.
f ) Weighted max-cut:
Dado un grafo con pesos en los arcos, partirlo en dos grafos de manera que se maximice la suma
total de los arcos de los dos subgrafos
Responde para cada problema los siguientes apartados:
Determina que elementos forman el estado y estima el tamao del espacio de bsqueda
Dado que los algoritmos que se pueden utilizar suelen partir de una solucin, busca mtodos con
los que se puede encontrar la solucin de partida (no tiene por que ser buena)
Define lo necesario para solucionar el problema mediante el algoritmo de hill-climbing (funcin
heurstica, operadores de cambio de estado)
Define lo necesario para solucionar el problema mediante algoritmos genticos (representacin del
estado, funcin de calidad, operadores de cruce y mutacin)
2. Una empresa de transporte martimo desea decidir la configuracin de la carga de su prximo barco.
La empresa recibe un conjunto de peticiones de envo de entre las que escoger. Cada peticin va dentro
de un tipo contenedor que est fijado por el tamao, el peso del envo y las caractersticas de la carga.
Existen solamente K tipos de contenedor.
15
16
NX
cont
P recioi
i=0
NX
cont
Costei
i=0
Donde N cont es el nmero de contenedores que hay en una solucin, P recioi es el precio de
transporte del contenedor i de la solucin y Costei es el coste de un contenedor i de la solucin.
b) Se plantea solucionarlo mediante Hill-climbing utilizando como solucin inicial escoger al azar
Cmin contenedores de cada tipo. Como operador utilizamos intercambiar un contenedor del barco
por otro que no est en l. Queremos usar como funcin de evaluacin de las soluciones lo siguiente:
h(n) =
NX
cont
i=0
P recioi
Costei
c) Se plantea utilizar algoritmos genticos donde la representacin de la solucin es una tira de bits
con tantos bits como peticiones haya, donde cada bit significa si la peticin est o no en el barco.
Para generar la poblacin inicial usamos la misma tcnica que en el apartado anterior. Usamos los
operadores habituales de cruce y mutacin y como funcin de evaluacin usamos la del apartado
anterior pero haciendo que valga cero si la solucin incumple las restricciones del problema.
3. Debido a la crisis y el aumento del precio del cobre, en los ltimos aos se ha vuelto habitual el
robo de cableado de cobre, tanto en gran escala (alumbrado de calles, vas del AVE) como a pequea
escala (en casas de campo, en explotaciones agrcolas, en polgonos industriales). Esto ha disparado la
demanda de cable elctrico de baja tensin de diferentes longitudes, segn lo grande del tramo robado.
Los fabricantes de cable elctrico no suelen hacer cables bajo demanda de la longitud indicada, sino
que suelen producir siempre una nica longitud fija de cable de corte (l) que se empaca y almacena
en rulos, y luego se sirven los pedidos cortando el cable de corte en tramos de cable de la longitud
solicitada (ningn tramo de cable solicitado ser de mayor que l).
Para reducir la cantidad y longitud de los tramos cortos de cable que no le sirven a nadie, nos han
pedido hacer un sistema que, dado un conjunto de pares (id_solicitud, longitud) obtenido al juntar
todos los pedidos recibidos en un da, nos diga como hemos de cortar los cables de corte que fabricamos
en tramos de cable de manera que desperdiciemos la menor cantidad de material.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comentar cada apartado
indicando si los elementos de la propuesta son correctos, eficientes en coste, mejor/peor que otras
alternativas propuestas o si hay alternativas mejores. Justifica tus respuestas.
17
a) Se plantea aplicar Hill-climbing usando como solucin inicial asignar en orden creciente de longitud tramos de cable solicitados a cables de corte; cuando la suma de las longitudes de los tramos
asignados a un cable superan su longitud se pasa al siguiente cable de corte. Como operadores
se usan mover un tramo solicitado de un cable de corte a otro y quitar un cable de corte que no
tiene tramos asignados. Como funcin heurstica se usa la suma de las longitudes de los cables de
corte que forman parte de la solucin.
b) Se plantea aplicar Hill-climbing usando como solucin inicial ir asignando al azar tramos solicitados a cables de corte; cuando la suma de las longitudes de los tramos asignados a un cable de corte
superan su longitud se pasa al siguiente cable de corte. Como operadores se usan intercambiar
dos tramos solicitados entre dos cables de corte siempre que no se supere la longitud de ninguno
de los cables a cortar, y quitar un cable de corte que no tiene tramos asignados. Como funcin
heurstica se usa la diferencia entre la longitud total de los tramos solicitados y la longitud total
de los cables de corte que forman parte de la solucin.
c) Se plantea utilizar algoritmos genticos. Para la representacin de una solucin se decide asignar
un nmero a cada tramo solicitado que se corresponder con el cable de corte que tiene asignado
(este valor ir de 1 al nmero de tramos solicitados). Con la codificacin en binario de la concatenacin de estos nmeros en un orden especfico tenemos la codificacin de una solucin. Como
mecanismo para generar la poblacin inicial se utiliza escoger al azar el cable de corte asignado a
cada tramo solicitado dentro de los valores [1, num tramos solicitados]. Como operadores genticos se usan los operadores de cruce y mutacin habituales. La funcin heurstica ser el nmero
de cables a cortar distintos que hay en la codificacin de la solucin.
4. Despus de los incendios del verano se nos plantea el problema de repoblar las reas afectadas. Dada
un rea concreta de cierto nmero de hectreas decidimos volver a repoblarla, para ello dividimos el
rea en una cuadrcula de N M y nos planteamos cuanto plantar en cada rea.
Podemos decidir un factor de repoblacin para cada elemento de la cuadrcula (F r(i)) que va de 0 a
3 (0 significa ninguna repoblacin, 1 significa plantar A rboles, ..., 3 significa plantar 3 A rboles).
Disponemos un mximo de K A rboles para plantar, pero no queremos plantar menos de I A
rboles.
Adems queremos minimizar el riesgo de incendio del rea. Este es una funcin del factor de repoblacin
de un elemento de la cuadrcula y todos los elementos adyacentes, de la siguiente manera:
X
R(i) =
F r(i) F r(j)
j adyacente a i
El objetivo es encontrar una solucin que plante el mximo nmero de rboles (entre los lmites I A
y K A ) y con el mnimo riesgo de incendio.
Una posible solucin a ste problema se puede obtener mediante el uso de algoritmos de bsqueda
local. En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos
necesarios para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comenta muy
brevemente la solucin que se propone respecto a si es correcta y si es mejor/peor respecto a otras
alternativas posibles. Justifica tus respuestas.
a) Usar Hill Climbing. Para ello generamos una solucin inicial en la que todas las reas tienen
factor de repoblacin 0. Los operadores son aumentar o disminuir el factor de repoblacin de un
rea. La funcin heurstica que queremos optimizar es:
h0 (n) =
MX
N
i=1
R(i)
MX
N
F r(i)
i=1
b) Usar Hill Climbing. Para ello generamos una solucin inicial en la que asignamos secuencialmente
factor de repoblacin 1 a cada elemento de la cuadrcula hasta llegar a la cantidad mnima de
18
h0 (n) = (
i=1
1
F r(i) K) PM N
i=1
R(i)
c) Usar algoritmos genticos. Para representar una solucin generamos una tira de 2 M N bits
(con 2 bits codificamos el factor de repoblacin). Como solucin inicial utilizamos la misma que en
el apartado anterior. Como operadores utilizamos los operadores habituales de cruce y mutacin.
La funcin heurstica que queremos optimizar es:
h0 (n) =
MX
N
i=1
R(i)
MX
N
F r(i)
i=1
5. Una empresa chocolatera desea comercializar una nueva caja de bombones que cumpla cierto conjunto
de caractersticas: el precio ha de ser el mnimo posible, el beneficio que se obtenga ha de ser el mximo
posible, ha de tener un peso limitado (no ms de 500 g, ni menos de 400 g) y ha de estar compuesta de
una combinacin de los diferentes tipos de bombones que fabrica, estos pertenecen a K tipos diferentes,
cada uno de ellos con un precio, un peso y un beneficio por bombn diferentes. La caja ha de contener
no ms de N y no menos de M bombones de cada tipo.
Una posible solucin a ste problema se puede obtener mediante el uso de algoritmos de bsqueda
local. En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos
necesarios para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comenta muy
brevemente la solucin que se propone respecto a si es correcta y si es mejor/peor respecto a otras
alternativas posibles. Justifica tus respuestas.
a) Se plantea solucionarlo mediante Hill-climbing utilizando como solucin inicial llenar la caja de
bombones de un solo tipo hasta llegar al peso mnimo y como operadores aadir un bombn
sin pasar del peso mximo y cambiar un bombn por otro de un tipo distinto. La funcin de
evaluacin es la suma del precio de los bombones multiplicada por la suma de los beneficios.
b) Se plantea solucionarlo mediante Hill-climbing utilizando como solucin inicial asignar un nmero
aleatorio de bombones de cada tipo dentro del rango [M,N]. Como operadores tenemos cambiar
un bombn de un tipo por otro de otro tipo siempre que se mantengan las cantidades mximas
y mnimas por tipo y no se violen las restricciones de peso. Se plantea utilizar como funcin de
evaluacin de las soluciones la suma del beneficio de los bombones de cada tipo que pasa de M
unidades dividida por la suma de precios de los bombones de cada tipo que pasa de M unidades.
c) Se plantea utilizar algoritmos genticos donde la representacin de la solucin es la concatenacin
de K grupos de N bits cada uno, donde cada bit determina si el bombn est o no en la caja.
Las soluciones iniciales se obtienen llenando la caja con M bombones de cada tipo. Se usan los
operadores habituales de cruce y mutacin. La funcin de evaluacin es la suma de los precios
penalizando la solucin con el valor + cuando el peso est por encima o por debajo de los
lmites de peso o se violan los lmites de nmero de bombones por tipo.
6. Se han descubierto A fuentes de contaminacin en un parque natural y se quieren colocar B (donde
B < A) aparatos de descontaminacin para mejorar la situacin. Para ello se dispone de un mapa del
parque que indica la posicin de la estacin de trenes donde se han almacenado todos los aparatos y de
los A lugares donde se necesita colocar los aparatos de descontaminacin. Adems tambin se dispone
del nivel de contaminacin que hay alrededor de cada fuente, de un mapa de los desplazamientos
(dirigidos) posibles de los aparatos en el territorio y del coste de cada desplazamiento. Cada aparato
puede eliminar por completo la contaminacin de una fuente, independientemente de su nivel.
El objetivo es colocar los aparatos de manera que se minimice la contaminacin total en el parque y el
coste del recorrido (suma de desplazamientos) que harn los aparatos en el sentido estacin fuente
de contaminacin.
19
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica). Hay que comentar la
solucin que se propone respecto a si es correcta, es eficiente, y es mejor o peor en comparacin con
otras alternativas. Y hay que justificar todas las respuestas.
a) Se plantea solucionar el problema mediante Hill-Climbing, partiendo de una solucin inicial sin
ningn aparato y con un operador que coloca un aparato en una fuente de contaminacin determinada, controlando que el nmero de los aparatos colocados sea como mximo B.
b) Se plantea solucionarlo mediante Hill-Climbing, partiendo de una solucin inicial con B aparatos colocados aleatoriamente, y utilizando como funcin heurstica la suma de los costes de
desplazamiento de la estacin a cada una de las B fuentes.
c) Se plantea solucionarlo mediante Hill-Climbing, partiendo de una solucin inicial con B aparatos
colocados aleatoriamente, y utilizando como funcin heurstica la suma de los costes mnimos de
los recorridos estacin fuente de contaminacin multiplicada por la suma de los niveles de
contaminacin en correspondientes a los B aparatos.
d) Se plantea solucionarlo mediante Hill-Climbing, partiendo de una solucin inicial alcanzada colocando los B aparatos ordenadamente segn el coste mnimo estacin fuente de contaminacin
y empezando con el que tiene coste menor. Se plantea como operador mover un aparato a cualquier fuente cuyo producto de coste mnimo estacin fuente por nivel de contaminacin
sea menor que el actual.
e) Se plantea solucionarlo mediante algoritmos genticos: se usan individuos de A bits y como
poblacin inicial se generan n individuos donde en cada uno hay exactamente B bits a 1. La
funcin de idoneidad es la suma de los costes mnimos estacin fuente de contaminacin ms
la contaminacin total residual del parque multiplicada por una constante. Como operadores se
usan los habituales de cruce y mutacin.
7. Los propietarios del hotel Bienestar trabajan habitualmente con N tour-operadores para los cuales
deben reservar siempre un conjunto de habitaciones. A principios de ao, cada operador realiza su
peticin de habitaciones para todo el ao. Las peticiones son consideradas como el nmero mximo a
reservar, pero los propietarios saben que no tienen habitaciones suficientes para cubrir todas las peticiones de todos los tour-operadores. Por esta razn, internamente tienen definido un nmero mnimo
a asignar a cada tour-operador. Este nmero les permite mantener las buenas relaciones. A partir de
aqu asignarn a los tour-operadores un nmero de habitaciones que estar entre el mnimo interno y
la peticin real recibida.
Para asignar las habitaciones, los propietarios tienen varias restricciones a respetar. Por un lado, hay
un nmero mnimo de habitaciones que queda siempre bajo la gestin directa del hotel. Por otro
lado, se quiere maximizar los beneficios obtenidos de las habitaciones reservadas a los tour-operadores,
teniendo en cuenta que los beneficios Bi son distintos dependiendo del tour-operador y el beneficio
por habitacin gestionada por el hotel es BH . Adicionalmente, se quiere maximizar la calidad de la
ocupacin para lo cual tienen asignado a cada tour-operador un ndice Qi que cuantifica la calidad de
los turistas que suelen venir a travs del operador en cuestin. Este ndice se asociar a cada habitacin
reservada para ese operador. El propio hotel tiene tambin un ndice QH .
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comentar cada apartado
indicando si los elementos de la propuesta son correctos, eficientes en coste, mejor/peor que otras
alternativas propuestas o si hay alternativas mejores. Justifica tus respuestas.
a) Se plantea aplicar Hill-climbing usando como solucin inicial asignar el mnimo de habitaciones a
cada tour-operador. Se define como operador asignar una habitacin a alguien distinto del que la
tiene asignada (tour-operador/hotel), siempre y cuando el nuevo tour-operador tenga mejor Q y
se respeten todos mnimos. Se plantea como funcin de evaluacin la suma total de los beneficios
obtenidos de cada habitacin.
20
N
X
i=1
num_habitacionesi
Bi
BH
+ num_habitacionesH
Qi
QH
21
c) Se plantea usar algoritmos genticos. Un individuo es una tira de bits cuya longitud es el nmero
total de satlites que tenemos. Si el bit est a 1 significa que el satlite est en la solucin y si
est a 0 es que no lo est. La poblacin inicial se genera creando individuos que tengan a 1 los
bits de los mi satlites con mayor coste de alquiler de cada tipo. Como operadores se usan los
habituales de cruce y mutacin. Como funcin heurstica usamos la suma del coste de alquiler de
todos los satlites en la solucin.
9. Tenemos una pequea flota de C camiones que utilizamos para repartir mercancas y cada da tenemos
que determinar qu ruta ha de seguir cada camin para abastecer un conjunto de ciudades por todo el
pas. El objetivo es que todos los camiones acaben la jornada aproximadamente a la misma hora, por
lo que el nmero de kilometros que ha de recorrer cada camin ha de ser muy parecido, y que recorran
en total el mnimo nmero de kilmetros.
Disponemos de un mapa de carreteras que nos dice la distancia en kilmetros entre cada ciudad donde
hemos de dejar nuestra mercanca, suponemos que todos los camiones parten de la misma ciudad y
han de volver a ella al final del da, cargan al principio de la jornada todo lo que han de repartir, han
de pasar slo una vez por cada ciudad.
Una posible solucin a ste problema se puede obtener mediante el uso de algoritmos de bsqueda
local. En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos
necesarios para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comenta muy
brevemente la solucin que se propone respecto a si es correcta y si es mejor/peor respecto a otras
alternativas posibles. Justifica tus respuestas.
a) Usar Hill Climbing. Como solucin inicial asignamos al azar a cada camin un nmero aproximadamente igual de ciudades, recorrindolas en orden tambin al azar. Como operadores usamos el
intercambiar dos ciudades entre los recorridos de dos camiones e intercambiar las posiciones de
dos ciudades en el recorrido de un camin. La funcin heurstica es la siguiente:
h(n) =
C
X
i=1
LRi
1
PC
C
j=1 LRj
C
Y
LRi
i=1
c) Usar Hill climbing. Como solucin inicial escogemos las C ciudades ms cercanas a la ciudad
origen como la primera ciudad a visitar por cada camin, como segunda ciudad en el recorrido de
cada camin escogemos la ms cercana a la primera que no est ya asignada, y as sucesivamente
hasta asignar todas las ciudades. Como operadores usamos el mover una ciudad del recorrido
de un camin a otro, intercambiar las posiciones de dos ciudades en el recorrido de un camin
e intercambiar dos ciudades entre los recorridos de dos camiones. La funcin heurstica es la
siguiente:
h(n) =
C X
C
C (C 1) X
LRi
2
LR
j
i=1 j=i+1
d) Usar algoritmos genticos. Donde cada ciudad est representada por tantos bits como sean necesarios para codificar el valor C, la tira de bits contiene concatenados los bits de todas las
ciudades, es decir, representamos en la tira de bits el nmero del camin que ha de recorrerla.
Como operadores utilizamos los operadores habituales de cruce y mutacin.
22
10. La sala de cine Lo nunca visto desea realizar una planificacin estratgica de las pelculas a proyectar
durante un ao (52 semanas) siguiendo varios criterios comerciales. Cada pelcula tiene asociada varias
informaciones relevantes para este problema: tipo (infantil/adulto), previsin de beneficio semanal,
ndice de calidad. La programacin anual debe contener al menos un 15 % de pelculas infantiles y un
40 % de pelculas para adultos. Se desea maximizar el beneficio anual de proyeccin de pelculas, pero
sin dejar de lado la calidad. Por este motivo, el ndice global de calidad no debe ser inferior a una
cota predeterminada (Q). En el caso de que una pelcula deba proyectarse ms de una semana, dichas
semanas debern ser consecutivas. Las estrategias comerciales exigen que una pelcula no se proyecte
ms de 8 semanas.
Teniendo en cuenta el escenario descrito, comenta brevemente las diversas propuestas que se describen
en los apartados siguientes. Valora si son correctas o no, si son eficientes o no, si son mejores o peores
que otras alternativas. Justifica tus respuestas.
a) Usar un Hill-climbing. Como estado inicial asignamos aleatoriamente una pelcula distinta a
cada una de las 52 semanas. Como operador usamos Asignar-pelcula (ttulo, num-semana), que
sustituye la pelcula asignada una semana por otra nueva o por alguna de las ya asignadas a otras
semanas.
b) Usar un Hill-climbing. Como estado inicial asignamos dos pelculas infantiles (4 semanas cada una) y seis pelculas para adultos (4 semanas cada una), el resto de las semanas se asigna
aleatoriamente. Como operador usamos el mismo del apartado a.
c) Usar un Hill-climbing. Partimos del mismo estado inicial del apartado b con el control adicional
de que el ndice de calidad no sea inferior a Q. Al operador de asignacin le aadimos como
condiciones de aplicabilidad que mantenga las proporciones mnimas de pelculas infantiles y
para adultos, que ninguna pelcula supere las 8 semanas y que se respete la cota inferior Q.
Como funcin heurstica usaremos h1(n): la suma de la previsin de beneficio semanal para cada
pelcula proyectada multiplicada por el nmero de semanas asignado.
d) Usar un Hill-climbing. Como heurstico usaremos h2(n): h1(n) + suma del ndice de calidad de
cada pelcula proyectada multiplicado por el nmero de semanas asignado.
e) Usar algoritmos genticos. Cada individuo se representa mediante 52 tiras de bits. La longitud
de la tira de bits es suficiente para codificar el nmero de identificacin de todas las pelculas.
Como poblacin inicial se generan n individuos con los criterios de estado inicial descritos en b y
c. Como funcin de fitness usamos h3(n): h1(n) + (suma del ndice de calidad de cada pelcula
proyectada multiplicado por el nmero de semanas asignado - Q). Como operadores usamos el
operador de cruce habitual, pero trabajando siempre con tiras completas de bits (la identificacin
de una pelcula), es decir, un punto de cruce nunca parte el identificador de una pelcula.
11. Los dueos del hotel Bed, bugs and beyond quieren reducir su presupuesto de limpieza para maximizar sus ganancias. Para hacerlo han decidido tener tres tipos diferentes de precios para sus habitaciones.
El precio A incluye una limpieza diaria de la habitacin y tiene un precio de pa euros por da, el precio
B incluye una limpieza de la habitacin en das alternos y tiene un precio de pb euros por da y el
precio C solo incluye una limpieza el primer y ltimo da y tiene un precio de pc por da. El mnimo
nmero de das que se pueden reservar para una habitacin es de dos, y asumiremos que la limpieza
de las habitaciones de precio B esta organizada de manera que la ltima limpieza se hace el da en el
que el cliente deja su habitacin. Tenemos un total de R habitaciones en el hotel.
Limpiar una habitacin de precio A cuesta ca euros por da de limpieza, una habitacin de precio B
cuesta cb por da de limpieza y una habitacin de precio C cuesta ca ms el nmero de das que la
habitacin ha sido reservada por cc. Las habitaciones que estn vacas no se limpian.
El departamento de sanidad impone como restriccin que toda habitacin (ocupada o no) ha de
limpiarse al menos 10 veces al mes.
El hotel recibe peticiones de reserva para un mes completo, cada reserva incluye el precio que el cliente
quiere, el da en el que la reserva comienza y el nmero de das a reservar. Asumiremos que todas las
23
peticiones comienzan y finalizan dentro del mes. El objetivo es decidir qu reservas aceptar, de manera
que los gastos de limpieza se minimicen y las ganancias se maximicen.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica, ...). El objetivo es comentar
la solucin que se propone respecto a si es correcta, es eficiente, o es mejor o peor respecto a otras
alternativas posibles. Justifica tu respuesta.
a) Queremos usar Hill-climbing, la solucin inicial es la solucin vaca. Como operadores de bsqueda
usamos aadir-reserva que aade una reserva de una habitacin, cambiar-reserva que cambia
la reserva de una habitacin por otra reserva que no est ya en la solucin. La funcin heurstica
es la suma de todos los costes de limpieza de las habitaciones multiplicado por las ganancias
obtenidas por las reservas.
b) Queremos usar Hill-climbing, la solucin inicial se obtiene de la siguiente manera: para una
habitacin elegimos una de las reservas que tenga la fecha ms temprana, la siguiente reserva ser
la que tenga la fecha ms temprana que empiece despus del final de la ltima reserva asignada
a la habitacin, repetimos este procedimiento hasta que no podamos asignar ms reservas a la
habitacin. Hacemos esto para todas las habitaciones. Como operadores de bsqueda usamos
cambiar-reserva que cambia una reserva de una habitacin por otra reserva que no este en la
solucin. La funcin heurstica es la suma de todos los costes de limpieza de las habitaciones
menos las ganancias obtenidas por las reservas.
c) Queremos usar algoritmos genticos, decidimos asignar a cada reserva un nmero de 0 a R, la
concatenacin de estos nmeros para todas las reservas en binario es la codificacin de una solucin. El nmero 0 significa que la reserva no esta asignada a ninguna habitacin, otro nmero
representa el nmero de habitacin asignada a la reserva. Para generar la poblacin inicial obtenemos una solucin asignando aleatoriamente una reserva a cada habitacin (solo R reservas
tienen un nmero diferente de 0). Como operadores genticos usamos los operadores habituales
de cruce y mutacin. La funcin heurstica es la suma para todas las reservas en la solucin del
cociente entre las ganancias obtenidas por la reserva y los costes de limpieza de la reserva.
12. Una empresa de distribucin de electricidad necesita calcular cada da qu centrales de produccin ha
de tener en marcha para abastecer la demanda de sus clientes. La empresa dispone de C centrales de
produccin elctrica ubicadas en diferentes puntos de la geografa, con una capacidad de produccin
CAi cada una. El coste diario de tener en marcha cada central es COi .
El contrato que tiene la empresa con cada uno de sus CL clientes indica la cantidad de electricidad
(Ei ) que se les debe suministrar cada da. La distancia entre los clientes y las centrales (dij ) supone
una prdida en la eficiencia del suministro, esta prdida se calcula como un factor fijo P multiplicado
por esa distancia.
El objetivo es determinar el conjunto de centrales que se han de tener en marcha y a qu clientes
han de servir, de manera que se minimice el coste de tenerlas en marcha y la prdida debida a la
distancia, teniendo en cuenta que la cantidad de electricidad que reciben los clientes de una central no
ha de sobrepasar su capacidad de produccin y que se ha de servir toda la demanda de los clientes.
Asumiremos que los valores asignados al problema siempre permiten hallar una solucin.
Una posible solucin a este problema se puede obtener mediante el uso de algoritmos de bsqueda
local. En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos
necesarios para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comenta muy
brevemente la solucin que se propone respecto a si es correcta y si es mejor/peor respecto a otras
alternativas posibles. Justifica tus respuestas.
a) Se plantea solucionarlo mediante Hill-climbing utilizando como solucin inicial asignar a cada
cliente al azar una central. Como operadores se utiliza el mover un cliente de una central a otra
e intercambiar dos clientes entre dos centrales. La funcin heurstica es la siguiente:
24
h(n) =
C
X
(COi marcha(i))
C X
CL
X
asig(i, j) dij
i=1 j=1
i=1
donde asig(i, j) es una funcin que retorna uno si el cliente i esta asignado a la central j y cero
en otro caso y marcha(i) retorna uno si la central tiene clientes asignados y cero si no.
b) Se plantea solucionarlo mediante Hill-climbing utilizando como solucin inicial un algoritmo avaricioso que ordena ascendentemente las centrales segn su coste y los clientes segn su demanda,
y va asignando clientes a las centrales segn ese orden. Cuando se sobrepasa la capacidad de una
central se pasa a la siguiente. El operador utilizado es intercambiar dos clientes entre dos centrales
siempre que no se supere la capacidad de suministro de alguna de ellas. La funcin heurstica es:
h(n) =
C
X
i=1
COi
C X
CL
X
P asig(i, j) di,j
i=1 j=1
c) Se plantea utilizar algoritmos genticos donde la representacin de la solucin es una tira de bits.
Esta est compuesta por la concatenacin de C grupos de CL bits, donde cada grupo representa
la asignacin o no de cada cliente a la central como un 1 o un 0. Las poblacin inicial la obtenemos
mediante el mismo mecanismo que en el apartado anterior. Se utilizan los operadores habituales
de cruce y mutacin. La funcin heurstica es:
h(n) =
C
X
COi marcha(i) + P
i=1
CL
C X
X
asig(i, j) di,j
i=1 j=1
13. El comit local de la federacin de ajedrez necesita establecer un calendario para la competicin anual.
En una competicin hay C diferentes categoras dependiendo de la edad y del nivel de los jugadores.
En cada categora participan un nmero Jc de jugadores, lo cual significa un nmero Rc de rondas
eliminatorias (obviamente log2 (Jc )). La competicin ha de durar un mximo de 15 das, para cada da
de competicin se disponen de F franjas horarias, en una franja solo se puede jugar una partida de
ajedrez. Obviamente se han de jugar todas las partidas de la competicin.
El calendario ha de cumplir un conjunto de restricciones:
El nmero de das necesarios para realizar la competicin ha de ser el mnimo posible.
El conjunto de rondas correspondientes a cada categora se ha de celebrar en el mnimo nmero
de das posible.
En un da se pueden jugar como mximo P partidas de una categora.
Entre dos partidas de una misma categora en un mismo da debe haber como mnimo dos franjas
horarias de separacin y como mximo cinco.
Debe haber como mnimo un da de separacin entre dos rondas de una categora.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comenta muy
brevemente la solucin que se propone respecto a si es correcta, eficiente o mejor/peor respecto a otras
alternativas posibles. Justifica tus respuestas.
a) Usar Hill-climbing. Como solucin inicial se utiliza el calendario vaco. Como operadores usamos
asignar y desasignar una partida de una ronda de una categora a una franja de un da. Como
funcin heurstica usamos el nmero de das total en los que hay partidas asignadas ms la suma
del nmero de das que ocupan las rondas de una categora.
25
b) Usar Hill-climbing. Como solucin inicial se usa el calendario resultante de aadir de manera
secuencial las competiciones de cada ronda de la primera categora manteniendo una distancia
de cinco franjas horarias entre cada partida, sin superar las P partidas diarias y manteniendo
un da de separacin entre cada ronda. Con el mismo procedimiento se van introduciendo las
competiciones del resto de categoras. Como operadores utilizamos mover una partida a una
franja no ocupada e intercambiar dos partidas. Como funcin heurstica usamos el nmero de
das total en los que hay partidas asignadas, ms la suma del nmero de das que ocupan las
rondas de una categora, ms una constante por el nmero de franjas que separan en un da las
partidas de una misma ronda y categora.
c) Usar Algoritmos Genticos. Asignamos a cada partida a jugar un cdigo binario con la longitud
necesaria para representarlas todas, aadimos a la codificacin un cdigo con todos los bits a
cero. Representamos un calendario como una cadena de bits de longitud igual al producto de F
franjas por 15 das por el nmero de bits necesarios para representar las partidas. Si una franja
no tiene una partida asignada contendr la codificacin a cero, si no tendr el cdigo de una
partida.
Para generar la poblacin inicial usamos el mtodo del segundo apartado cambiando el orden en
el que escogemos las categoras. Como operadores genticos usamos solamente el de cruce por un
punto, donde el punto de cruce no puede estar en medio de la codificacin de una partida. Como
funcin heurstica minimizamos el nmero de franjas vacas entre dos partidas consecutivas.
14. Una de las labores de los equipos de comunicaciones en una red es distribuir el flujo de paquetes
que le llegan entre los diferentes equipos con los que estn conectados, optimizando la calidad de su
distribucin.
Una posible estrategia de distribucin de paquetes sera decidir a priori cuantos de los paquetes que
se reciben en cierto momento se envan por cada conexin, sin preocuparnos exactamente de a donde
deben ir.
Un equipo de comunicaciones recibe cierto nmero de paquetes (P ) por segundo que tiene que distribuir entre sus conexiones de salida. Para cada una de las N conexiones de salida, se conocen tres
informaciones, su capacidad en nmero de paquetes por segundo, el tiempo de retraso que introduce
la conexin (tiempo medio adicional que aade el nodo de salida al tiempo de llegada a destino de
cada paquete) y el nmero medio de saltos que har cada paquete hasta llegar a su destino.
Deseamos calcular el nmero de paquetes que debemos enviar por cada conexin de salida para optimizar la distribucin de paquetes de manera que el retraso y nmero medio de saltos de los paquetes
sea el mnimo posible. Evidentemente se han de enviar todos los paquetes que llegan.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica, ...). El objetivo es comentar
la solucin que se propone respecto a si es correcta, es eficiente, o es mejor o peor respecto a otras
alternativas posibles. Justifica tu respuesta.
a) Se plantea solucionarlo mediante Hill-Climbing usando como solucin inicial el repartir los paquetes a partes iguales entre todas las conexiones. Como operador utilizamos mover cierta cantidad
de paquetes de una conexin a otra. Como funcin heurstica usamos el sumatorio para todas las
conexiones con paquetes asignados del producto entre el retraso de la conexin y el nmero de
saltos.
b) Se plantea solucionarlo mediante Hill-Climbing tomando como solucin inicial el repartir los paquetes entre las conexiones asignando aleatoriamente a una conexin el mximo de su capacidad,
repitiendo el proceso hasta haber repartido todos los paquetes. Como operador se utilizara mover cualquiera de los paquetes de una conexin a otra siempre que la operacin sea vlida. Como
funcin heurstica usamos el sumatorio para todas las conexiones con paquetes asignados del
producto entre el nmero de paquetes y el retraso de la conexin ms el sumatorio para todas
las conexiones con paquetes asignados del producto entre el nmero de paquetes y el nmero de
saltos.
26
15. La empresa Cloud For U se dedica a revender tiempo de cmputo para cloud computing y para ello
ha montado un servicio que recibe solicitudes para usar ese tiempo. Este servicio es un sistema de
pre-reserva que nos permite saber las solicitudes para un mes completo. Cada peticin nos indica un
da y hora de inicio y un tiempo de uso en horas, indicando adems la prioridad de la peticin (de 1
a 3, siendo 1 la mnima prioridad). Una peticin ha de ejecutarse completamente, sin interrupciones
y usando exclusivamente una CPU. Nosotros compramos el tiempo de cmputo en una CPU durante
un mes a M y cobramos el tiempo de cmputo a prioridad P por hora, con el compromiso de que si
no servimos la peticin, sta se servir seguro el mes siguiente a solo P por hora independientemente
de su prioridad inicial. Nos planteamos saber cuantas CPUs debemos alquilar nosotros para poder
obtener el mayor beneficio posible.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica,...). Comentar cada apartado
indicando si los elementos de la propuesta son correctos, eficientes en coste, mejor/peor que otras
alternativas propuestas o si hay alternativas mejores. Justifica tus respuestas.
a) Se plantea aplicar Hill-climbing, para crear la solucin inicial suponemos que necesitamos tantas
CPUs como peticiones nos han llegado, de manera que asignamos cada peticin a una CPU
diferente. Como operador usamos fusionar dos CPUs, que consiste en combinar las peticiones de
dos CPUs en una sola eliminando la CPU sobrante. Como funcin heurstica consideraremos que
alquilaremos las CPUs en la solucin que tengan ms del 90 % de ocupacin (CP U 90), por lo
tanto minimizaremos la funcin:
h(n) = (NCP U M )
prio(pi ) P long(pi ) +
pi CP U 90
3 P long(pi )
pi CP U 90
X
pi 6CP Uf
prio(pi ) P long(pi ) +
prio(pi ) P long(pi )
pi CP Uf
donde NCP U es el nmero de CPUs que no son la ficticia, CP Uf es el conjunto de peticiones que
estn en la CPU ficticia.
16. Tenemos que planificar la topologa de interconexin de un conjunto de routers que estn distribuidos
por el campus nord, de manera que podamos canalizar todo su trfico hacia el equipo de comunicaciones
27
que lo reenva a internet. Para cada router sabemos su localizacin en el campus (supondremos que
tenemos un sistema de coordenadas en el que podemos situar cada router) y el ancho de banda
del trfico directo que debe distribuir (el que no le llega de otros routers). Tambin conocemos las
coordenadas del equipo de comunicaciones. Cada router puede estar conectado a otro router o al
equipo de comunicaciones exterior directamente (la topologa ha de ser un rbol). Disponemos de tres
tipos de router (tipos A, B y C) capaces de distribuir hasta cierto ancho de banda mximo cada uno.
Para distribuir el trfico directo hay suficiente con un router de tipo A. El coste de cada router es
proporcional al tipo (el tipo B cuesta el doble que el A y el C el doble que el B). Para conectar cada
router necesitamos instalar un cable de cierta longitud (supondremos que es la distancia eucldea entre
las coordenadas de los dos equipos conectados) el coste de este cable es proporcional a la longitud y se
multiplica por el coste del tipo del router que enva por ese cable. El coste del equipo de comunicaciones
exterior es fijo y no lo tendremos en cuenta.
El objetivo es decidir el tipo de los routers dependiendo del ancho de banda que deben soportar y la
forma de interconectarlos, de manera que se que minimice el coste de la instalacin.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica). Hay que comentar la
solucin que se propone respecto a si es correcta, es eficiente, y es mejor o peor en comparacin con
otras alternativas. Y hay que justificar todas las respuestas.
a) Usar Hill climbing. Como solucin inicial conectamos directamente todos los routers al equipo de
comunicaciones exterior. Como operadores usamos conectar un router a otro y desconectar un
router de otro. La funcin heurstica es la suma de los costes de los routers.
b) Usar Hill climbing. Como solucin inicial calculamos el rbol de expansin mnima de los routers
y el equipo exterior y asignamos a cada router el tipo C. Como operador usamos cambiar la
conexin de un router o equipo exterior a otro. La funcin heurstica es la suma de los costes del
cableado.
c) Usar Hill climbing. Como solucin inicial conectamos cada router con el router ms cercano y
conectamos aleatoriamente uno de los routers al equipo exterior, asignamos a cada router el tipo
A. Como operador usamos cambiar la conexin de un router a otro router o equipo exterior por
otra distinta si no superamos su capacidad y cambiar el tipo del router. La funcin heurstica es
la suma de los costes del cableado ms el coste de los routers.
d) Usamos algoritmos genticos. Supondremos que los routers y el equipo exterior estn numerados
consecutivamente, supondremos que para codificar ese nmero hacen falta n bits, la codificacin
es una tira r n de bits, donde r es el nmero de routers, cada grupo de n bits corresponden a
un router siguiendo el orden de la numeracin. Como operadores usamos los operadores de cruce
y mutacin habituales. La funcin heurstica la suma de los costes de cada cable dividido por el
coste del router que enva por l.
17. Se ha de celebrar un concurso nacional de canto coral que reune a varias corales no profesionales. Con
el objetivo de reducir el desembolso que han de realizar los miembros de las corales, la organizacin
ha solicitado y ha obtenido el patrocinio de una empresa para sufragar los costes de alojamiento de
los participantes. Para llevar mejor el control del gasto en alojamiento, los organizadores del evento
han de planificar las reservas de alojamiento de los 950 asistentes en los hostales de la zona. Disponen
de una lista de hostales y para cada uno de ellos saben:
A qu distancia se encuentra del lugar de la celebracin del concurso,
Cuantas camas tiene disponibles.
El precio de la cama por noche.
Su problema es encontrar una asignacin de las 950 personas a hostales de modo que no se supere el
tope de camas disponibles en cada hostal, se minimice la suma de las distancias recorridas por todos los
asistentes y se minimice la cantidad de dinero que la organizacin va a dedicar al pago del alojamiento.
Se puede suponer que slo hay que planificar una noche, que en cada hostal todas las camas cuestan
28
18. Tras numerosas crticas por la lentitud de la justicia en Espaa, el Ministerio de Justicia quiere
mejorar la eficiencia del sistema con un nuevo procedimiento de asignacin de plazas de funcionarios a
los juzgados. Cada funcionario fi tiene un rol (juez, fiscal, abogado defensor, administrativo...), acepta
un cierto sueldo mnimo (P fi ) y acepta una distancia mxima a recorrer entre su casa y su trabajo
(Dfi ). Cada juzgado jk dispone de xr plazas nuevas por cada rol r. El ministerio paga cada plaza del
rol r a un precio mximo determinado (Prk ) que es diferente para cada juzgado jk , y dispone de una
tabla de distancias entre las viviendas de los funcionarios y los juzgados.
Se quiere asignar funcionarios a juzgados de forma que se maximice el ahorro econmico respecto a lo
que inicialmente est dispuesto a pagar el ministerio, se minimicen las distancias que los funcionarios
debern recorrer a su trabajo, y se cubra el mximo nmero de plazas nuevas, priorizando este ltimo
factor respecto a los dos anteriores.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica). Hay que comentar la
solucin que se propone respecto a si es correcta, es eficiente, y es mejor o peor en comparacin con
otras alternativas. Justifica todas las respuestas.
a) Usar Hill-climbing a partir del estado en el que no se ha asignado ninguna plaza. Utilizar los
operadores de asignar/desasignar funcionario a plaza si los roles son iguales y el sueldo que piden
es menor que el precio que se quiere pagar (Prk ). Usar como funcin heurstica la suma de sueldos
mnimos que aceptan los funcionarios asignados, ms la suma de distancias que debern recorrer
dichos funcionarios para ir a trabajar, todo ello dividido por el nmero de plazas asignadas.
b) Usar algoritmos genticos. Cada estado se representa con una cadena de bits de longitud equivalente al producto de nmero de plazas por el nmero de funcionarios. Un bit representa la
asignacin o no de un funcionario a una plaza. Los operadores son los tpicos de cruce y mutacin. La funcin de fitness es:
P
h(n) =
iF
P fi
iF Asig Dfi
+
P fi
M axD #F
iF Asig
29
Donde F es el conjunto de todos los funcionarios, F Asig es el conjunto los funcionarios asignados
a una plaza, #F es la cardinalidad de F y M axD es la distancia mayor entre la vivienda de un
funcionario y un juzgado.
19. La conocida cadena de supermercados Mercahoma desea expandirse a otras ciudades. El problema
que se le plantea es decidir qu locales son los ms adecuados para instalar sus supermercados. Para
ello disponemos de un mapa de la ciudad que nos indica L posibles locales donde podemos colocar
un total de S supermercados (obviamente L S). Adems tambin disponemos de una estimacin
de la poblacin que hay en una rea de 500 m2 alrededor de cada local en el que se puede ubicar un
supermercado.
El objetivo es colocar todos los supermercados de manera que se maximice la poblacin que vive
alrededor de cada supermercado y la suma de las distancias entre ellos (obviamente disponemos de
una tabla con sus distancias).
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica, ...). El objetivo es comentar
la solucin que se propone respecto a si es correcta, es eficiente, o es mejor o peor respecto a otras
alternativas posibles. Justifica tu respuesta.
a) Se plantea solucionarlo mediante Hill-Climbing. Como solucin inicial se parte de la solucin vaca.
Como operadores se usa el colocar un supermercado en un local vaco y quitar un supermercado
de un local. Como funcin heurstica se usa la suma de las distancias de los locales de cada
uno de los S supermercados al resto, dividido por la suma de la poblacin alrededor de cada
supermercado.
b) Se plantea solucionarlo mediante Hill-Climbing utilizando como solucin inicial el colocar aleatoriamente los S supermercados y usando como operadores de bsqueda mover un supermercado
al local vaco ms cercano respecto a su posicin actual. Como funcin heurstica se usa la suma
de las distancias de los locales de cada uno de los S supermercados al resto ms la suma de la
poblacin alrededor de cada supermercado.
c) Se plantea resolverlo mediante algoritmos genticos. Para representar el problema utilizamos una
tira de L bits y como poblacin inicial generamos aleatoriamente n individuos donde en cada uno
hay exactamente S bits a 1. La funcin heurstica es la suma de distancias de cada supermercado
al resto ms una constante por la suma de la poblacin alrededor de cada local. Como operadores
usamos un operador de cruce que intercambia aleatoriamente la mitad de los bits de cada individuo
de la pareja cruzada y un operador de mutacin que intercambia aleatoriamente dos posiciones
de la tira de bits cumpliendo que en una sea un bit a 1 y en la otra un bit a 0.
20. Como plan de emergencia ante una posible impugnacin del proceso del 9-N nos piden crear un
programa que, de forma automtica, asigne nuevas localizaciones para las urnas en locales que no
dependen de la Generalitat. Para ello nos proporcionan un mapa del territorio con L posibles locales
alternativos donde podemos colocar un total de C colegios electorales (L > C). Tenemos una tabla
con las distancias entre los locales. Adems tambin disponemos del nmero de voluntarios disponibles
en cada local en el que se puede ubicar un colegio electoral.
El objetivo es colocar todos los colegios electorales de manera que se maximice la suma de las distancias
entre ellos (para obtener as la cobertura mxima del territorio) y se maximice tambin el nmero de
voluntarios disponibles que se movilizan para ayudar en las votaciones.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica, ...). El objetivo es comentar
la solucin que se propone respecto a si es correcta, es eficiente, o es mejor o peor respecto a otras
alternativas posibles. Justifica tu respuesta.
a) Se plantea solucionarlo mediante Hill-Climbing. Como solucin inicial se parte de la solucin
vaca. Como operadores se usa el colocar un colegio electoral en un local vaco y quitar un colegio
30
4. Jocs
1. La figura segent mostra larbre dun determinat joc, generat fins a una profunditat mxima de 4. Els
nmeros que acompanyen als nodes del nivell 4 indiquen el valor de la funci davaluaci esttica per
cadascun dells.
a
12
6
12 11 10
12 10 8
b
6
d
g
0
f
8
h
7 8
i
5 4
32
Captulo 4. Jocs
2 6
1 6
4. La siguiente figura muestra el rbol de bsqueda de profundidad 4 para un determinado juego para el
jugador MAX. Los valores de los nodos terminales indican el valor de la funcin de evaluacin para la
posicin obtenida en dicho nodo.
5 6 7
3 4
2 3 4
10
a) Utiliza el algoritmo Mnimax para decidir qu jugada debe escoger MAX, indicando claramente
los valores de la funcin de evaluacin propagados a cada nodo.
b) Repite la exploracin del apartado anterior utilizando la poda alfa-beta. Indica claramente la
evolucin de los valores de alfa y beta y los nodos que se podan.
c) Crees que modificando el orden de generacin de nodos podra podarse un mayor nmero de
nodos? Justifica brevemente la respuesta.
5. Donada la segent posici del joc de dames en un tauler de 4 per 4 on nosaltres juguem amb les peces
rodones i toca jugar al contrari.
3
1
2
Indica quina seria la valoraci que min-max donaria a la jugada del contrari consistent en avanar la
pea 3 cap a lesquerra (en relaci a la nostra posici davant el tauler), tenint en compte que:
la valoraci de cada posici es fa sumant peces prpies i restant peces contrries, en base als
segents valors individuals de les peces: 1 pea = 1 punt, 1 dama = 5 punts
noms cal cercar fins a una fondria de 4 jugades (a comptar des de la posici del dibuix). Cal
que:
utilitzis lalgorisme min-max amb poda alfa-beta
generis els successors dun estat seleccionant :
primer les peces etiquetades amb un nombre mes baix
33
primer el moviment cap a lesquerra (en relaci a la nostra posici davant el tauler).
dibuixis larbre generat indicant, per cada node, lordre de visita, el valor min-max calculat,
levoluci dels valors de alfa i beta i els valors propagats a daltres nodes.
Nota per a aquells que NO saben jugar a dames:
Moviment: Una pea es pot moure a qualsevol de les caselles adjacents, diagonals del davant (en
relaci a la posici prpia davant del tauler).
Una pea pot matar una pea contrria si aquesta est al davant i pot saltar pel damunt en
diagonal (o sigui la posici on va a parar est lliure).
Coronaci: Una pea esdev dama si es situa en una casella de la darrera fila (en relaci a la
posici prpia davant del tauler).
Moviment de dama: Una dama es pot desplaar en qualsevol sentit de qualsevol diagonal i en un
nombre no restringit de caselles.
6. Supongamos la siguiente posicin en un juego de damas en un tablero 4 x 4. Las piezas propias son 1
y 2, las del contrario son 3 y 4. Acabo de jugar y la posicin es:
4
3
2
1
Valorar la posicin utilizando min-max con profundidad de bsqueda 4 (dos jugadas del contrario y
dos propias) a partir de la posicin del dibujo. La valoracin de una posicin se obtiene sumando los
puntos de las pieza propias y restando las del adversario. Cada pieza vale 1 punto. Al coronar las
piezas se convierten en damas y valen 5 puntos.
El orden de generacin de los sucesores es:
la pieza 1 (3) tiene prioridad sobre la 2 (4)
Si una pieza tiene ms de un movimiento, tiene prioridad el de menor abscisa.
NO se aplicar la regla de la "bufada".
Se pide:
a) Utilizar el algoritmo min-max SIN poda dibujando el rbol e indicando para cada nodo el orden
de visita y el valor de la posicin.
b) Hacer lo mismo con el algoritmo min-max CON poda alfa-beta indicando adems la evolucin de
los valores alfa/beta.
c) Comparar los resultados, ha habido ahorro en el nmero de nodos visitados? Nota per a aquells
que NO saben jugar a dames veure regles al problema 5.
7. Supongamos la siguiente posicin en un juego de damas en un tablero 4 x 4. Las piezas propias son 1
y 2, las del contrario son 3 y 4. Acabo de jugar y la posicin es:
4
3
1
2
34
Captulo 4. Jocs
Valorar la posicin utilizando min-max con profundidad de bsqueda 4 (dos jugadas del contrario y
dos propias) a partir de la posicin del dibujo. La valoracin de una posicin se obtiene sumando los
puntos de las piezas propias y restando las del adversario. Cada pieza vale 1 punto. Al coronar las
piezas se convierten en damas y valen 5 puntos.
El orden de generacin de los sucesores es:
la pieza que pueda comer. Si hubiera ms de una, el orden sera (1, 2) o (3, 4)
la pieza 1 (3) tiene prioridad sobre la 2 (4)
Si una pieza tiene ms de un movimiento, tiene prioridad el de menor abscisa.
NO se aplicar la regla de la "bufada".
Se pide:
a) Aplicar el algoritmo min-max SIN poda, dibujando el rbol e indicando para cada nodo el orden
de visita y el valor de la posicin.
b) Hacer lo mismo con el algoritmo min-max CON poda alfa-beta indicando adems la evolucin de
los valores alfa/beta.
c) Comparar los resultados, ha habido ahorro en el nmero de nodos visitados? Nota per a aquells
que NO saben jugar a dames veure regles al problema 5.
8. Tenemos el tablero que aparece en la figura, en la que el jugador MAX tiene las fichas marcadas como
X y el min las fichas marcadas como O. La nica ficha que pueden mover los jugadores es la marcada
como +. Esta ficha se puede mover hacia la derecha y hacia la izquierda y tiene el efecto de cambiarse
con la ficha que ocupa la posicin a la que se desplaza y cambiar el signo de esa ficha y de la que pasa
a ser su contigua. Por ejemplo, en la configuracin XOXO+XOXO, si desplazamos la ficha + hacia la
derecha obtenemos la configuracin XOXOO+XXO. El objetivo de cada jugador es tener 5 fichas del
mismo tipo seguidas.
X
35
N
B
B
N
B
a) Utiliza el algoritmo de minimax con poda alfa-beta para averiguar qu movimiento deberan hacer
las blancas desde la posicin inicial. Explora hasta profundidad 2 (un movimiento de las blancas
y otro de las negras). Para la evaluacin de los estados utiliza la siguiente tabla para asignar valor
a cada ficha, el valor de un estado se obtiene sumando los valores de las fichas propias y restando
las del contrario.
4
2
2
4
2
1
1
2
2
1
1
2
4
2
2
4
F
C
N
B
B
N
36
Captulo 4. Jocs
a) Utiliza el algoritmo de minimax con poda alfa-beta para averiguar qu movimiento deberan hacer
las blancas desde la posicin inicial. Explora hasta profundidad 2 (un movimiento de las blancas
y otro de las negras). Para la evaluacin de los estados utiliza la siguiente tabla para asignar valor
a cada ficha, el valor de un estado se obtiene sumando los valores de las fichas propias y restando
las del contrario.
4
2
2
4
2
1
1
2
2
1
1
2
4
2
2
4
2
1
2
1
Cada jugador posee una mitad del tablero, el jugador MAX tiene la mitad superior y el jugador MIN
la mitad inferior. Cada jugador escoge en cada turno una de las celdas de su mitad. Cuando se escoge
una celda, sta pasa su valor a sus celdas adyacentes de la siguiente manera: 2 puntos (o 1 si la celda
slo contiene 1) pasan a la celda inferior en el caso de MAX o superior en el caso de MIN, el resto de
puntos que queden se reparten, primero un punto a la celda de la izquierda y despus un punto a la
celda de la derecha, si aun quedan puntos, uno pasa a la celda superior en el caso de MAX o inferior
en el caso de MIN. Los puntos que queden se mantienen en la celda elegida. Si se reparten todos los
puntos la celda queda con un valor de 0. Se gana cuando se consigue que en la zona del contrario la
suma de los valores de las celdas sea igual o superior a 9.
a) Aplicar el algoritmo minimax con poda alfa-beta dos niveles (una jugada de MAX y otra de
MIN) para averiguar cual sera la jugada de MAX a partir de la posicin inicial. Para evaluar las
posiciones se ha de utilizar la siguiente funcin:
Vposicin= VMAX - VMIN
VMAX= suma de valores de la zona MIN - suma de diferencias de la zona MAX (valor de celda
mayor de 2 - 2)
VMIN= suma de valores de la zona MAX - suma de diferencias de la zona MIN (valor de celda
mayor de 2 - 2)
Por ejemplo:
0
3
1
2
2
3
0
1
37
b) A partir de la jugada elegida por MAX, hacer una nueva bsqueda para averiguar cual ser la
respuesta de MIN.
13. El siguiente juego sobre un tablero 3x4 empieza con las fichas X en la fila 1 y con las fichas O en la
fila 4. Un jugador gana cuando consigue colocar todas sus fichas en la fila del contrincante. Dada la
siguiente situacin del juego, donde le toca jugar al contrincante (fichas O),
1
2
3
4
1
X
X
O
O
O
1
2
3
4
1
A
A
A
B
B
38
Captulo 4. Jocs
y aplicando los movimientos ESTRICTAMENTE en el siguiente orden. Seleccin de fichas: mover
primero la ficha ms cercana al objetivo que est ms a la izquierda, seleccionar la segunda con el
mismo criterio y luego mover la tercera. Orden de seleccin de movimientos: 1) Saltar. 2) Mover a
diagonal izquierda. 3) Mover en vertical. 4) Mover a diagonal derecha.
a) Aplicar el algoritmo minimax con una profundidad mxima 2 para obtener la siguiente jugada a
realizar. Utiliza la siguiente funcin de evaluacin de estados:
FAE = V(B) - V(A)
donde V(*) es el nmero de movimientos posibles para las fichas *. Si no hay posibilidad de
movimientos para esas fichas, el valor de V(*) ser .
b) Aplicar el algoritmo minimax bajo las mismas circunstancias para el mismo propsito. Qu
jugada te recomienda ahora?
c) Cuntos nodos se han podado?
d) Existe algn orden de aplicacin de movimientos diferente al exigido que podra provocar ms
podas?
O
X
X
1
O
2
O
X
3
X
O
4
a) a Cul sera el movimiento que hara la mquina si el juego estuviera implementado con un algoritmo minimax de profundidad 2? Representa los pasos seguidos por dicho algoritmo suponiendo
que se est utilizando la siguiente FAE:
FAE = posibles alineaciones para el ordenador - posibles alineaciones para la persona
39
donde una posible alineacin significa la existencia de una posibilidad de llegar a conseguir una
alineacin en lo que queda de juego. Por ejemplo, en el estado dibujado, la persona (O) tiene 4
posibles alineaciones (una en diagonal, una vertical y dos horizontales) mientras que el ordenador
(X) tiene dos posibilidades (una en diagonal y una horizontal).
ORDEN ESTRICTO: Considera las posibles jugadas recorriendo las columnas de izquierda a
derecha.
b) Cul sera dicho movimiento si la implementacin incorporase podas Representa los pasos
seguidos por dicho algoritmo de forma separada del apartado (a). Para ello etiqueta con letras
maysculas (A, ... , Z, AA, ...) cada estado del apartado (a) y utilzalas aqu. Cuntos nodos se
han podado?
17. El juego del Nim se juega a partir de varias filas de palillos de las cuales un jugador puede retirar, en
un turno, el nmero que desee de palillos pero de una nica fila. El jugador que retira el ltimo palillo
pierde.
Podemos representar la configuracin de las filas mediante secuencias de enteros. Por ejemplo, (1, 3,
5) indica que hay tres filas con uno, tres y cinco palillos respectivamente.
Se pide:
a) A partir de la configuracin (1, 2, 2), utiliza el algoritmo minimax para averiguar qu movimiento
deberamos realizar primero.
b) Repite la exploracin utilizando la poda alfa-beta. Qu movimiento nos aconseja? Cuntos
nodos se han podado?
Orden de generacin de sucesores: de izquierda a derecha segn el orden indicado en la secuencia de
enteros y aplicando todos los movimientos posibles para cada fila antes de pasar a la siguiente. Dentro
de cada fila, se comenzar por retirar un palillo, luego dos, y as sucesivamente. Si el estado resultante
de la aplicacin de un movimiento es una permutacin de otro estado hermano anterior, no hay que
incluirlo en el rbol (por ejemplo, de (1,2,2) se puede pasar a (1,1,2) y tambin a (1,2,1), pero este
ltimo no se incluir en el rbol). Estados finales: En el rbol, son estados finales tanto los estados
con cero palillos como los estados con un palillo ya que en ambos casos podemos marcar quien es el
ganador.
18. Tenemos el tablero que aparece en la figura, en la que el jugador MAX tiene las fichas marcadas como
A y el MIN las fichas marcadas como B. Los jugadores pueden mover sus fichas y las del contrario.
Los movimientos posibles son dos:
desplazamiento de una ficha a la casilla libre contigua
salto de una ficha sobre otra contraria (slo una) cambiando de signo la ficha contraria, siempre
y cuando la siguiente casilla est libre. Ejemplo: ABA_BAB A_BBBAB
Restriccin: una jugada de desplazamiento no es vlida si simplemente est deshaciendo la jugada
anterior. Por ejemplo, si un jugador pasa de AB_BBAB al estado ABB_BAB, el otro jugador no
puede volver a pasar a AB_BBAB. El objetivo de cada jugador es tener 4 fichas del mismo tipo
estrictamente consecutivas.
A
40
Captulo 4. Jocs
a) Utiliza el algoritmo minimax con poda alfa-beta para evaluar cual debera ser el primer movimiento del jugador MAX. Haz la exploracin hasta el nivel 3 (dos jugadas de MAX y una de
MIN). Aplica siempre el mismo orden: movimientos posibles recorriendo el tablero de izquierda
a derecha. Para cada nodo muestra claramente la evolucin de los valores alfa y beta. Cul es
el movimiento que debera escoger MAX?
b) Cuntos nodos nos ahorramos respecto al uso del algoritmo sin poda?
5. Satisfacci de restriccions
1. Una empresa de alquiler de vehculos dispone de una flota con las siguientes caractersticas:
Coche1
Coche2
Coche3
Coche4
Coche5
Coche6
Coche7
Coche8
Coche9
Coche10
Marca
Ford
Citroen
Mercedes
Citroen
Seat
Opel
Mercedes
BMW
Citroen
Seat
Color
Blanco
Azul
Gris
Verde
Rojo
Blanco
Rojo
Negro
Gris
Azul
Precio/da
30 euros
35 euros
60 euros
30 euros
35 euros
35 euros
35 euros
60 euros
40 euros
40 euros
Peticin1
Peticin2
Peticin3
Peticin4
Peticin5
Precio/da
<= 40 euros
<= 30 euros
<= 60 euros
<= 40 euros
<= 60 euros
Color
NO Azul
Azul O Blanco
NO Gris y NO Negro
NO Rojo y NO Azul
Blanco
Tenemos la restriccin adicional de que no puede haber dos coches de la misma marca. Considera las
peticiones como variables, en el mismo orden en que figuran, y los coches de la flota como valores,
tambin en el mismo orden en que se listan.
a) Aplica forward-checking para resolver el problema. Desarrolla el proceso hasta el punto en el que
encuentres una solucin. Indica en cada paso slo los dominios que se modifican.
b) Aplica backtracking cronolgico hasta el segundo backtracking a la variable peticin 1.
2. El director de la coral infantil "Veus suaus" tiene que decidir el orden de colocacin de los ocho cantores.
Debe distribuirlos en dos filas (A, B) de forma que en cada fila queden en orden decreciente de altura,
colocando el ms alto a la izquierda (posicin 1). Adems, la altura de cada ni@ de la fila trasera
(A) debe ser superior o igual a la del que tenga delante. Finalmente, no quiere colocar dos herman@s
seguid@s en la misma fila ni un@ delante del otr@. La relacin de ni@s y sus alturas es la siguiente:
Nombre
Esteva Blanco
Pedro Costa
Ana Costa
Juan Costa
Oriol Pi
Mara Ruiz
Rosa Snchez
Carla Snchez
41
(EB)
(PC)
(AC)
(JC)
(OP)
(MR)
(RS)
(CS)
Altura
1,40
1,60
1,50
1,30
1,40
1,60
1,50
1,30
42
D-C-B-C-D
43
a) Utiliza el algoritmo de forward checking para dar una solucin a la ubicacin de estos 7 personajes
en una mesa circular (cada comensal slo tiene dos vecinos, uno a la derecha y otro a la izquierda).
Usa para la exploracin de los valores el orden en el que estn en el enunciado.
b) Resuelve el mismo problema aplicando el algoritmo de backtracking cronolgico.
6. Deseamos resolver el crucigrama de la figura colocando las siguientes palabras: ROLLO, SALVO,
SOLAR, ROCAS, OCIOS, SILOS.
a) Para resolverlo aplica el algoritmo de forward checking utilizando las posiciones para las palabras
como variables y las palabras como valores utilizando la numeracin para las variables que se
indica la figura y explorando las palabras en el orden en que se dan en el enunciado.
b) Resuelve ahora el problema aplicando el backtracking cronolgico.
2
1
5
6
NOTA: las palabras horizontales se colocan de izquierda a derecha y las palabras verticales de arriba
a abajo. No hay palabras escritas al revs.
7. Una petita empresa ha de comprar telfons mbils pels seus directius. Han estat mirant preus de
companyies telefniques i es troben amb la segent informaci:
Companyia
MultiStaf (MS)
AguaTel (AT)
FunkyTel (FT)
TopeVisin (TV)
Tarifa
5000
6000
4500
3500
Aquesta petita companyia t cinc executius i vol assignar-los un telfon mbil a cadascun sota les
segents restriccions:
No pot haver-hi ms de dos executius amb la mateixa companyia.
El cost total de lassignaci de companyies a executius no ha de superar les 21.000 ptes.
Es demana:
a) Resoldre completament el problema aplicant forward checking.
b) Desenvolupar laplicaci del backtracking cronolgic fins al punt en que el backtracking ens porta
a revisar la primera assignaci feta a la segona variable.
NOTA: Per ambds apartats considereu que els executius es representen per E1, E2, E3, E4 i E5. Els
valors possibles sn MS, AT, FT, TV i cal considerar-los sempre en aquest ordre.
44
45
43
40
47
aos
aos
aos
aos
Pilotos
P1 Asensio
P2 Martn
P3 Marn
P4 Casales
32
35
38
40
aos
aos
aos
aos
Las normas de la compaa, para vuelos fuera de Europa, impiden que la suma de edades del comandante y el piloto exceda de 75 aos. Adicionalmente, los comandantes son muy supersticiosos y
no admiten que su piloto tenga como inicial de apellido la misma que ellos. Aplica el algoritmo de
forward checking para configurar las cuatro tripulaciones necesarias. Explicita los valores posibles de
cada variable en cada paso. Utiliza variables y valores en el orden en que aparecen en el enunciado.
9. El senyors Grfol tenen el problema habitual de cada Nadal i que consisteix en comprar regals per
als seus nebots/nebodes. Han de comprar regals per als germans Joan i Maria, per als germans Pere,
Ana i Oriol i per en Ramon i en Xavier, ambds fills nics. Han decidit que compraran dos jocs iguals
descacs, docs jocs iguals dexperiments de qumica i tres llibres didctics iguals. Per a repartir aquests
regals entre els nebots han de tenir en compte que, per raons bvies, no poden donar el mateix regal
entre germans, que ni el Joan ni el Xavier poden tenir el mateix regal que lOriol i que el Ramon no
pot tenir el mateix regal que lAna.
NOTA: Utilitza els noms dels nebots en lordre en que apareixen a lenunciat. Els regals sidentifiquen
per E1, E2, Q1, Q2, L1, L2, L3 i tamb cal respectar aquest ordre.
a) Dibuixa el graf de restriccions entre les variables.
b) Resol el problema aplicant forward checking. Indica clarament a linici i a cada pas el domini de
les variables.
c) Inicia el procs de resoluci aplicant cerca en profunditat i backtracking cronolgic. Desenvolupa
el procs fins al moment en que es produeix el segon backtracking cap a Oriol.
d) Creus que el backtracking cronolgic trobar la soluci? Justifica la resposta.
10. Una empresa de telefona mvil quiere colocar seis antenas en una ciudad cuyas posibles ubicaciones
estn reflejadas por este grafo:
1
Donde cada arco indica que existe visin directa entre dos posiciones. Las antenas tienen las caractersticas siguientes:
Antena
A
B
C
D
E
F
Frecuencia
20 GHz
1.8 GHz
20 GHz
1.8 GHz
20 GHz
1.8 GHz
Potencia
1 Mw
2 Mw
3 Mw
1 Mw
1 Mw
2 Mw
45
Las restricciones de colocacin de las antenas son las siguientes: No se pueden colocar dos antenas
consecutivas de la misma frecuencia No puede haber dos antenas con visibilidad directa cuya suma de
potencia sea superior a 4 Mw
a) Considerando las posiciones de las antenas como variables y las antenas como los dominios de
estas variables, utiliza el algoritmo del forward checking para buscar una solucin a la colocacin
de las antenas usando para la exploracin el orden en el que aparecen las posiciones y las antenas
en el enunciado. Desarrolla el algoritmo hasta el primer backtracking a la primera variable.
b) Desarrolla el algoritmo de bactracking cronolgico hasta el punto en que deba realizarse el primer
backtracking. Para cada asignacin que falle indica brevemente el motivo.
11. El responsable del peridico "Noticias frescas" debe confeccionar la primera pgina de la edicin de
maana que consta de cuatro posiciones tal como se ve en la figura
Noticias Frescas
8-junio-2002
P1
P2
P3
P4
N1:
N2:
N3:
N4:
N5:
N6:
N7:
mbito
Nacional
Nacional
Internacional
Nacional
Nacional
Internacional
Internacional
Tema
Poltica
Sucesos
Poltica
Deportes
Poltica
Sociedad
Sucesos
46
13. Deseamos construir un circuito ubicando los componentes de manera que las distancias que los componentes permitan su correcto funcionamiento. El circuito sobre el que queremos trabajar es una
cuadrcula de 3x3, de manera que cada componente tiene asignado unas coordenadas.
Tenemos que ubicar 4 componentes (A,B,C,D), las restricciones entre ellos son:
La distancia entre el componente A y B ha de ser mayor o igual a 2
La distancia entre el componente A y C ha de ser 1
La distancia entre el componente B y C ha de ser 2
La distancia entre el componente B y D ha de ser 1
La distancia entre el componente C y D ha de ser 1
Para calcular la distancia entre dos componentes se usa la funcin: d(a,b)=|ax-bx|+|ay-by|-1, donde
ax es el valor de la coordenada x del componente a, ay es el valor de la coordenada y del componente
a, dem para el componente b Considera los componentes como variables y las componentes como los
valores de estas variables. Como orden de exploracin, empieza por la esquina superior izquierda y
sigue el orden de izquierda a derecha y de arriba a abajo.
a) Utiliza el algoritmo de forward checking para explorar el problema hasta llegar al tercer valor de
la variable A
b) Utiliza el algoritmo de backtracking cronolgico para explorar el problema hasta el primer backtracking a la variable B
c) Se puede simplificar el primer problema eliminando valores del dominio de las variables propagando las restricciones? Porqu?
d) Se puede aprovechar alguna caracterstica del problema para simplificarlo y probar menos valores
en la bsqueda?
e) En muchas ocasiones se pueden intercambiar variables y valores en los problemas de satisfaccin
de restricciones. Cules seran los dominios de valores si usramos como variables las posiciones
en lugar de los componentes?
14. Tenim les segents peces dun trencaclosques:
A
Fent servir les segents posicions del trencaclosques com a variables i les peces com a valors (poden
efectuar-se rotacions sobre les peces, excepte per la C i la I):
47
1
10
9
2
11
8
3
12
7
4
5
6
el domini de cada variable queda inicialment restringit, donades les caracterstiques del puzzle.
a) Utilitza backtracking cronolgic per completar el trencaclosques.
b) Fes-ho ara amb forward checking.
NOTA: En ambdos casos, feu servir lordre numeric per les variables i lordre alfabtic pels valors.
Deixa clar quins son els passos donats!!
15. Una empresa de consultora tiene que organizar el trabajo de tres proyectos durante tres das y dispone
de cuatro consultores para llevarlos a cabo. Cada consultor puede dedicar un conjunto de horas a cada
proyecto, este conjunto de horas est dividido en fracciones (un consultor slo tiene dos fracciones de
dedicacin al da), las horas de cada consultor en cada fraccin de dedicacin son las siguientes:
Consultor
C1
C2
C3
C4
Disponibilidad
2.5
4
3
1.5
48
17. Dado el siguiente grafo de restricciones donde cada restriccin es una condicin de desigualdad y los
siguientes dominios para las variables:
A={1,2,3}
B={1,2}
C={2,3}
D={2,3}
E={1,2,3}
Haz la ejecucin del backtracking cronolgico hasta el primer backtracking a la variable A y del forward
checking hasta encontrar la primera solucin
18. Dado el siguiente grafo de restricciones donde cada restriccin es una condicin de desigualdad y los
siguientes dominios para las variables:
A={1,2}
B={2,3}
C={1,3}
D={2,3}
E={1,3}
49
A={1,2}
B={2,3}
C={1,2}
D={1,2,3}
E={1,2,3}
E
50
1. Utilitzant les regles i fets que apareixen a continuaci, mostreu com un sistema de producci amb
encadenament cap enrera (seguint una estratgia seqencial en la selecci tant de fets i regles com
dobjectius), intentaria demostrar R(a).
Base
F1.
F2.
F3.
F4.
de hechos
P(b)
F5.
U(b)
F6.
Q(c,d)
P(a)
S(d,b)
Q(a,c)
Base
R1.
R2.
R3.
R4.
de reglas
P(x) P(y) S(x,y) R(y)
U(x) T(y) Q(x,y)
Q(x,y) S(y,x)
S(z,x) S(z,y) Q(x,y)
Base
R1.
R2.
R3.
de reglas
S(x,y) Q(y,x)
Q(x,z) Q(z,y) S(x,y)
P(x) P(y) Q(x,y) R(x)
de hechos
P(b)
F4.
S(a,b) F5.
Q(a,c)
P(c)
Q(a,d)
a) Seguint encadenament cap endavant, mostreu com un sistema de producci amb estratgia seqencial en la selecci de les regles arribaria a R(c).
b) Fer el mateix considerant que el criteri de resoluci de conflictes escull la regla amb ms condicions.
3. Considera la siguiente base de hechos (donde cada hecho viene acompaado por el momento de su
creacin) y la siguiente base de reglas:
Base
H1.
H2.
H3
de hechos
A(e) H4.
D(e) H5.
A(n) H6.
P(n)
A(s)
C(n,s)
Base
R1.
R2.
R3.
de reglas
A(x) A(y) C(x,y) L(x,y)
L(x,y) L(y,z) L(x,z)
D(x) P(y) C(x,y)
a) Considera el objetivo L(e,s) y comprueba si es deducible aplicando razonamiento hacia atrs. Utiliza la estrategia de resolucin de conflictos: 1o ) subobjetivo ms reciente, 2o ) primer subobjetivo
por la izquierda, 3o ) regla ms especfica 4o ) hechos en secuencia. Indica claramente para cada
iteracin el conjunto conflicto, la seleccin realizada y el resultado de la aplicacin de la regla.
b) Considera ahora el objetivo L(n,e) y comprueba si es deducible aplicando razonamiento hacia
delante. Utiliza la estrategia de resolucin de conflictos: 1o ) regla ms general, 2o ) instanciacin
ms antigua, 3o ) hecho ms antiguo en la primera condicin. Indica claramente en cada iteracin
el conjunto de conflicto, la seleccin realizada y el resultado de la aplicacin de la regla. Una
estrategia distinta dara mejores resultados?
4. Tenemos la siguiente base de reglas y la siguiente base de hechos:
Base
H1.
H2.
H3.
de hechos
P(a)
P(b)
R(a)
Base
R1.
R2.
R3.
R4.
51
de reglas
P(x) R(y) Q(x,y)
Q(x,y) Q(y,x)
P(x) P(y) R(y)
Q(x,y) R(y) P(x)
52
de hechos
P(a,c)
Q(c)
R(d)
P(c,d)
Base
R1.
R2.
R3.
R4.
R5.
de reglas
P(x,y) R(y) Q(x)
Q(x) R(x)
Q(x) P(x,y)
Q(x) P(x,y) R(y)
P(x,y) P(y,z) R(y)
a) Realiza los 5 primeros pasos del razonamiento hacia delante con la estrategia de resolucin de
conflictos 1) primera regla en secuencia 2) instanciacin con hechos ms recientes 3) condicin de
mas a la izquierda con hecho ms antiguo. Especifica claramente para cada iteracin el conjunto
de conflicto, la seleccin realizada y el resultado de la aplicacin de la regla
b) Realiza los 5 primeros pasos del razonamiento hacia delante con la estrategia de resolucin de
conflictos 1) regla ms especfica 2) instanciacin con hechos ms antiguos 3) condicin de mas
a la izquierda con hecho ms antiguo 4) primera regla en secuencia. Especifica claramente para
cada iteracin el conjunto de conflicto, la seleccin realizada y el resultado de la aplicacin de la
regla
c) Realiza los 5 primeros pasos del razonamiento hacia delante con la estrategia de resolucin de
conflictos 1) regla ms general 2) instanciacin con hechos ms recientes 3) condicin de mas a la
izquierda con hecho ms recientes 4) primera regla en secuencia. Especifica claramente para cada
iteracin el conjunto de conflicto, la seleccin realizada y el resultado de la aplicacin de la regla
d) Realiza la traza del razonamiento hacia atrs para intentar resolver el objetivo R(b) utilizando
como estrategia de resolucin de conflictos 1) objetivos en secuencia 2) hechos mas recientes 3)
regla ms general 4) primera regla en secuencia. Especifica claramente para cada iteracin el
objetivo, el conjunto de conflicto, la seleccin realizada y el resultado de la aplicacin de la regla
6. Dados la siguiente base de hechos (cada hecho viene precedido por el tiempo en que ha sido establecido)
y base de reglas:
Base
H1.
H2.
H3.
H4.
de hechos
P(a)
Q(c)
R(10)
P(c)
Base
R1.
R2.
R3.
R4.
de reglas
P(a) Q(e) Q(b)
P(c) R(x) (x < 15 ) (y = x - 5) R(y)
Q(b) R(x) (x < 5 ) S(e)
Q(x) Q(e)
53
a) Dado el objetivo S(e) y suponiendo un mecanismo de razonamiento hacia delante con estrategia
de resolucin de conflictos: 1o ) regla ms especfica y 2o ) instanciacin ms reciente,
1) Indica las 3 primeras iteraciones en la aplicacin de las reglas, mostrando para cada una de
ellas el conjunto de conflictos, la seleccin realizada y el resultado de la aplicacin.
2) Si detectas algn problema, propn alguna solucin.
b) Dado el objetivo R(0) y suponiendo un mecanismo de encadenamiento hacia atrs con estrategia
de resolucin de conflictos: 1o ) regla ms especfica, 2o ) subobjetivo ms simple y 3o ) hechos ms
antiguos,
1) Indica las 3 primeras iteraciones mostrando para cada una de ellas el conjunto de conflictos,
la seleccin realizada y el resultado de la aplicacin.
2) Qu pasara si el objetivo fuera R(20)?
7. Suposeu que tenim la segent de fets (fets precedits per lidentificador temporal del moment de creaci)
i Base de regles:
Base
F1.
F2.
F3.
F4.
de hechos
P(a)
Q(c)
S(a)
P(c)
Base
R1.
R2.
R3.
R4.
de reglas
P(x) C(x,y) S(x)
S(x) C(x,y) R(x)
S(x) C(y,x)
P(x) C(x,y)
a) Donat lobjectiu C(a,x) i suposant estratgia de raonament cap endavant amb els criteris de
resoluci de conflictes: 1er.) regla ms especfica i 2n.) instanciaci ms recent, mostra les quatre
primeres iteracions daplicaci de les regles. Mostra explcitament cadascun dels conjunts de
conflictes que hi ha, la regla finalment seleccionada a cada pas i el resultat daplicar-la.
b) Donat lobjectiu ( C(x,b) R(a) ) i suposant estratgia de raonament cap enrera amb criteris de
resoluci de conflictes: 1er.) suobjectiu (predicat) amb menys parmetres i 2n.) ordre seqencial
de les regles, mostra les cinc primeres iteracions daplicaci de les regles. Mostra explcitament
cadascun dels conjunts de conflictes que hi ha, els subojectius pendents a cada iteraci, la regla
finalment seleccionada a cada pas i el resultat daplicar-la.
8. Es frecuente encontrar en las secciones de pasatiempos de los peridicos cosas como "dado un nmero,
normalmente alto, cmo puede expresarse a travs de una expresin aritmtica sobre un conjunto de
nmeros bsico?". Este ejercicio se basa en la misma idea: Considerse el siguiente conjunto de hechos
y reglas:
Base
H1.
H2.
H3.
de hechos
par(0)
num(1)
num(17)
Base
R1.
R2.
R3.
R4.
R5.
R6.
R7.
de reglas
par(x) par(x+2)
par(x) x>0 par(x-2)
num(x) num(y) num(x+y)
num(x) num(y) num(x*x)
num(x) par(x) num(x/2)
num(x) num(x*x)
num(x) num(y) x > y num(x-y)
Suponemos que los valores que pueden recibir las variables son nmeros naturales menores que 100.
El objetivo es num(9). Se pide:
a) Considerar un sistema de razonamiento dirigido por hechos en el que la resolucin de conflictos
se lleve a cabo de acuerdo a los siguientes criterios:
1) Tendr prioridad la regla ms compleja.
54
de hechos
num(13)
num(4)
num(2)
divexacta(4,2)
divexacta(2,2)
Base
R1.
R2.
R3.
R4.
R5.
R6.
R7.
de reglas
num(x) num(y) divexacta(x,y) mltiplo(x,y)
num(x) divexacta(x,2) par(x)
num(x) no divexacta(x,2) impar(x)
par(x) (x > 2) par(x-2)
par(x) par(x+2)
num(x) mltiplo(x,2) par(x)
par(x) impar(y) impar(x+y)
55
Base
H1.
H2.
H3.
H4.
H5.
H6.
H7.
Base
R1.
R2.
R3.
R4.
R5.
R6.
de Hechos
cliente(P)
cliente(Q)
cliente(R)
pariente(Q,R)
rico(Q)
trabajador(P)
especial(R)
H8.
H9.
H10.
H11.
H12.
H13.
H14.
salario(P,100.000)
posee(R,C1)
valor(C1,600.000)
trabajador(S)
salario(S,200.000)
posee(S,C2)
valor(C2,1.000.000)
de reglas
cliente(x) rico(x) crdito(x,y)
cliente(x) pariente(x,y) rico(y) rico(x)
pariente(x,y) pariente(y,x)
cliente(x) posee(x,y) valor(y,z) (z>t) crdito(x,t)
cliente(x) trabajador(x) salario(x,y) (y3 > z) crdito(x,z)
cliente(x) especial(x) crdito(x,y) crdito(x , 2y)
de reglas
cliente(x) rico(x) crdito(x,y)
cliente(x) pariente(x,y) rico(y) rico(x)
pariente(x,y) pariente(y,x)
cliente(x) posee(x,y) valor(y,z) crdito(x,z)
cliente(x) trabajador(x) salario(x,y) crdito(x,3y)
Aplica razonamiento hacia delante para saber el crdito mximo para las cuatro personas (P,Q,R,S).
En cada iteracin indica el conjunto conflicto, la seleccin realizada y el resultado de la aplicacin
de la regla. Estrategia de resolucin de conflictos: 1) Regla con ms condiciones, 2) Instanciacin
ms antigua.
11. Considera la siguiente base de hechos (donde cada hecho viene acompaado por el momento de su
creacin) y la siguiente base de reglas:
Base
H1.
H2.
H3.
H4.
H5.
H6.
de hechos
P(a,b)
E(a,b)
E(b,c)
C(a)
C(b)
C(c)
Base
R1.
R2.
R3.
R4.
R5.
R6.
de reglas
P(x,y) P(y,x)
P(x,y) H(x,y)
C(x) V(x)
H(x,y) S(x,y)
V(x) E(x,y) S(x,y)
M(x,y) S(x,y)
a) Resuelve el objetivo S(b,a) suponiendo el mecanismo de inferencia dirigido por hechos y una
estrategia de resolucin de conflictos con los criterios: 1o ) regla ms especfica, 2o ) primera regla
en secuencia, 3o ) instanciacin con hechos ms antiguos. Indica en cada iteracin el conjunto de
conflicto, la seleccin realizada y el resultado de la aplicacin.
56
12. Dadas las siguientes bases de hechos y conocimiento donde los hechos estn ordenados por antigedad,
x, y son variables y a, b, c son constantes:
Base
H1.
H2.
H3.
H4.
H5.
H6.
H7.
de hechos
T(b,c)
P(a)
Q(b,c)
T(c,b)
P(c)
Q(a,a)
Q(a,b)
Base
R1.
R2.
R3.
R4.
R5.
R6.
R7.
de reglas
T(c,x) Q(x,c) U(a) R(c,x)
T(b,x) S(a) P(x)
P(x) U(y) R(x,y)
S(x) R(x,b)
P(x) Q(a,x) S(x)
S(x) P(x) U(x)
R(x,c) U(y) Q(x,y)
Base
H1.
H2.
H3.
H4.
H5.
H6.
de hechos
U(b,c)
P(a,f)
P(f,f)
P(b,a)
U(f,c)
R(a,h)
Base
R1.
R2.
R3.
R4.
R5.
R6.
R7.
de reglas
U(x,c) S(x,e)
P(x,f) S(x,e)
S(x,e) U(x,h) Q(x,e)
S(x,e) U(x,c) Q(x,b) ? Q(x,e)
U(x,c) R(x,d)
P(b,x) R(x,h) U(x,h)
R(x,d) U(x,c)
57
Base
F1.
F2.
F3.
F4.
F5.
F6.
F7.
de hechos
Q(d,b)
Q(a,a)
P(a,b,d)
R(a,d)
P(a,c,d)
R(a,c)
S(a,b)
Base
R1.
R2.
R3.
R4.
R5.
R6.
de reglas
Q(x,y) S(x,y)
P(x,y,z) Q(z,a) S(z,y)
R(x,y) Q(y,x) R(y,z) S(x,z)
R(x,y) S(x,y) P(x,d,y)
R(x,y) S(x,t) Q(y,b) P(x,t,z)
R(x,y) P(x,z,y) Q(x,z)
a) Veure si el fet s(a,c) es deduble per raonament cap enrera aplicant la seqent estratgia de
sel.lecci de regles, fets i objectius: 1) objectius en ordre seqencial dels ms recentment creats,
2) regla ms especfica, 3) regla en ordre seqencial, 4) fets en ordre seqencial.
b) Realitzar les 5 primeres iteracions de raonament cap endavant aplicant la segent estratgia
de sel.lecci: 1) regla ms especfica, 2) instanciaci ms recent (comparaci feta per ordre de
predicats).
15. Considera la siguiente base de hechos (donde cada hecho viene acompaado por el momento de su
creacin) y la siguiente base de reglas:
Base
H1.
H2.
H3.
H4.
H5.
de hechos
P(a,b)
P(b,c)
Q(b)
T(c)
S(b)
Base
R1.
R2.
R3.
R4.
de reglas
T(x) P(x,y) S(x)
R(x,y) P(y,x)
P(x,y) S(y) R(y,x)
P(x,y) Q(x) R(x,y)
de hechos
R(a)
R(b)
Q(b)
Base
R1.
R2.
R3.
R4.
de reglas
R(x) R(y) P(x,y)
R(x) P(x,x)
P(x,y) Q(x) R(x)
P(x,y) R(y) Q(y)
a) Realiza los 3 primeros pasos del razonamiento hacia adelante con la estrategia de resolucin de
conflictos 1) primera regla en secuencia, 2) instanciacin con hechos mas recientes. Especifica
claramente para cada iteracin el conjunto de conflicto, la seleccin realizada y el resultado de la
aplicacin de la regla.
b) Realiza los 3 primeros pasos del razonamiento hacia adelante con la estrategia de resolucin de
conflictos 1) regla mas general, 2) instanciacin con hechos mas recientes. Especifica claramente
para cada iteracin el conjunto de conflicto, la seleccin realizada y el resultado de la aplicacin
de la regla.
c) Realiza los 3 primeros pasos del razonamiento hacia adelante con la estrategia de resolucin de
conflictos 1) regla mas especfica, 2) instanciacin con hechos mas antiguos. Especifica claramente
para cada iteracin el conjunto de conflicto, la seleccin realizada y el resultado de la aplicacin
de la regla.
58
17. Considera la siguiente base de hechos (donde cada hecho viene acompaado de su momento de creacin)
y de reglas:
Base de hechos
H1. R(a)
H2. Q(b)
Base de reglas
R1. P(x,y) Q(x) P(x,x)
R2. Q(x) Q(y) P(x,y)
R3.
R4.
P(x,y) Q(y)
R(x) Q(y) Q(x)
a) Realiza los 4 primeros pasos del razonamiento hacia adelante con la estrategia de resolucin de
conflictos 1) primera regla en secuencia 2) instanciacin con hechos mas recientes 3) condicin de
mas a la izquierda con hecho mas reciente. Especifica claramente para cada iteracin el conjunto
de conflicto, la seleccin realizada y el resultado de la aplicacin de la regla.
b) Realiza los 4 primeros pasos del razonamiento hacia adelante con la estrategia de resolucin de
conflictos 1) regla mas especfica 2) hechos mas antiguos 3) condicin de mas a la izquierda con
hecho mas antiguo. Especifica claramente para cada iteracin el conjunto de conflicto, la seleccin
realizada y el resultado de la aplicacin de la regla.
c) Utiliza el razonamiento hacia atrs para resolver el objetivo P(b,a) utilizando como estrategia de
resolucin de conflictos 1) objetivos en secuencia 2) reglas en secuencia 3) hechos en secuencia.
Especifica claramente para cada iteracin el conjunto de conflicto, la seleccin realizada y el
resultado de la aplicacin de la regla.
d) Utiliza el razonamiento hacia atrs para resolver el objetivo Q(c) utilizando como estrategia de
resolucin de conflictos 1) objetivos en secuencia 2) reglas en secuencia 3) hechos en secuencia.
Especifica claramente para cada iteracin el conjunto de conflicto, la seleccin realizada y el
resultado de la aplicacin de la regla.
18. Considera la siguiente base de hechos, en la que cada hecho viene acompaado de su momento de
creacin, y la de reglas:
Base de hechos
H1. Q(b)
H2. R(a)
Base de reglas
R1. Q(x) Q(y) P(x,y)
R2. Q(x) P(x,x)
R3.
R4.
Usuarios de una biblioteca que tienen prestados libros publicados antes de cierto ao
Tiempo que lleva prestado un libro a un usuario
Nmero de documentos que citan a un documento
Libros que nunca se han prestado
Usuarios de cierto tipo que son usuarios de una biblioteca
2. Desde hace un tiempo internet ha visto una iniciativa de web colaborativa donde mltiples personas aportan su opinin sobre un tema. Esta iniciativa se ha bautizado como WikiWiki (termino que
viene del Hawaiano y significa rpido). Dentro de esta filosofa de contenidos colaborativos ha aparecido la iniciativa WikiPedia (www.wikipedia.org), una enciclopedia multiidioma gratuita creada con
colaboraciones de todos los usuarios de internet.
Pretendemos organizar la creacin de la WikiPedia registrando la informacin bsica para su funcionamiento. La WikiPedia esta a cargo de diferentes personas entre las que tenemos a los autores, que
59
60
3. LIRC (Internet Relay Chat) s una de les possibilitats que internet ofereix per tal de relacionar
gent de diverses parts del Mn. Els components bsics sn els anomenats canals, en els que la gent
entra i pot parlar (b, teclejar i llegir) amb tota la resta de gent que hi ha al canal. Dins de les
moltes coses que hi ha al mn de lIRC existeixen unes coses anomenades bots que no sn res ms
que programes que es dediquen a tasques variades. El nostre objectiu s dissenyar un sistema de
representaci estructurada del coneixement per tal de possibilitar la construcci dun bot intelligent.
Per tal de fer-ho, a continuaci es descriur de forma molt simplificada, quins coneixements bsics
sobre lIRC ha de disposar el bot: Com en la gran majora de coses dinternet, hi ha dos tipos de
mquines: els servidors i els clients (identificats per ladrea IP, un nom de mquina, sistema operatiu,
etc.).
Qui proveeix els recursos per utilitzar lIRC sn els servidors (dels quals s necessari saber el(s) nmero(s) de port(s) que permeten). Els servidors dIRC sagrupen en xarxes (p.e. Undernet, Dalnet,
Hispanet, ....) de les quals, a part del nom, s interessant saber la plana web que tenen, les adreces electrniques dels responsables, etc. A cadascuna de les xarxes es formen diversos canals que sidentifiquen
amb un nom. De canals hi ha de dos tipus: els enregistrats i els no-enregistrats. En un canal enregistrat
61
hi ha una persona que s el manager del canal, vries que en sn administrados i daltres que en sn
operadors. En els canals no-enregistrats, qui mana s el primer que es connecta (quan tafegeixes a un
canal no enregistrat i abans dit canal estava buit, ets automticament el responsable del mateix).
Els ordinadors clients sn els que utilitzem des de casa (o des daltres llocs que no esmentar) per tal
de connectar-nos a lIRC. Cada usuari es connecta des del seu ordinador i sidentifica dins de lIRC
amb un nom, anomenat nick. Dun usuari normalment tamb s interessant conixer ladrea de mail,
el nom real, etc. Cada usuari, via el seu ordinador es connecta a un servidor duna xarxa concreta i,
una vegada connectat, por accedir a tots el canals de la xarxa (els canals pertanyen a la xarxa i no als
servidors que formen part de la mateixa).
Es demana:
a) Dissenyar un sistema de representaci estructurada del coneixement i indicar, per cada concepte,
els atributs que el caracteritzen (no cal definir completament cada atribut).
b) Caracteritzar completament les relacions entre servidor i xarxa, entre client i usuari, entre client
i servidor i entre servidor i usuari.
c) Ladrea IP dun usuari coincideix amb la del client que est utilitzant. Definir completament
lslot IP i modifiqueu el que calgui per a que dita deducci pugui realitzar-se.
d) Definir un demon que implementi la funci /server que s la que utilitza un usuari per tal de
connectar-se a un servidor. Dit demon ha de comprovar que no hi hagi cap altre usuari amb el
mateix nick a la xarxa a la que pertany el servidor.
e) Definir un demon que implementi la funci /list tal que permeti, per a cada usuari, saber els
noms dels canals als quals pot accedir en un moment donat.
4. El membres del grup de recerca TALP de la UPC estan posant en marxa un sistema automtic
dinformaci telefnica sobre el servei de trens. Per a desenvolupar aquest projecte es necessita representar el coneixement del domini. En concret, volem representar informaci sobre les lnies (origen,
dest, longitud, etc) i els diferents tipus de lnies (rodalies, regionals, grans lnies nacionals, internacionals), sobre els trens (nom, composici/categoria, serveis, etc.) i els diferents tipus de trens (tramvia,
intercity, rpid, exprs, Talgo, Euromed), sobre els punts daturada (estacions i baixadors) i les persones que treballen a lempresa (maquinistes, revisors, taquillers, cambrers,...). Es demana:
a) Proposa un sistema de representaci estructurada del coneixement per aquest domini indicant els
diferents conceptes aix com les relacions taxonmiques entre ells. Indica dos o tres atributs per
a cada concepte. Caracteritza completament un atribut tipus-lnia del frame lnia.
b) Caracteritza la relaci que permeti connectar un tren amb la lnia on dona servei. Aquesta relaci
ha de permetre inferir el tipus de lnia per a cada tren en servei. Qu passaria si fs possible que
un tren dons servei a ms duna lnia?. Revisa la caracteritzaci de tipus-lnia.
c) Caracteritza la relaci c.1) entre lnia i punt daturada per on passa i la relaci c.2) entre tren i
punt daturada on para. El procs ser sempre primer definir una lnia i desprs assignar-hi trens,
per tant a la relaci c.2) cal definir un demon que doni un missatge derror en cas de que estiguem
connectant un tren amb un punt daturada que no pertany a la lnia on el tren dona servei.
d) Defineix un mtode amb un parmetre que ens permeti saber el nom dels trens dun determinat
tipus que paren en un punt daturada concret i per cadascun daquests trens el tipus de lnia i
lorigen i el dest de la mateixa. Situa adequadament aquest mtode.
e) Caracteritza la relaci entre maquinista i tren que condueix. Aprofitant tot el que tens definit
fins ara, caracteritza la relaci entre maquinista i punt daturada.
5. Els propietaris de lagncia de viatges Ms enll han decidit reorganitzar tota la informaci de la que
disposen per tal de tenir-la ms integrada. Duna banda, volen mantenir informaci de les empreses
amb qui treballen (Majoristes turstics, cadenes hoteleres, empreses de lloguer dautocars, empreses de
lloguer de guies, etc.), sobre algunes de les persones lligades a aquestes empreses (conductors, guies,
62
63
e) Define un mtodo que reciba como parmetro el nombre de una sala y que permita saber el
nombre de los pacientes ingresados en esa sala y el de todos los mdicos que han escrito en el
historial clnico de esos pacientes. Sita adecuadamente este mtodo.
7. El holding MegaServeis, S.L. s una agrupaci dempreses de serveis de tota mena: empreses de serveis
de missatgeria, empreses de serveis dinformtica, empreses de serveis de traducci, etc. El conjunt
de persones que treballen per al holding de manera fixa o per contracte temporal es molt ampli i
de profesions diverses: administratius, missatgers, traductors, programadors,... Cada empresa t una
problemtica segons els tipus de serveis que ofereix. Ens fixarem en les empreses de traducci. Les empreses de traducci reben encrrecs de documents a traduir. Aquests documents poden ser de temtica
diversa: cientfic-tcnics (llibres de text, manuals, articles,...), literaris (novel.les, assaigs,...), oficials
(reglaments, butlletins,...), etc. A cada document li assignen dues persones diferents: un traductor i
un revisor, amds experts en les llengues font i dest de la traducci. Per aquesta ra han de mantenir
informaci de persones contractables amb indicaci de les llenges que dominen. Els documents poden
tenir tres estats possibles: rebut, assignat, acabat. Es demana:
a) Proposar a la gerncia de MegaServeis un sistema de representaci estructurada del coneixement
que permeti gestionar els diferents tipus dempreses i, en particular, tot el que es descriu per a
les empreses de serveis de traducci. Assigna dos o tres atributs a cada concepte.
b) Caracteritza les relacions entre document i traductor al qual est assignat i entre document i revisor assignat. Aquestes relacions han de tenir un demon que avisi en cas de que el traductor/revisor
no sigui expert en alguna de les dues llenges (font i dest) que sapliquen al document.
c) Cada document acabat t assignat un valor (1..5) que correspon al grau de satisfacci de lempresa
amb la traducci realitzada. Es defineix el nivell de qualitat dun traductor com la nota mitjana
de tots els documents que ha traduit (independentment de la llengua). Defineix un atribut amb
demon per tal de gestionar automticament aquest nivell de qualitat per a cada traductor. Fora
possible deduir el nivell de qualitat dun traductor per mecanismes dherncia?
d) Caracteritza la relaci entre document i empresa de serveis de traducci que reb lencarrec. A
partir de les relacions definides fins ara, defineix una relaci entre traductor i empresa de serveis.
e) Defineix un mtode amb un parmetre que ens permeti llistar el ttol de tots els documents dun
determinat tipus que shan encarregat a una empresa. Cada document ha danar acompanyat de
la segent informaci: llengua origen, llengua dest, nom del traductor i nom del revisor. Sita
adequadament aquest mtode.
8. El ministerio de telecomunicaciones, deseoso de poder manejar de manera sencilla y eficiente la informacin correspondiente a todos los medios de comunicacin que emiten su seal al aire, quiere usar
un sistema de frames para organizarla.
La informacin que se desea organizar es la siguiente: Actualmente dos tipos de medios informativos
emiten su informacin al espacio radioelctrico, emisoras de radio y de televisin. Los programas
que emiten se pueden clasificar esencialmente en dos, los programas de entretenimiento (variedades,
concursos, cine, series, ...) y los programas de informacin (informativos, debates, reportajes, ...).
Estos programas estn asignados a las diferentes franjas horarias que forman la parrilla de emisin.
Las diferentes franjas horarias estan clasificadas segun el pblico al que van dirigidos los programas
(prime-time, infantil-juvenil, noctmbulos, ...) Cada emisora tiene su personal, que podramos dividir
en el personal tcnico, que se encarga de que todo funcione correctamente (tcnicos de sonido, cmaras,
regidores, ...) y el personal no tcnico, que es el que da la cara en los programas (presentadores,
corresponsales, humoristas, etc.).
a) Propn una representacin estructurada del dominio, asignando entre uno y tres atributos a
los conceptos que aparecen. Define el atributo pas de corresponsala, correspondiente a un
corresponsal y el atributo ranking de un programa que indique su posicin en los ndices de
audiencia segn su tipo de programa.
64
10. Una empresa logstica est interesada en organizar la informacin de todos sus envos, por lo que se
plantea hacer una representacin de la informacin que interviene en su negocio. La empresa se encarga
de realizar envos que pueden ser de paquetes (grandes y pequeos) o correo. Los envos los realizan
clientes que pueden ser empresas o particulares. Para realizar la recogida y entrega de los envos utiliza
vehculos (camiones, o furgonetas).
El almacenaje de los envos est organizado en centros de distribucin, que es donde se recogen todos
los envos para ser trasladados a los centros de reparto, que es desde donde se realizan las entregas.
El traslado de los envos puede realizarse a otros centros de distribucin con los que tiene conexin de
manera que un envo puede pasar por varios centros de distribucin hasta llegar al centro de reparto.
a) Propn una representacin estructurada del dominio. Especifica al menos tres atributos para cada
uno de los conceptos principales. Especifica completamente el atributo destino en el frame envo,
capacidad de almacn en almacn y tara en vehculo.
65
b) Define la relacin enva entre envo y cliente, la relacin asignado entre vehculo y almacn, la
relacin almacena entre envo y almacn y la relacin recibe entre envo y cliente.
c) Define la relacin conecta entre almacenes. Define el atributo hotpotato de forma que indique,
para un almacn, el nombre del almacn que tiene mayor espacio libre de entre los que est
conectado. Define la relacin recoge entre vehculo y envo de manera que compruebe que el
peso de los paquetes que ha recogido no superen su tara. En ambos casos, define todo lo que sea
necesario.
d) Queremos que el envo herede la ubicacin del almacn que lo tiene almacenado, define lo necesario
para que esto sea posible. Se puede hacer mediante herencia? Sirve la herencia si un paquete
es trasladado a otro almacn? Caracteriza el slot ubicacin.
e) Define el mtodo reparto que, para un centro de reparto, haga un listado de los envos de un
determinado tipo, indicando el nombre del cliente que ha de recibirlo y la matrcula del vehculo
que lo ha de recoger. Ubica adecuadamente el mtodo. Define lo que creas necesario para que se
pueda implementar el mtodo Es heredable este mtodo?
11. Una gran cadena de distribucin de ordenadores nos ha encargado que diseemos para ella una representacin del conocimiento que usa su organizacin de manera que pueda construir un sistema que
lo utilice. Esta cadena est organizada en tipos de departamentos que pueden estar ubicados en las
diferentes tiendas que tiene. Tenemos los departamentos de ventas, servicio post venta, almacn, y
departamento de montaje. Las tiendas estn organizadas en sucursales (slo tienen departamento de
ventas), centros de atencin (slo tienen servicio post venta), centros de montaje (slo tienen almacn
y departamento de montaje) y grandes centros (slo tienen departamento de ventas y servicio post
venta). Los ordenadores que vende la cadena se clasifican en porttiles y de sobremesa, stos a su vez
se clasifican en cuatro categoras: servidores, estaciones grficas, SOHO y hogar.
Esta cadena tiene dos tipos de clientes: las grandes empresas y los pequeos clientes, que incluyen las
pyme, los profesionales liberales y los particulares.
a) Propn una representacin estructurada del dominio. Especifica al menos tres atributos para cada
uno de los conceptos principales. Especifica completamente el atributo nmero de empleados
en departamento y potencia en ordenador.
b) Define la relacin vende entre departamento de venta y cliente, la relacin encarga entre departamento de venta y de montaje, la relacin monta entre departamento de montaje y ordenador
y la relacin elige entre cliente y ordenador.
c) Define la relacin ubicado entre departamento y tienda, esta relacin ha de comprobar que el
tipo de tienda acoge a los departamentos correctos. Define la relacin almacena entre almacn y
ordenador de manera que no se exceda la capacidad de almacenaje del almacn y que el ordenador
se almacene en el mismo centro de montaje en el que el ordenador es montado. Define lo que sea
necesario.
d) Queremos que las tiendas hereden el slot nmero de empleados de los departamentos que tiene
ubicados define lo necesario para que esto sea posible. Es la herencia la mejor solucin?
e) Define el mtodo pedidos que liste los ordenadores de un determinado tipo vendidos, indicando
los nombres de los clientes a los que se han vendido y el centro de montaje en el que se ha
encargado el montaje de cada ordenador. Ubica adecuadamente el mtodo. Define lo que creas
necesario para que se pueda implementar el mtodo Es heredable este mtodo?
12. El Institut Catal de la Salut (ICS) desea organizar toda la informacin relativa a sus competencias.
Por un lado, desea representar la informacin de los centros: ambulatorios y hospitales. Existen tres
tipos de ambulatorios: centro de asistencia primaria (CAP), centro de especialistas (CE) i centro
no reconvertido (CNR). Algunos ambulatorios disponen de un servicio de urgencias y otros no. Los
hospitales propios pueden ser generales o comarcales. Los hospitales concertados son hospitales privados
con convenio de asistencia con el ICS.
66
13. Dado el complicado panorama de la solicitud de fondos para la investigacin, el ministerio de ciencia
y tecnologa ha decidido poner a disposicin de todos los investigadores la informacin relativa a los
proyectos de investigacin y las concesiones de ayudas de los diferentes organismos mundiales. Existen
diferentes organismos financiadores que conceden ayuda econmica para el desarrollo de proyectos de
investigacin, entre estos tenemos organismos transnacionales como por ejemplo la Unin Europea u
organizaciones dependientes de Naciones Unidas (UNESCO, UNICEF, ACNUR, ...), Organismos gubernamentales (NSF, CNRS, CICyT, CIRIT, ...) o Fundaciones privadas (Empresas, organizaciones sin
nimo de lucro, ...). Estas organismos financiadores conceden ayudas a la investigacin en proyectos de
diferente temtica, como por ejemplo tecnologas de la informacin y de la comunicacin (Inteligencia
Artificial, Redes de comunicaciones, Sociedad de la Informacin,...), fsica (Altas energas, materiales,
astrofsica, ...), salud (lucha contra el cncer, creacin de vacunas, ...), humanidades (historia, poltica,
...), etc. Son los diferentes grupos de investigacin que trabajan para diferentes organismos cientficos
(centros de investigacin transnacionales (CERN, ...), universidades (publicas y privadas) y centros de
I+D de la industria) los que proponen, en solitario o coordinadamente entre varios grupos, proyectos
a los organismos financiadores.
Se pide:
a) Propn una representacin estructurada del dominio. Asigna al menos tres atributos para cada
uno de los conceptos principales. Especifica completamente el atributo ubicacin para los organismos cientficos y el atributo nmero de investigadores para los grupos de investigacin.
b) Define la relacin evala entre organismo financiador y proyecto de investigacin, la relacin
propone entre grupo de investigacin y proyecto, y la relacin financia entre organismos financiadores y grupos de investigacin.
c) Define tambin la relacin concede entre organismo financiador y proyecto de investigacin
de manera que compruebe que, si el organismo que concede la financiacin es un organismo
transnacional, el proyecto est propuesto por al menos tres grupos de investigacin de distintas
nacionalidades. Se trata de una relacin compuesta? Define en organismo financiador el slot presupuesto comprometido que calcule el dinero total que ya ha concedido (indica las diferentes
maneras de realizar el clculo).
67
d) Queremos que los grupos de investigacin hereden el atributo ubicacin del organismo cientfico
para el que trabajan, define todo lo necesario para que esto sea posible.
e) Define el mtodo proyectos financiados que haga una lista de todos los proyectos concedidos
por un organismo financiador, indicando el cdigo de proyecto, el dinero aportado y el nombre y
nmero de componentes de los grupos de investigacin que participan. Ubica adecuadamente el
mtodo.
14. Una gran multinacional desea organizar la informacin de su negocio mediante un sistema de representacin del conocimiento. Por una parte, existe informacin sobre clientes, los cuales pueden
ser empresas privadas, empresas pblicas o particulares (personas a ttulo individual), y empleados
(auditores, consultores, financieros). Por otro lado, esta multinacional ofrece dos tipos diferentes de
producto, servicios y banca. Entre los servicios ofrece consultora (informtica, legal,... ) y auditora
(financiera, medioambiental,...). La banca incluye prstamos (personales, hipotecas) e inversiones en
renta fija y variable (en bolsa, fondos de inversin,... ). Cada empleado tiene asignada una zona donde
acta. Los clientes particulares tienen asociado un grado de fiabilidad entre 0 y 1 segn su solvencia.
a) Propn un sistema de representacin estructurada del conocimiento que permita gestionar todos
los conceptos expuestos. Indica dos o tres atributos para cada concepto. Caracteriza el atributo
zona de empleado.
b) Un empleado puede realizar ofertas o ventas de productos. Caracteriza ambas relaciones entre
empleado y producto. Incluye un demon que avise en caso de que un empleado que no sea
financiero pretenda vender un producto que sea de banca.
c) Cada empleado contacta con varios clientes para ofrecer productos. La empresa desea tener una
medida del valor potencial de un cliente segn las ofertas que ha recibido. Define un slot valor
potencial que calcule el valor de un cliente a partir del nmero de ofertas que le han hecho.
d) Define la relacin entre cliente y productos que compra. A partir de las relaciones definidas
hasta ahora, caracteriza la relacin entre empleado y cliente. Es posible deducir la zona de un
cliente a partir de la de un empleado por mecanismos de herencia? En caso afirmativo, modifica
la representacin adecuadamente.
e) Define un mtodo que permita listar la fiabilidad media de los clientes particulares que han
adquirido prstamos personales. Sita este mtodo adecuadamente.
15. Una empresa de parkings intel.ligents ens ha encarregat la modernitzaci del control automatic de cada
un dels seus parkings, de manera que des duna cnsola externa, el client pugui demanar que li sigui
aparcat o retornat el seu vehicle, entre altres serveis automtics. El director de lempresa ens informa
que els parkings estan destinats a diversos tipus de vehicles: cotxes, furgonetes, motos i bicicletes. Per
optimitzar lespai, els parkings disposen de places grans, mitjanes i petites. Cada una delles es localitza
en un parking mitjanant un identificador. Una de les tasques que han de controlar els parkings es la
gesti automtica de locupaci de les places. Per aquest motiu, han de coneixer quines places lliures
estan destinades a la venda i quines al lloguer. Sespera que aquestes places passin a ser privades o
contractades (mensualment o ocasionalment). Una vegada sha ocupat una plaa, sha de coneixer
quin ser el preu de manteniment/lloguer que haur de pagar el seu ocupant per mes/hora. A ms a
ms, cada parking ofereixen diferents tipus de serveis automatitzats als client, cada un dells a diferent
preu: rentar, encerar, passar laspiradora, inflar les rodes, etc. No obstant, degut a les limitacions dels
robots, aquests serveis poden no haver estat realitzats satisfactoriament en opini dels clients. Amb
motiu de millorar-los, el parking ha de coneixer si algn dels tipus de serveis es defectus. Com que
el director de lempresa es molt exigent, un tipus de servei es considerat defectus si ha rebut alguna
queixa. Es demana:
a) Representar el coneixement necessari per a aquesta aplicaci mitjanant frames. Assigna tres
atributs a cadascun dels conceptes principals. Especificar totalment el slot preu.
b) Especificar totalment les relacions entre plaa i parking, entre vehicle i plaa, i entre servei i
vehicle. Especificar, tamb, la relaci entre servei i parking a partir de les anteriors.
68
16. Una gran empresa multinacional desea organizar la informacin relativa a la gestin de los recursos
informticos de su organizacin. La descripcin de su problemtica es la siguiente: La empresa cuenta
con personal que utiliza y mantiene los diferentes recursos, este personal se puede clasificar en: usuarios (expertos o noveles), administradores de sistemas y personal de mantenimiento. El personal est
organizado en departamentos (contabilidad, recursos humanos, investigacin y desarrollo, marketing,
informtica, direccin), cada departamento tiene una ubicacin.
Para organizar el parque informtico se piensa en contemplar una clasificacin segn el sistema operativo de la mquina (Windows, Unix, Mac/OS) y segn el uso que se hace (workstation, servidor,
ofimtica). Estas mquinas proveen diferentes servicios, como por ejemplo servicios de Internet (servicio de web, de ftp) servicio de base de datos, servicio de almacenamiento, ...
a) Propn una representacin estructurada del dominio. Especifica al menos tres atributos para cada
uno de los conceptos principales y caracteriza completamente tres de ellos
b) Las mquinas de la empresa se pueden asignar directamente a usuarios o a departamentos, en
ambos casos el uso de la maquina es en exclusiva, caracteriza esta relacin. En el caso de mquinas asignadas a departamentos, estas pueden ser usadas por muchos usuarios, pero solo del
departamento o solamente por el usuario asignado si esta asignada a un usuario en concreto,
caracteriza esta relacin Que se le debe aadir a esta relacin para que sea coherente con la semntica que se pretende? Aade lo que sea necesario a la representacin para que se compruebe
que una maquina no est asignada simultneamente a una persona y a un departamento.
c) Las mquinas estn ubicadas en el departamento en el que estn asignadas o en el departamento
al que pertenece la persona que la tiene asignada. Aade a la representacin y/o modifica lo
necesario para que esta informacin se pueda obtener mediante el mecanismo de herencia.
d) Los servidores son proveedores de los diferentes servicios descritos, que son instalados por el
personal de administracin. Aade lo necesario a la representacin para que se pueda obtener
para una mquina especfica la lista de las personas que han instalado los diferentes servicios
que provee esa mquina. que diferencia habra respecto de usar un demon o un mtodo? y si
quisiramos slo la informacin de un tipo de servicio concreto?
e) Supongamos que queremos obtener de la representacin un listado de todos los usuarios de cierto
tipo que tienen una mquina con cierto sistema operativo, que le deberamos aadir a la representacin para que fuera posible? Caracteriza y/o programa el slot, demon o mtodo que sea
necesario.
17. El Ministerio de Ciencia y Tecnologa desea organizar toda la informacin relativa a los proyectos de
investigacin que financia. El Ministerio distingue entre dos tipos de proyectos: investigacin orientada
e investigacin no orientada. Los primeros, a su vez, se dividen en proyectos de investigacin bsica y
proyectos de investigacin aplicada. En el caso de la investigacin aplicada hay dos modalidades: con
participacin opcional de empresas y con participacin obligatoria de empresas. Los proyectos tienen
un cdigo de identificacin, un ttulo, un presupuesto, unos objetivos, etc. Los proyectos pueden ser
presentados por un nico grupo de investigacin (proyecto simple) o por varios (proyecto coordinado).
Los proyectos coordinados constan de varios proyectos simples (los subproyectos), cada uno con un
grupo de investigacin como responsable. Adems, uno de estos grupos ser el coordinador del proyecto
coordinado.
69
Los participantes pueden ser Empresas y grupos de investigacin pertenecientes a Universidades, Centros pblicos/privados de investigacin, Centros pblicos/privados de I+D. Las empresas siempre
tienen que participar en proyectos en colaboracin con grupos de investigacin. Las empresas no pueden actuar como coordinador de proyecto, salvo en el caso de los proyectos de investigacin aplicada
con participacin obligatoria de empresas donde el coordinador ha de ser forzosamente una empresa.
Cada grupo de investigacin cuenta con un investigador principal y varios investigadores colaboradores.
Cada empresa cuenta con un representante y varias personas adscritas. Cada grupo y cada empresa
tienen un cdigo de identificacin.
a) Propn una representacin estructurada del dominio. Asigna al menos tres atributos a cada uno
de los conceptos principales. Caracteriza las relaciones entre proyecto coordinado y subproyectos,
entre proyecto simple y participante responsable, entre proyecto coordinado y participante coordinador y entre persona y grupo de investigacin al que pertenece. Caracteriza completamente el
slot cdigo de identificacin.
b) Incorpora lo que sea necesario a las relaciones entre proyecto y participante responsable/coordinador que compruebe que el responsable HA de ser una empresa para el caso de proyectos de
investigacin aplicada con participacin obligatoria de empresas y NO ha de serlo en cualquier
otro caso.
c) Un proyecto de cualquier tipo se considera de alto nivel si el participante responsable lo es. Puedes
establecer mediante mecanismos de herencia esta inferencia? En caso afirmativo, propnlos. En
caso negativo, propn otro mecanismo para poder realizar la inferencia.
d) Un proyecto coordinado se considera conflictivo si el nmero de participantes es superior a
seis o bien si al menos tres de los participantes son empresas, sea cual sea el nmero total de
participantes. Establece el mecanismo adecuado que permita consultar si un proyecto coordinado
es conflictivo o no.
e) Disea un mtodo con un parmetro que permita listar todos los proyectos de investigacin
orientada que sean de un determinado tipo de los tres posibles. Por cada proyecto, hay que mostrar
su cdigo, ttulo, presupuesto, participante responsable/coordinador, investigador principal (o
representante) y, en el caso de los coordinados, la identificacin de todos los grupos/empresas
participantes. Aade lo que sea necesario. Sita adecuadamente este mtodo. Es heredable?
18. La empresa de alquiler de vehculos Los mas guays desea incorporar un sistema de gestin del
conocimiento para incrementar sus beneficios. De momento quiere mantener informacin sobre sus
vehculos en sus tres categoras: turismos (de ciudad, familiar, para grupos), furgonetas (con o sin
conductor) y autocares (grande, minibs). La empresa tiene muchas sucursales, la mayora son de
ciudad y algunas son especiales (por ejemplo, las ubicadas en aeropuertos). Tambin dispone de muchos
empleados: directores de sucursal, personal administrativo, conductores, ... Dentro de la informacin a
mantener es importante incluir la referida a los clientes, ya sea habituales o espordicos, para realizar
campaas de promocin, estudios de mercado, ... Se pide:
a) Propn una representacin estructurada del conocimiento adecuada para este dominio. Asigna
dos o tres atributos a cada frame principal y al menos uno a los dems.
b) Caracteriza las siguientes relaciones: entre empleado y sucursal donde trabaja, entre vehculo y
sucursal al que pertenece, entre vehculo y sucursal donde est fsicamente, entre cliente y vehculo
que alquila. Un vehculo no es alquilable si su estado es en-taller. Aade lo necesario para que el
sistema controle esta incidencia.
c) Cuando se alquila una furgoneta con conductor, debe expresarse esta informacin mediante una
relacin, caracterzala. cmo caracterizaras la relacin entre cliente que la alquila y el conductor?
d) Los vehculos son especiales si pertenecen a sucursales especiales. Establece el mecanismo adecuado para que el sistema pueda inferirlo.
e) Una sucursal esta en-crisis si el 40 % o ms de sus coches estn en-taller. Establece el mecanismo
adecuado para consultar el estado de una sucursal.
70
19. Una compaa de telefona dispone de una cartera de productos y de diferentes modalidades de contrato para ofertrselas a sus clientes. En concreto los productos que ofrece son telefona_fija, telefona_mvil, ADSL (con diferentes anchos de banda) e internet_mvil y las modalidades de contrato
son: slo_consumo, mnimo+ %consumo y tarifa_plana (todo el da, slo en una franja horaria determinada y hay varias franjas horarias preestablecidas). Los clientes de la empresa en cuestin son
particulares, autnomos y empresas y pueden contratar ms de un producto y con modalidades de
contrato distintas.
a) Representa una red de frames que describa los conceptos ms relevantes que maneja la empresa.
Aade 3 slots a los frames ms destacados.
b) Define completamente las relaciones que creas necesarias para que se pueda saber qu modalidades de contrato tienen los clientes, qu productos han contratado y qu modalidad de contrato
tiene cada uno de los productos contratados. Es necesario que un cliente tenga contratada telefona_mvil para que pueda contratar internet_mvil. Fijado un cliente, un producto contratado
por l no puede tener asociada ms de una modalidad de contrato activa (puede tener otras pero
ya inactivas). Un cliente no puede cambiar la modalidad de contrato de un producto si no ha
cumplido el periodo mnimo de permanencia de su modalidad de contrato anterior. Si se dan
las condiciones para cambiar, entonces la modalidad de contrato anterior pasa a estar inactiva.
Aade todo lo necesario para que se controle la satisfaccin de todas las restricciones anteriores.
Para simplificar el problema podis suponer que pese a que varios clientes pueden tener contratado el mismo producto, a efectos prcticos podemos considerarlos como productos concretos
diferentes, es decir, como instancias distintas del mismo producto.
c) Cuando ms de un 80 % de los clientes que tienen contratado el mismo tipo de producto comparten
una modalidad de contrato dada, la empresa considera que esa modalidad tiene la categora de
estrella. Define lo necesario para averiguar si una modalidad es estrella para un producto y, en
caso afirmativo, se listen todos los clientes que la tengan contratada.
d) El grado de satisfaccin de un cliente es una funcin que depende del nmero de cambios de
modalidad de contrato y del tiempo de permanencia en cada uno de ellos. Describe, sin necesidad
de implementar, el procedimiento que usaras para conocer el grado de satisfaccin de un cliente
tiene sentido plantear la posibilidad de que una modalidad de contrato herede el grado de
satisfaccin de los clientes que tengan esa modalidad de contrato?
20. Dado el inters que ha suscitado el mercado inmobiliario, el ministerio de hacienda ha decidido crear un
sistema inteligente que le permita mantenerlo controlado. Para ello necesita representar el conocimiento
que interviene. El mercado inmobiliario est compuesto por usuarios que tienen diferentes roles, nos
encontramos con vendedores (que pueden ser promotoras, agencias inmobiliarias, particulares) y con
compradores (que pueden ser agencias inmobiliarias, particulares, empresas).
Los inmuebles que se pueden comprar y vender pueden ser viviendas (pisos, casas unifamiliares),
locales, edificios, naves industriales, etc. Para la adquisicin de estos inmuebles por lo general hay que
pedir crditos hipotecarios a inters fijo o variable. Estos son concedidos por entidades financieras,
tanto bancos como cajas de ahorros. Se pide:
a) Propn una representacin estructurada del conocimiento adecuada para este dominio. Asigna
dos o tres atributos a cada frame principal y al menos uno a los dems. Define completamente los
slots precio de venta en inmueble e inters en crdito hipotecario Hace falta un slot diferente
para los diferentes tipos de crditos?
b) Caracteriza la relacin solicita entre comprador y crdito hipotecario, la relacin estudia entre
entidad financiera y crdito hipotecario, la relacin concede entre entidad financiera y crdito
71
hipotecario y la relacin hipotecado entre inmueble y crdito hipotecario. Aade y define lo
necesario para que no se pueda conceder un crdito que suponga ms del 80 % del valor del
inmueble que se va a adquirir (explica todas las decisiones que tomes).
c) Cuando se adquiere un inmueble se ha de comprobar que ste no tenga alguna hipoteca pendiente.
Aade y define lo necesario para que no se pueda adquirir un inmueble si su poseedor tiene
concedido un crdito que hipoteca el inmueble.
d) Define el slot potentado que sea cierto cuando un particular posee inmuebles no hipotecados
con un valor mayor a 3 millones de euros.
e) Un comprador se puede desgravar parte de lo que paga de hipoteca si sta supone ms de un
50 % del valor de compra de la vivienda. Define un mtodo que permita a hacienda saber qu
compradores pueden tener desgravacin, la entidad que ha concedido la hipoteca y la direccin
del inmueble. Dnde se ubica el mtodo? Es heredable?
72
1. Para los siguientes problemas indica si son problemas de sntesis o de anlisis justificando tu respuesta:
Determinar la mejor ubicacin para un hospital dentro de una ciudad dadas un conjunto de
posibles ubicaciones y sus caractersticas.
Determinar la mejor forma de asignar los horarios del personal de ambulancias de una red de
hospitales para que se puedan atender un mnimo de urgencias optimizando los desplazamientos
de las ambulancias.
Determinar para una lista de operaciones quirrgicas a realizar y una lista de mdicos y personal
de quirfano, en qu orden se han de realizar las operaciones y qu personal ha de intervenir,
dadas las restricciones de horarios de quirfanos y la urgencia de las intervenciones.
2. El departamento de planificacin urbana de la ciudad de Urbpolis ha decidido utilizar un SBC para
la planificacin de los diferentes elementos de la ciudad.
Para este departamento la ciudad est compuesta por unidades urbanas de tres tipos distintos. El
primer tipo son las unidades comerciales que pueden corresponder a comercios mayoristas o comercios
minoristas. El segundo tipo son las unidades de servicio al ciudadano tales como colegios pblicos,
bibliotecas, zonas verdes, polideportivos, hospitales, centros de asistencia primaria, plazas pblicas,
farmacias y oficinas de servicios pblicos. Finalmente, el tercer tipo son las unidades residenciales que
pueden corresponder a viviendas unifamiliares, edificios de pisos y manzanas de viviendas.
Las unidades urbanas se pueden ubicar en espacios. Hay espacios de dos tipos. El primero son los
solares que pueden clasificarse en bloques (capacidad para un solo edificio), manzanas (capacidad para
varios edificios) y grandes reas (capacidad para grandes instalaciones). El segundo tipo son los locales.
El departamento de planificacin tiene la informacin de todos los espacios que existen en la ciudad.
Tambin dispone de la informacin de qu espacios estn vacantes en la actualidad y qu unidades
urbanas se han asignado a los espacios ya ocupados. A cada espacio solo se le puede asociar una unidad
urbana.
Las unidades urbanas se encuentran dentro de barrios, que es la divisin ms fina en la que el ayuntamiento agrupa las zonas de la ciudad. El barrio tiene informacin sobre su poblacin, incluyendo su
distribucin por edades (nios, adultos, ancianos). Los barrios a su vez estn agrupados en distritos.
Otro elemento de la ciudad son las vas. Estas se pueden clasificar en grandes vas, avenidas, vas
fluidas y vas comunes. Todo espacio tiene una serie de vas con las que est relacionado (aquellas
que lo bordean y/o cruzan). Cada va tiene informacin de la cantidad de coches por minuto que la
recorren. Estas vas estarn relacionadas tambin con barrios y distritos.
A) Preguntas de Ontologas/Frames
a) Propn una representacin estructurada del dominio descrito e identifica los atributos ms relevantes.
b) Define todas las relaciones de usuario que consideres necesarias y, en particular, especifica ubicado_en entre unidad urbana y espacio, situado_en entre espacio y barrio, relacionado_con
entre espacio y va.
c) Propn e implementa un mecanismo adecuado para obtener el total de la poblacin infantil en la
ciudad.
d) Define todo lo necesario para determinar a qu distrito pertenece una unidad urbana y a qu
barrios pertenece una va Es posible asociar nmeros de distrito a barrios y vas usando el
mecanismo de herencia? Justifica tu respuesta.
73
74
75
urbanas de ese tipo ya existentes, las diferentes restricciones de ubicacin que impone el propio
departamento y los recursos de que se disponen.
La ciudad determina que debe haber al menos un centro de atencin primaria por barrio, pero
no ms de diez por distrito. Los centros de atencin primaria han de estar lo ms lejos posible
entre si dentro del barrio. Debe haber al menos dos farmacias cercanas a cada centro de atencin
primaria, pero las farmacias del barrio deben estar a una distancia media entre ellas. Debe haber
al menos un hospital por distrito y deben estar a distancia media de los centros de atencin
primaria.
Debe haber un colegio en un barrio por cada 300 nios, pero ste debe estar a una distancia media
de otros colegios del barrio y debe estar cerca de al menos dos bibliotecas y al menos tres plazas
en el barrio. Debe haber a distancia media del colegio al menos una zona verde y un polideportivo
en el barrio.
El barrio debe tener al menos una zona verde y un polideportivo pero las reas verdes y polideportivos de cada barrio deben estar a distancia lejana ente s. Cada barrio debe tener al menos 5
plazas que deben estar a distancia media entre s pero no ms de 30 por distrito. No debe haber
grandes vas cerca de colegios, zonas verdes o polideportivos.
Las oficinas de atencin ciudadana deben estar cerca entre si en el barrio y no debe haber ms
de 5 por barrio. Debe haber como mnimo una biblioteca por barrio y debe estar cerca de alguna
oficina de atencin ciudadana.
Este problema se puede plantear como un problema de satisfaccin de restricciones. Explica cmo
se puede resolver con este enfoque. Identifica las variables adecuadas, sus dominios, los diferentes
tipos de restricciones entre variables que se necesitan y la estructura de la red de restricciones.
Justifica tus respuestas.
3. El siguiente problema es un problema de anlisis:
Una labor de los equipos mdicos de urgencias en situaciones de emergencia es determinar la prioridad
con la que se ha de tratar a los pacientes. Este proceso es denominado triage. Los mdicos estn
entrenados para analizar el estado del paciente y clasificarlo en tres grupos: Situacin vital, grave
pero no vital y heridas menores. Para realizar esta clasificacin se utilizan diferentes criterios, pero
podramos reducirlos a tres: cardiovasculares, traumatismos y respiratorios. Cada uno de estos incluye
toda una serie de sintomas, como por ejemplo, paro cardaco, arritmias, tensin arterial, ... para los
cardiovasculares, hemorragias, heridas abiertas, cortes, fracturas, ... para traumatismos, obstruccin
de vas, perforacin pulmonar, colapso pulmonar, ritmo respiratorio, ... para respiratorios
Explica cmo lo resolveras usando clasificacin heurstica. Da algn ejemplo de regla para cada una
de las fases de esta metodologa.
4. La FIB desea construir un sistema de recomendacin capaz de proponer un conjunto de asignaturas
de las que matricularse que se ajuste a las preferencias del alumno, su historial acadmico y sus
restricciones (horarias, de perfil profesional, de dedicacin, ...)
La FIB dispone para cada alumno de su expediente acadmico, que guarda cada convocatoria de
examen a la que se ha presentado, con la asignatura, el cuatrimestre, el horario en el que se realiz y
su calificacin.
Para cada asignatura tiene su nmero de crditos ECTS, su distribucin segn teora, problemas y
laboratorio y la carga de horas total de trabajo por cada uno de estos conceptos. Tambin se tiene si
es obligatoria, optativa o de libre eleccin, si es de proyecto, el curso en el que esta ubicada en el plan
de estudios, sus prerrequistos, los temas en los que puede ubicarse, si tiene horarios de maana y tarde
o solo de maana o de tarde. Como informacin adicional se tiene tambin el nmero de personas
matriculadas el cuatrimestre anterior y el porcentaje de aprobados.
Los temas estn clasificados segn si son generales (programacin, ingeniera de software, bases de
datos, redes, arquitectura de computadores, matemticas, fsica, ... ), especializados (lenguajes de
programacin, inteligencia artificial, clculo numrico, grficos, investigacin operativa, tratamiento de
datos, geometra computacional, lgica, ...) o no informticos (ldicas, culturales, divulgacin cientfica,
76
77
El esquema del guin lo basaremos en secuencias ordenadas de estados por los que pasar cada personaje. Estos estados podrn ser emocionales (triste, alegre, enamorado, enfadado, ...) o fsicos (peligro,
hambre, herido, muerto, viaje). Esta secuencia de estados la determinaremos a partir del tipo de serie
que queramos crear y las caractersticas de los personajes principales que intervienen.
El esquema propiamente dicho del guin ser una secuencia ordenada de escenas. Estas escenas las
clasificaremos en dramticas (por ejemplo un rescate), humorsticas (un personaje le gasta una broma
a otro), accin (una pelea), cotidianas (una familia desayunando), ... Una escena tendr una duracin
asociada.
Cada escena estar asociada al conjunto de estados necesarios para aplicarla. Una escena tambin
tendr asociados unos roles que indican qu personajes han de intervenir en la escena, los roles pueden
ser por ejemplo iniciador, participante, receptor, ... Cada personaje estar asociado a una escena a
travs de un rol.
El objetivo del SBC es crear el guin un episodio con una duracin lo mas cercana posible a una dada,
pero siempre inferior. Como datos de entrada nos indicarn qu personajes principales aparecen, cuales
son sus caractersticas, la temtica de la serie y detalles sobre la ambientacin, como por ejemplo la
poca, el lugar, ... El episodio se compondr de una serie de escenas y los personajes que intervienen
en cada una de ellas. Todos los personajes principales tendrn que aparecer en algn momento y
tendremos que determinar qu personajes secundarios hacen falta, con la restriccin de que deberemos
aadir el mnimo posible ya que los actores son caros.
a) Identifica todos los conceptos que forman parte del problema. Representa grficamente estos
conceptos mediante una red de frames incluyendo los atributos mas relevantes y las relaciones
tanto taxonmicas como no taxonmicas que creas que son necesarias.
b) Hemos decidido que el primer subproblema a resolver es el determinar los estados por los que
pasar cada personaje. Para hacer mas sencillo el problema hemos escogido un conjunto finito
de secuencias de estados tpicas y una serie de caractersticas propias que las describen. Lo que
queremos es asignar una de ellas a cada personaje principal dependiendo de la informacin de
entrada del problema. Estas secuencias se podra refinar con algunas caractersticas especficas
de los personajes o de la serie.
Por ejemplo, podramos definir la secuencia torbellino emocional genrico que correspondera a
la secuencia de estados (triste, enamorado, alegre, engaado, (triste o vengativo)) que podramos
describir por las caractersticas (soporta estrs = si, fortaleza emocional = si, fortaleza fsica =
indefinida, aspecto fsico = normal), donde se poda definir la eleccin sobre el ltimo estado
dependiendo por ejemplo de si el personaje es bueno o malo.
Este planteamiento encaja con el mtodo de clasificacin heurstica. Explica lo que se debera
hacer en cada una de las fases de esta metodologa para resolver el problema tal como se ha
explicado. Pon ejemplos sencillos de reglas para cada fase.
c) El segundo subproblema consiste en construir la secuencia de escenas que encajen lo mejor posible
con los estados por los que han de pasar los personajes principales (los estados que no se puedan
encajar deberan corresponder a personajes secundarios) y determinar los personajes necesarios
para cada escena. ste es un problema de sntesis que podramos resolver mediante proponer
y aplicar. Define un conjunto de operadores que permitan resolver el problema, indicando que
haran, las restricciones globales y especficas que deberan tenerse en cuenta para aplicarse y los
criterios de evaluacin que determinan la bondad de cada operador.
6. Una compaa area desea organizar las asignaciones de puestos que han de desempear sus empleados
de manera que se puedan cubrir todos los puestos que necesitan para atender los vuelos de la compaa
que llegan y salen de un aeropuerto concreto.
El personal de que dispone la compaa se puede clasificar en personal de vuelo y personal de tierra.
Para el personal de vuelo hay puestos de piloto y auxiliar de vuelo. Para el personal de tierra hay
puestos en facturacin de equipajes, venta de billetes, atencin al cliente, embarque y reclamacin de
equipajes. Cualquier persona del personal de tierra puede ocupar cualquiera de los puestos posibles.
78
79
La empresa dispone de diferentes medios de traslado (camiones grandes, furgonetas, contenedores
de tren) y personal para realizar el traslado (empaquetadores, cargadores, desmontadores, personal
especializado). Un traslado se compone de un conjunto de medios de traslado y el personal necesario.
A) Preguntas de Frames
a) Propn una representacin estructurada del dominio descrito e identifica los atributos ms relevantes. Define completamente el atributo empaquetable? en objeto, indica si las subclases
tienen alguna particularidad respecto a este slot.
b) Define las relaciones formado_por entre ubicaciones y habitculos, la relacin contiene entre
habitculo y objeto y la relacin traslada entre personal y ubicacin.
c) Define el slot gra? en ubicacin que sea cierto si hay un objeto no empaquetable que tiene una
dimensin mayor de 3 metros o un peso mayor a 100 Kg.
d) Implementa un mtodo que calcule el volumen total de todos los objetos empaquetables en una
ubicacin. Donde habra que ubicar este mtodo?
e) Podramos definir el slot empaquetable? en habitculo de manera que utilizara herencia para
que fuera cierto si todos los objetos que hay en el habitculo son empaquetables? Si no se puede,
define lo que sea necesario para tener ese slot con la semntica indicada.
B) Preguntas de SBCs
a) Para poder obtener la recomendacin del traslado el usuario indica tambin cual es la distancia
al lugar del traslado, cual es el tiempo mximo de carga y descarga de los objetos a trasladar (en
horas) y el precio mximo que quiere pagar por el traslado.
A partir de esta informacin y de las caractersticas de los objetos que hay que trasladar, el
tipo de ubicacin y las caractersticas de los accesos se quiere obtener una solucin que indique
si el traslado debe hacerse mediante camiones grandes y/o furgonetas y cuntas hacen falta de
cada tipo, si se ha de utilizar tambin el tren y el tipo de personal que es necesario y el nmero
aproximado de personas de cada tipo.
Se ha determinado que este es un problema de anlisis y para solucionarlo se han de abstraer
ciertas caractersticas de los datos del problema. Hay caractersticas que son sencillas de abstraer,
como por ejemplo el tipo de traslado: local (menos de 10 Km), regional (menos de 100 Km) o
larga distancia; o el presupuesto: bajo (menos de 1000 euros), medio (menos de 3000 euros) o
alto; o la duracin del traslado: corta (menos de 5 horas), media (menos de 10 horas), larga.
Otras requieren cierto razonamiento, como la complejidad del traslado: sencilla en la que la
mayor parte de los objetos se pueden empaquetar, no hay que desmontar muchos muebles y
no hay objetos voluminosos y frgiles, normal en la que hay que hacer bastante desmontaje,
hay algunos objetos voluminosos pero no se necesitan gras y hay algunos objetos frgiles y
difcil en la que se necesitan gras y hay bastantes objetos frgiles; el volumen del traslado:
pequeo si el nmero de habitculos es inferior a 5 y no hay objetos voluminosos o muebles
no desmontables, medio si es una casa unifamiliar o una planta de oficinas y hay pocos objetos
no desmontables, grande si es una planta de oficinas y hay bastantes objetos no desmontables,
extremo si es un edificio de oficinas o hay una gran cantidad de objetos no desmontables;
la accesibilidad del traslado: accesible si se pueden ubicar los medios de traslado cerca de la
ubicacin y hay ascensor, medianamente accesible si hay ascensor, pero no caben todos los
objetos voluminosos, poco accesible si no se pueden ubicar los medios de traslado cerca de la
ubicacin y el ascensor no se puede utilizar para la mayor parte de los objetos voluminosos.
A partir de estas caractersticas podemos decidir qu tipo de medios de traslado necesitamos y
los tipos de personal, por ejemplo para un traslado de volumen grande harn falta camiones, si el
traslado es de larga distancia y de volumen grande har falta usar el tren, si la ubicacin es poco
accesible es mejor usar furgonetas, ... Si la complejidad del traslado es difcil y es de volumen
grande harn falta empaquetadores, cargadores y desmontadores, si el volumen es pequeo con
cargadores podra haber suficiente, ...
80
81
El problema consiste en analizar el dominio propuesto (decidir las necesidades informticas de una
empresa) y reflexionar en cmo se debera construir un SBC que fuera capaz de evaluar la informacin
que viene de la empresa y aconsejar la solucin informtica que necesitan a grandes rasgos, sin entrar
en detalles concretos.
Informacin que se podra tener en cuenta sobre una empresa es por ejemplo: actividad, necesidad de
relacionarse con otras empresas, tamao de la empresa, necesidad de comunicacin interna, comparticin de recursos, presupuesto del que disponen, proyeccin de futuro. Todas estas caractersticas y
restricciones apuntarn a soluciones informticas parciales que deberan coordinarse: nmero de ordenadores, potencia de estos, necesidad de servidor de ficheros, tipo de red, comunicaciones externas.
Por ejemplo, si al sistema se le presenta una empresa con un tamao medio (unos 50 empleados)
que se dedica a la venta de material de construccin que tiene un presupuesto razonable, con una
previsin de crecimiento grande, que deseara mantener control de sus actividades (stock, ventas,
proveedores, clientes), que desea tambin una comunicacin gil con sus proveedores que tambin estn
informatizados, pero que las tareas burocrticas (cartas, facturas, pedidos a proveedores, redaccin de
contratos) las desarrollan pocas personas ya que la mayora de su plantilla son representantes, se le
podra presentar una solucin basada en un ordenador central para todo el control del negocio con
una capacidad de almacenamiento grande al que se pudieran conectar terminales y un nmero no
muy grande de ordenadores de sobremesa para las labores burocrticas con impresoras, un nmero de
ordenadores porttiles para los representantes con capacidad para conectarse a la central y un sistema
de comunicaciones que permita conectarse a los representantes y realizar pedidos electrnicos a los
proveedores. La necesidad de comunicaciones internas no existira. La posibilidad de ampliacin de la
capacidad de la mquina central y de comunicacin externa debera asegurarse para no comprometer
un probable crecimiento del negocio.
Una vez reflexionado sobre el problema planteado hay que responder a estas preguntas, justificando
las decisiones que se toman:
a) Identifica qu conceptos forman los datos de entrada del problema. Representa grficamente estos
conceptos mediante una red de frames incluyendo los atributos ms relevantes y las relaciones,
tanto las taxonmicas como las no taxonmicas que creas que son necesarias.
b) Identifica los conceptos que forman la solucin del problema. Representa grficamente estos conceptos mediante una red de frames y las relaciones, tanto las taxonmicas, como las no taxonmicas, que creas que son necesarias.
c) Cmo descompondras el problema en subproblemas? Identifica y especifica los subproblemas a
resolver y cmo se encadenaran para construir la solucin.
d) Indica para cada subproblema que has identificado si es un problema de anlisis o de sntesis.
Justifcalo.
e) Qu tipo de razonamiento te parece ms adecuado para cada subproblema? Justifcalo.
10. Despus de observar los problemas de descoordinacin de la ayuda humanitaria en desastres como los
terremotos de Haiti o Chile, la Oficina Para la Coordinacin de Asuntos Humanitarios de la ONU
ha decidido crear un SBC que, segn el tipo de catstrofe, ayude a tomar decisiones sobre el tipo de
ayuda a enviar en cada caso.
El sistema se limita a la resolucin puntual de las emergencias ocurridas por desastres naturales. Para
poder decidir el tipo de ayuda que se necesita en cada caso, el sistema ha de tener en cuenta:
el tipo de desastre (huracn, terremoto, inundacin, erupcin...);
la magnitud del desastre (cada desastre tiene su propia escala de magnitudes.);
el nmero estimado de personas afectadas por el desastre que necesiten ayuda;
el nmero estimado de heridos;
el lugar donde ha ocurrido el desastre (isla, costa, interior);
82
11. El elegir una tarifa de telefona mvil es una tarea realmente complicada dado el gran nmero de diferentes tarifas que los operadores de telefona ofrecen. Para facilitarlo el portal SuperComparador.com
quiere desarrollar un sistema que permita recomendar la tarifa ms adecuada a cada usuario de las
disponibles en el mercado.
Para desarrollar el sistema el portal hace rellenar al usuario un formulario sobre su uso mensual del
mvil, como por ejemplo cuantas llamadas tienen como destinatario a amigos y familiares, cuantas
tienen como destinatario a contactos del trabajo y cual es ms o menos la duracin de cada tipo,
cuantas llamadas hace en horario de maana, tarde y noche, cuantas llamadas hace en das laborables
83
y cuantas en fin de semana, si usa internet en el movil, y en caso positivo el nmero de GB de
datos que en media suele consumir al mes, cuantos mensajes SMS/MMS enva, a cuantos operadores
diferentes son sus llamadas, cuantas tarifas diferentes de mvil ha tenido en los ltimos tres aos, las
caractersticas de cada una de esas tarifas y a qu operador pertenecan, ...
A partir de esta informacin se puede elaborar un perfil de las caractersticas del usuario basndonos
en un conjunto de atributos: perfil particular (bajo, medio, alto), perfil laboral (bajo, medio, alto),
uso de telfono (bajo, moderado, alto, intensivo), flexibilidad horaria (baja, media, alta), destino de
llamadas (al operador, a varios operadores), uso de mensajera (bajo, medio, alto), uso de intenet (nulo,
bajo, medio, intensivo), fidelidad (alta, baja).
Las diferentes tarifas de mvil tambin se pueden describir mediante una serie de caractersticas que
nos permitirn identificar mejor que conjunto de tarifas son las ms adecuadas para el usuario. Una
tarifa pertenece a un operador de telefona y puede ser descrita por su cuota mensual (ninguna, baja,
media, alta), la exigencia de un consumo mnimo (no, bajo, medio, alto), el coste de establecimiento
de llamada (ninguno, bajo, medio, alto), el coste de la llamada por minuto al operador (ninguno,
bajo, medio, alto), el coste por minuto a otros operadores (ninguno, bajo, medio, alto), descuento por
volumen de llamadas (si, no), minutos de llamada incluidos en la cuota mensual (medio, alto, muy
alto), flexibilidad de horario con coste reducido (ninguna, baja, media, alta), velocidad de internet (no
tiene, 2G, 3G, 4G), los GB de datos incluidos en la tarifa (ninguno, menos de 2 GB, entre 3 y 4 GB,
ms de 4 GB), coste de los mensajes (bajo, medio, alto), exigencia de permanencia (alta, media, baja).
A partir del perfil del usuario podemos asociar los valores de las caractersticas de la tarifa ms
adecuada, por ejemplo, si el perfil particular del usuario es alto y hace un uso alto, puede convenirle
una tarifa que tenga una exigencia de consumo mnimo alta y que tenga una cuota mensual media.
Si el perfil particular es alto, el uso del telfono es bajo y con una flexibilidad horaria baja puede
convenirle una tarifa con ninguna cuota mensual y una exigencia de consumo baja. Si el uso del
telfono es intensivo necesitar una flexibilidad de horario alta y con los minutos de llamada incluidos
en la tarifa altos o muy altos o bien con un descuento por volumen de llamadas. Si el perfil laboral es
alto le conviene una tarifa con un coste de llamada a otros operadores bajo o medio. Si la fidelidad del
usuario es alta y su uso es bajo podr tener una tarifa con una cuota mensual baja y con una exigencia
de permanencia alta.
Una vez determinados los valores de las caractersticas de la tarifa ms adecuada se puede identificar
la tarifa concreta a partir de los valores concretos de consumo del usuario y los precios y caractersticas
especficas de las tarifas ofrecidas por los operadores de telefona (que tiene el portal en su base de
datos).
a) Disea la ontologa del dominio descrito, incluyendo todos los conceptos que aparecen en la
descripcin e identificando los atributos ms relevantes. Lista que conceptos forman parte de los
datos de entrada del problema y que conceptos forman parte de la solucin. (Nota: tened en
cuenta que la ontologa puede necesitar modificaciones para adaptarla al apartado siguiente).
b) El problema descrito es un problema de anlisis. Explica cmo lo resolveras usando clasificacin
heurstica, usando los conceptos de la ontologa desarrollada en el apartado anterior. Da al menos
3 ejemplos de reglas para cada una de las fases de esta metodologa. Inventa algun ejemplo
concreto de tarifa si te hace falta.
c) Las caractersticas que se utilizan para caracterizar a los usuarios y los tipos de tarifas no son
independientes entre si. Por ejemplo: un uso alto de mensajeria suele implicar la recomendacin de
una tarifa con baja velocidad de internet y viceversa, un uso intensivo de internet suele implicar la
recomendacion de tarifas con altas velocidades de internet y con ms de 2 GB de datos incluidos,
una flexibilidad horaria alta implica la recomendacion de tarifas con una flexibilidad de horario
de coste reducido media o alta, etc.
Define el problema de asociacin heurstica como una red bayesiana expresando en ella al menos
las relaciones indicadas en el enunciado, en este apartado y alguna ms, de forma que todas las
caractersticas abstractas del problema que hayas definido en el apartado anterior tengan algun
tipo de influencia en la solucin. Separa bien en el diagrama que variables describen caractersticas
84
12. Muchos alcaldes estan deseosos de satisfacer a sus ciudadanos instalando un parque de atracciones en
su ciudad para que puedan disfrutar de ellos en sus momentos de ocio. Dada esta necesidad nos hemos
decidido a hacer un sistema capaz de disear el parque mas adecuado para una ciudad a partir de sus
caractersticas y el pblico potencial que puede atraer.
De esta manera, nos podemos fijar en diferentes informaciones que nos pueden indicar qu tipo de
atracciones, qu tamao debera tener el parque, qu tipo de ubicacin es ms adecuada en la ciudad
(si es que hay un sitio adecuado). Hay que tener en cuenta que el tipo de atracciones que podemos
incluir depender mucho del pblico potencial de la ciudad, por ejemplo puede influir la distribucin
por edades, el nmero de parejas con hijos pequeos, los otros equipamientos que pueda haber en
la ciudad. Tambin puede influir el nivel de turismo de la ciudad, la cercana de otras poblaciones
grandes, ...
Analizando esta informacin nos podemos hacer una idea de cuantas atracciones hacen falta, de que
tipo (infantiles, juveniles, adultos, todos los pblicos, ..) y qu otros equipamientos nos hacen falta
(tiendas de souvenirs, de palomitas, de perritos, ...)
Otra cosa interesante (en este caso para nosotros) es una vez decididas que atracciones son interesantes
en el parque, saber cmo ponerlas para maximizar el nmero de atracciones que visita la gente. Por
ejemplo, si la montaa rusa est la primera y la gente se sube primero a ella posiblemente se le quiten
las ganas de subir a otra atraccin o si las atracciones infantiles estn muy dispersas solo se subirn a
las primeras, o si el tiempo que se pasa en las primeras atracciones es muy corto la gente se ir antes
porque ya ha subido en muchas, ...
A partir de tener en cuenta estas restricciones podremos tener una idea de cmo colocar las diferentes
atracciones y otros equipamientos en el parque a la hora de construirlo.
Una vez reflexionado sobre el problema planteado hay que responder a estas preguntas, justificando
las decisiones que se toman:
a) Identifica qu conceptos forman los datos de entrada del problema. Representa grficamente estos
conceptos mediante una red de frames incluyendo los atributos ms relevantes y las relaciones,
tanto las taxonmicas como las no taxonmicas que creas que son necesarias.
b) Identifica los conceptos que forman la solucin del problema. Representa grficamente estos conceptos mediante una red de frames y las relaciones, tanto las taxonmicas, como las no taxonmicas, que creas que son necesarias.
c) Cmo descompondras el problema en subproblemas? Identifica y especifica los subproblemas a
resolver y cmo se encadenaran para construir la solucin.
d) Indica para cada subproblema que has identificado si es un problema de anlisis o de sntesis.
Justifcalo.
e) Qu tipo de razonamiento te parece ms adecuado para cada subproblema? Justifcalo.
13. La cadena de supermercados HIPERFUR nos pide que diseemos un SBC orientado a la creacin de
folletos de ofertas de productos personalizados para cada cliente. Cada folleto consta de 8 pginas
y en cada pgina se pueden colocar 9 ofertas diferentes, que provienen de una base de ofertas a la
que tendr acceso el SBC. Toda oferta tiene una fecha de inicio y de fin, y un producto o productos
asociados. Hay dos tipos de ofertas:
descuentos, que tienen entre otros datos el porcentaje de descuento, e informacin sobre si son
descuentos directos (el cliente paga el precio rebajado) o indirectos (el cliente recibe un vale de
compra).
promociones, que pueden ser packs de productos diferentes (por ejemplo, un queso y un jamn)
u ofertas al llevarse varias unidades del mismo producto (2x1, 3x2, 4x3).
85
Los productos pueden ser de diferente tipologia: alimentacin (leche, huevos, pescado, carne, bebidas...), belleza (cremas, maquillaje, after-shave...), menaje (sartenes, ollas, vasos, cuberteria...), limpieza del hogar (jabon de ropa, lavavajillas, quitamanchas, mocho, escoba...). Adems los productos
pueden pertenecer a una marca blanca (precio muy bajo), a una marca generalista (precio medio) o
a una marca premium (precios muy altos). Este sistema obtendr la informacin de los hbitos de
compra de un cliente (una lista de las ofertas y los productos individuales que ha comprado en los
ltimos 6 meses donde, para cada oferta y para cada producto individual, se dice cuantas unidades
ha comprado. Adems los clientes pueden (a travs de la pgina web) aadir una lista de productos
preferidos , y/o una lista de restricciones que se pueden aplicar a un producto concreto (ej: no quiero
el jabn "Pixan plus") o a un subtipo de producto (ej: no me gustan las leches de soja). Se quiere
construir este SBC de manera que, en base a toda la informacin disponible sobre el cliente, seleccione
un conjunto de ofertas adecuadas para ese tipo de cliente y las asigne a alguna de las 8 pginas del
folleto. El director de marketing de HIPERFUR nos recomienda que incluyamos las siguientes caractersticas abstractas como base de la seleccin: el nivel de gasto mensual (alto, medio, bajo) que
servir para calcular el importe total de los productos que se coloquen en el folleto; la calidad de
los productos (mayoria premium, mayoria normal, mayoria marca blanca) que servir para seleccionar, dentro de un (sub)tipo de producto, el producto adecuado al patrn de compra del cliente; la
cantidad_alimentacin (exagerada, mucha, normal, poca, limitada), que servir para decidir que
porcentaje del folleto se dedica a productos alimenticios (y en los casos extremos -exagerada, limitadase colocarn preferentemente productos de alto valor nutricional);la cantidad_belleza (narcicista,
normal, dejado/a) que servir para decidir que porcentaje del folleto se dedica a productos de belleza;
la cantidad_menaje (exagerado/a, normal, minimalista) que servir para decidir que porcentaje del
folleto se dedica a productos de menaje; y la cantidad_limpieza (obseso/a, normal, sucio/a) que
servir para decidir que porcentaje del folleto se dedica a productos de limpieza.
a) Disea la ontologa del dominio descrito, incluyendo todos los conceptos que aparecen en la
descripcin e identificando los atributos ms relevantes. Lista qu conceptos forman parte de los
datos de entrada del problema y qu conceptos forman parte de la solucin. (Nota: tened en
cuenta que la ontologa puede necesitar modificaciones para adaptarla al apartado siguiente).
b) El problema descrito es un problema de anlisis. Explica cmo lo resolveras usando clasificacin
heurstica, usando los conceptos de la ontologa desarrollada en el apartado anterior. Da al menos
3 ejemplos de reglas para cada una de las fases de esta metodologa.
c) Las caractersticas que se utilizan para determinar las ofertas a incluir en el folleto no son independientes entre si. Por ejemplo: la cantidad de productos de belleza suele ser inversamente
proporcional a la cantidad de alimentacin (cuanto ms cuida su aspecto, menos come), la calidad
esta influida por el nivel de gasto mensual y las cantidades de cada tipo de producto. El tipo de
ofertas a incluir viene influenciado por el nivel de gasto y la cantidad (por ejemplo, en caso de
niveles de gasto bajos o cantidades bajas suele ser mejor incluir descuentos, mientras que para
clientes que compran grandes cantidades o con niveles de gasto elevado lo mejor es recomendar
promociones multi-producto, etc).
Define el problema de asociacin heurstica como una red bayesiana expresando en ella al menos
las relaciones indicadas y alguna ms. Da un ejemplo de tabla de probabilidad de algn nodo,
inventndote las probabilidades, pero expresando como influyen los valores de los nodos padre en
las probabilidades de los valores de los nodos hijo.
14. La empresa de pirotcnica FantasIA quiere disear un sistema inteligente de gestin de pedidos de
material a travs de su pgina web que ayude al cliente a escoger el material pirotcnico que desea
recomendndole el ms adecuado segn sus preferencias, el evento y el lugar donde se celebrar.
Coincidiendo con las fiestas de San Juan de este ao quiere probar un primer prototipo del sistema y
ver si gusta a sus clientes.
Los usuarios de este sistema podran ser empresas o ayuntamientos. De las empresas podemos obtener
informacin sobre si es una empresa pequea, mediana o grande, y de los ayuntamiento podemos saber
si se trata de una metrpoli (una ciudad grande), una ciudad pequea, una villa o un pueblo (cuanto
ms grande es la empresa o el ayuntamiento ms puede invertir en material pirotcnico). Tanto en
86
87
Es importante aclarar que los niveles de peligro antes mencionados no dependen del producto que
finalmente se va a recomendar al cliente. Se trata de niveles de peligro a priori computados nicamente
a partir de las caractersticas del cliente, el evento y el lugar.
A partir de la evalucin de estos criterios queremos obtener una recomendacin que diga al usuario de
la web que tipo de pack es el ms adecuado para su evento y la cantidad de productos de cada tipo
que habr finalmente en el pack.
Sabemos que las caractersticas abstractas tienen diferentes relaciones con estos productos. Por ejemplo, las preferencias marcan de una forma abstracta el tipo de pack que suele escoger el cliente, los
pack color y fantasia suelen estar contraindicados si hay niveles extremos de peligro en alguno de los
criterios, niveles generosos de presupuesto suelen llevar la recomendacin hasta el mximo nivel de
pack que sea adecuado para las caractersticas del evento, ...
a) Disea la ontologa del dominio descrito, incluyendo todos los conceptos que aparecen en la
descripcin e identificando los atributos ms relevantes. Lista que conceptos forman parte de los
datos de entrada del problema y que conceptos forman parte de la solucin. (Nota: tened en
cuenta que la ontologa puede necesitar modificaciones para adaptarla al apartado siguiente).
b) El problema descrito es un problema de anlisis. Explica cmo lo resolveras usando clasificacin
heurstica, usando los conceptos de la ontologa desarrollada en el apartado anterior. Da al menos
3 ejemplos de reglas para cada una de las fases de esta metodologa.
c) Las caractersticas que se utilizan para caracterizar el pedido y el pack recomendado no son
independientes entre si. Por ejemplo: el peligro de incendio influye sobre el peligro de daos
materiales, y ste sobre el peligro de daos personales; las preferencias influyen directamente
sobre la eleccin de cada tipo de pack, etc.
Define el problema de asociacin heurstica como una red bayesiana expresando en ella al menos
las relaciones indicadas y alguna ms, de forma que todas las caractersticas tengan algun tipo de
influencia en la solucin. Da un ejemplo de tabla de probabilidad de algn nodo, inventndote las
probabilidades, pero expresando como influyen los valores de los nodos padre en las probabilidades
de los valores de los nodos hijo.
15. El telescopio Kepler1 es un telescopio orbital usado para el descubrimiento de planetas extrasolares. Los
datos de este telescopio y los de otros observatorios tanto terrestres como orbitales se pueden utilizar
para estimar la habitablilidad de los planetas descubiertos. Una organizacin que prefiere mantenerse
annima nos ha encargado un SBC que permita planificar la prxima emigracin masiva de toda la
poblacin terrestre a los planetas descubiertos.
Los datos de los que disponemos incluyen informacin sobre el planeta candidato, el resto de planetas y
la estrella del sistema planetario y otros astros y sistemas candidatos en la cercana (unos 100 parsecs).
Cada sistema planetario tiene asociada su distancia a la Tierra (en aos-luz) y est compuesto por
una estrella y varios planetas (se descartan sistemas de ms de una estrella, suelen ser inabitables). De
cada estrella guardamos su radio (medido en soles: por debajo de 0.4 soles es una estrella enana, por
encima de 20 soles es una estrella gigante). Los planetas pueden ser rocosos o gigantes gaseosos. De
los planetas rocosos se tiene su tamao relativo a la Tierra (medido en tierras) y la distancia mxima
y mnima de la rbita del planeta a su estrella (medida en unidades astronmicas -UA-). Del planera
candidato (siempre rocoso) se guarda otra informacin adicional (como el porcentaje de oxgeno y de
hidrocarburos en la atmsfera),tal y como veremos a continuacin. De los gigantes rocosos se tiene
su tamao relativo a Jpiter (medido en jpiteres) y la distancia mxima y mnima de la rbita del
planeta a su estrella (medida en unidades astronmicas -UA-). Tambin tenemos informacin de las
supernovas cercanas (a mximo 10 parsecs de distancia), de ellas guardamos su tipo (Ia, Ib, Ib, II-b,
II-L, II-P, II-n) y su distancia (en parsecs) al sistema planetario. Tenemos informacin de las estrellas
gigantes cercanas (a mximo 10 parsecs de distancia) ya que son estrellas con alta probabilidad de
convertirse en supernovas en el futuro, de ellas guardamos su masa (medida en masas solares) y
su distancia (en parsecs) al sistema planetario candidato. Finalmente tenemos informacin de otros
1
http://kepler.nasa.gov/
88
89
mnima calurosa, una atmsfera de hidrocarburos densa y una atmsfera de oxgeno reactiva har un
planeta inhabitable, pero si la atmsfera de oxgeno es respirable lo har muy duro.
A partir de estas caractersticas queremos determinar la supervivencia de la poblacin que se traslade
a ese planeta en una escala de enteros del 0 al 10, donde 0 significa misin suicida y 10 un viaje al
paraso.
La experiencia en el dominio nos dice que:
La hospitalidad de la regin tiene un peso moderado en el xito, e incluso una zona segura no
aportara ms de tres puntos de la valoracin. Lo que si sabemos es que una zona peligrosa no
permite dar una valoracin total superior a cinco.
La hospitalidad del sistema tiene un peso superior y aportara hasta cinco puntos de la valoracin.
Sabemos que una hospitalidad segura permite una valoracin total de al menos cinco si la regin
es por lo menos aceptable.
La hospitalidad planetaria aportara hasta seis puntos de la valoracin. Lo que sabemos es que
un planeta inhabitable no permite una valoracin total mayor que uno. Una valoracin ideal
aportara el mximo de valoracin posible para este criterio, si la hospitalidad del sistema es al
menos soportable y la de la regin es al menos aceptable.
El valor final de la supervivencia se calcula a partir de las puntuaciones obtenidas para los tres criterios,
combinndolas segn las restricciones que imponen para obtener un valor en la escala entera de 0 a
10.
a) Disea la ontologa del dominio descrito, incluyendo todos los conceptos que aparecen en la
descripcin e identificando los atributos ms relevantes. Lista que conceptos forman parte de los
datos de entrada del problema y que conceptos forman parte de la solucin. (Nota: tened en
cuenta que la ontologa puede necesitar modificaciones para adaptarla al apartado siguiente).
b) El problema descrito es un problema de anlisis. Explica cmo lo resolveras usando clasificacin
heurstica, usando los conceptos de la ontologa desarrollada en el apartado anterior. Da al menos
3 ejemplos de reglas para cada una de las fases de esta metodologa.
c) Para aumentar la capacidad de trabajar con datos incompletos la empresa nos pide sustituir
las reglas de asociacin heurstica por una red bayesiana que, en vez de calcular la supervivencia
potencial de los humanos en el planeta candidato como un nmero entre 1 y 10, lo haga calculando
la probabilidad de supervivencia o de no supervivencia en ese planeta.
Define el problema de asociacin heurstica como una red bayesiana expresando en ella al menos
las relaciones indicadas en el enunciado, de forma que todas las caractersticas abstractas del
problema que hayas definido en el apartado anterior tengan algun tipo de influencia en la solucin.
Separa bien en el diagrama que variables describen caractersticas de problema y cuales describen
soluciones. Lista de forma clara los diferentes valores que puede tomar cada variable. Da un
ejemplo de tabla de probabilidad de algn nodo, inventndote las probabilidades, pero expresando
como influyen los valores de los nodos padre en las probabilidades de los valores de los nodos hijo.
16. Una famosa tienda de Internet desea ampliar los servicios que da a sus clientes dando recomendaciones
sobre que productos podra comprar a partir de la informacin que ha recolectado de los usuarios que
han hecho compras similares a las suyas.
Dado que es bastante costoso guardar toda la informacin de cada usuario individual se ha decidido
utilizar un sistema basado en el conocimiento capaz de determinar el perfil al que pertenece un usuario
usando las caractersticas de las diez ltimas compras realizadas para cada tipo de producto. De todas
formas, para poder refinar mas las recomendaciones guardamos tambin la cantidad de productos de
cada tipo que ha comprado el usuario a lo largo del tiempo. Los productos que se venden en esta
tienda virtual son libros, CDs musicales y pelculas en DVD.
Los libros estn caracterizados por una serie de atributos como pueden ser el titulo, el autor, el tipo de
encuadernacin (tapa dura o bolsillo), el precio. Estos estn categorizados segn su temtica en libros
90
17. La empresa de jardinera KAMACO esta introduciendo las tecnologas de la informacin y las tcnicas
avanzadas de inteligencia artificial en su gestin diaria. Por eso est pensando en la posibilidad de
construir un Sistema Experto (SE) para el diseo de jardines para sus clientes.
El diseo de jardines es una tarea muy creativa, pero tiene bastantes pautas de comportamiento que
pueden ser generalizadas y usadas informticamente. Hay una serie de caractersticas que se han de
tener en cuenta a la hora de disear un jardn:
El clima de la zona (temperatura, lluvia, viento, etc.)
El tipo de suelo, que puede ser muy pesado y resistente al agua (arcilloso), ligero (arenoso), con
cierta cantidad de sal (salino), etc.
La profundidad de la capa de suelo frtil, el drenaje natural, el pH de suelo
91
La orografa de la parcela, si hay zonas elevadas o zonas deprimidas, zonas planas, zonas con
pendientes fuertes o suaves, etc.
Las plantas a incluir: rboles, arbustos, setos, trepadoras, csped, plantas aromticas, rboles
frutales, etc.
Elementos del jardn, como por ejemplo mobiliario, rocas, muros de contencin, piscina, etc.
Usos del jardn que implican diversas zonas de utilizacin como por ejemplo usos deportivos,
reuniones familiares, relajacin y descanso, etc.
El coste del mantenimiento del jardn, que vara segn las especies vegetales
El presupuesto que quiere gastar el cliente, etc.
En la vida de la empresa se ha acumulado mucho conocimiento sobre el diseo de jardines. Hay un
conjunto de tipos bsicos de jardines con unas caractersticas determinadas: el jardn mediterrneo
con predominio de pinos, arbustos, rosales, csped suave, plantas aromticas; el jardn tropical
donde predominan el bamb, las palmeras, el csped y la vegetacin frondosa; el jardn alpino con
csped resistente al fro, abetos, plantas resistentes al fro; el jardn rabe con plantas resistentes a la
sequa, plantas autctonas, una fuente i/o estanque; el jardn clsico con setos, csped, parterres con
flores vistosas, estanques, plantas trepadoras; y unos cuantos tipos ms de jardn (ingls o paisajstico,
francs, japons, romntico, medieval, etc.).
Adems, se suelen identificar las diferentes zonas en las que se quiere dividir el jardn para diferentes
usos.
Se quiere construir un SE que dadas las preferencias del cliente, pero teniendo tambin en cuenta las
caractersticas de la parcela y del entorno obtenga el mejor diseo posible del jardn.
a) Identifica qu conceptos forman los datos de entrada del problema. Representa grficamente estos
conceptos mediante una red de frames incluyendo los atributos ms relevantes y las relaciones,
tanto las taxonmicas como las no taxonmicas que creas que son necesarias.
b) Identifica los conceptos que forman la solucin del problema. Representa grficamente estos conceptos mediante una red de frames y las relaciones, tanto las taxonmicas, como las no taxonmicas, que creas que son necesarias.
c) Cmo descompondras el problema en subproblemas? Identifica y especifica los subproblemas a
resolver y cmo se encadenaran para construir la solucin.
d) Indica para cada subproblema que has identificado si es un problema de anlisis o de sntesis.
Justifcalo.
e) Qu tipo de razonamiento te parece ms adecuado para cada subproblema? Justifcalo.
18. Los redactores jefe de cada peridico tienen cada da el difcil problema de decidir qu noticias incluyen
y en qu seccin y pgina deben ir. Para facilitar su tarea vamos a disear un SBC que realice este
trabajo de manera automtica a partir de una representacin de los elementos que describen una
noticia.
Una noticia se puede describir segn parte del conjunto de preguntas que todo buen periodista debe
seguir para escribir una noticia.
Qu? - Tema de la noticia, ste puede ser: poltica (elecciones, cumbres, escndalos, declaraciones, ...), desastres (desastres naturales, guerras, terrorismo, ...), cultura (cine, teatro, conciertos,
personajes, ...), deportes (ftbol, baloncesto, ...), economa (bolsa, empresas, escndalos, ...),
ciencia, sucesos, religin, otros ...
Quin? - Protagonista o protagonistas de la noticia, pueden ser un individuo, un colectivo (organizaciones, poblaciones, el mundo, ...) o entidades abstractas (el clima, la tierra, ... ). Estos
protagonistas pueden ser de mayor o menor relevancia.
92
19. Deseamos crear un sistema capaz de aconsejar a un usuario como invertir de la mejor manera los ahorros
de los que dispone. Para ello queremos recoger toda una serie de informaciones que nos puedan indicar
cules son sus caractersticas como ahorrador/inversor y a partir de ellas darle unas prioridades sobre
qu productos podran ser ms interesantes para el. La informacin que le pedimos al usuario incluye:
93
Su edad.
Si su perspectiva de ahorro futuro es favorable o desfavorable.
Si tiene deudas, cuanta proporcin de su salario supone pagar esas deudas.
Su actitud respecto a fluctuaciones negativas interanuales de sus inversiones de un 5 %, un 10 %,
un 20 % o ms de un 20 % (moderada, negativa, muy negativa).
Su actitud respecto a la oportunidad de ganancia contra la posibilidad de prdida (seguridad
ante todo, ganar un poco ms compensa si la posibilidad de prdida es pequea, la ganancia ante
todo).
Objetivo del ahorro (garantizar el capital, mantener la inflacin, obtener ganancias sobre la inflacin, obtener grandes ganancias).
Experiencia en la administracin de inversiones (nada, poca, bastante).
El ahorro de impuestos (indiferente, importante o muy importante).
Hemos decidido abstraer la informacin obtenida del usuario en cinco caractersticas:
Riesgo, que mide el riesgo que puede o quiere asumir el cliente, valorado como bajo, medio, alto
y muy alto. El riesgo esta asociado a la edad (cuanto ms viejo, menos riesgo se puede asumir), a
la actitud a las fluctuaciones (cuanto peor, menos riesgo), a la proporcin que suponen las deudas
respecto al salario (cuantas ms deudas, menos riesgo), a la actitud respecto a la oportunidad
de ganancia, el objetivo de ahorro (cuantas ms ganancias ms riesgo) y la experiencia en la
administracin de inversiones (cuanta ms experiencia, ms riesgo).
Diversificacin, que mide la variedad de valores en los que invertir, valorado como poca, media
y mucha. La diversificacin est asociada a la actitud a la oportunidad de ganancia, (cuanta ms
seguridad se quiera respecto a la ganancia, mayor ha de ser la diversificacin), la actitud respecto
a las fluctuaciones (cuanto ms negativa, ms diversificacin) y la experiencia en la administracin
de inversiones (cuanta menos experiencia, ms diversificacin).
Plazo, que mide el tiempo que se debe mantener la inversin, valorado como corto, medio o
largo. El plazo depende de la actitud respecto las fluctuaciones (cuanto menos negativa, el plazo
puede ser ms largo), la perspectiva del futuro ahorro (cuanto mejor sea, ms plazo), el objetivo
de ahorro (cuantas ms ganancias, mayor ha de ser el plazo) y el ahorro de impuestos (se pagan
ms impuestos cuanto ms corto sea el periodo de la inversin)
Administracin activa, que mide lo involucrado que debe estar el cliente en la evolucin y
manejo de sus inversiones, valorada en constante, moderada y poca. Esta caracterstica depende
de la experiencia del cliente (cuanta menos experiencia, menos involucrado), el objetivo del ahorro
(cuanta mayor la ganancia, ms deber estar involucrado) y la actitud respecto a las fluctuaciones
(cuanto ms negativa sea a mayores prdidas, ms deber estar involucrado).
Liquidez de la inversin, que mide la facilidad para convertir la inversin en dinero a corto
plazo, valorada como alta, moderada y baja. La liquidez depender de la proporcin de la deudas
(cuantas ms deudas, ms liquidez), la experiencia en administracin de inversiones (cuanto
menos experiencia, menos liquidez), la actitud respecto a la prdida (cuanto menos negativa,
menos liquidez es necesaria) y el objetivo de ahorro (cuanto menos ganancia, menos liquidez).
A partir de evaluar estos criterios queremos obtener una prioridad para los diferentes tipos de productos
que se pueden ofrecer al cliente: fondos de pensiones, acciones, fondos de inversin (en acciones, renta
fija o mixtos) y depsitos (a corto plazo o a largo plazo). Esta prioridad debera obtenerse como un
valor entero entre 0 y 5, indicando la importancia de incluir ese tipo de valor en la inversin.
La experiencia del dominio nos dice que:
Los fondos de pensiones son ms convenientes cuanto menos riesgo se quiera, son mejores cuando
se quiere una buena diversificacin, tienen mejor resultado cuanto ms largo es el plazo, no
requieren una administracin activa y no tienen liquidez.
Las acciones son ms recomendables para inversiones con ms riesgo, siempre que se pueda hacer
una administracin activa, permiten menos diversificacin, se puede invertir en ellas a cualquier
plazo, pero son ms recomendables a corto y tienen total liquidez.
94
95
a) Disea la ontologa del dominio descrito, incluyendo todos los conceptos que aparecen en la
descripcin e identificando los atributos ms relevantes. Lista que conceptos forman parte de los
datos de entrada del problema y que conceptos forman parte de la solucin. (Nota: tened en
cuenta que la ontologa puede necesitar modificaciones para adaptarla al apartado siguiente).
b) El problema descrito es un problema de anlisis. Explica cmo lo resolveras usando clasificacin
heurstica, usando los conceptos de la ontologa desarrollada en el apartado anterior. Da al menos
3 ejemplos de reglas para cada una de las fases de esta metodologa.
c) Las caractersticas que se utilizan para caracterizar el pedido y los tipos bsicos de viviendas
escogidos no son independientes entre si. Por ejemplo: la movilidad de los habitantes de la casa,
el presupuesto, la orografa y el espacio disponible afectan al nmero de plantas, el presupuesto
tambin influye en la calidad de los materiales, que a su vez tiene un efecto sobre el nmero de
plantas, etc.
Define el problema de asociacin heurstica como una red bayesiana expresando en ella al menos
las
relaciones indicadas en el enunciado, en este apartado y alguna ms, de forma que todas las
caractersticas abstractas del problema que hayas definido en el apartado anterior tengan algun
tipo de influencia en la solucin. Separa bien en el diagrama que variables describen caractersticas
de problema y cuales describen soluciones. Da un ejemplo de tabla de probabilidad de algn nodo,
inventndote las probabilidades, pero expresando como influyen los valores de los nodos padre en
las probabilidades de los valores de los nodos hijo.
96
P (A)
P (B)
C
F
0.25
0.75
C
F
0.4
0.6
C
C
F
F
C
F
C
F
P (C|A, B)
C
F
0.75 0.25
0.5
0.5
0.75 0.25
0.1
0.9
C
C
F
P (D|C)
C
F
0.3 0.7
0.4 0.6
P (C|a, b)
P (D|b, c)
P (B|a)
P (D|a)
P (A)
C
F
0.3
0.7
C
F
P (B|A)
C
F
0.1 0.9
0.4 0.6
A
C
F
P (C|A)
C
F
0.1 0.9
0.6 0.4
C
C
F
F
C
F
C
F
P (D|B, C)
C
F
0.7
0.3
0.2
0.8
0.1
0.9
0.4
0.6
98
D
C
P (A)
P (B)
C
F
0.3
0.7
C
F
0.2
0.8
C
C
F
F
C
F
C
F
P (C|A, B)
C
F
0.3
0.7
0.1
0.9
0.7
0.3
0.4
0.6
C
C
F
P (D|C)
C
F
0.1 0.9
0.7 0.3
C
C
F
P (E|C)
C
F
0.4 0.6
0.7 0.3
C
E
P (A)
P (B)
C
F
0.2
0.8
C
F
0.6
0.4
C
F
P (C|A)
C
F
0.3 0.7
0.2 0.8
B
C
F
P (D|A)
C
F
0.6 0.4
0.9 0.1
C
C
F
F
C
F
C
F
P (E|C, D)
C
F
0.1
0.9
0.7
0.3
0.2
0.8
0.4
0.6
99
C
D
P (A)
P (B)
C
F
0.1
0.9
C
F
0.3
0.7
C
F
P (C|A)
C
F
0.2 0.8
0.6 0.4
C
C
F
F
C
F
C
F
P (D|B, C)
C
F
0.1
0.9
0.7
0.3
0.8
0.2
0.4
0.6
D
C
F
P (E|D)
C
F
0.2 0.8
0.7 0.3
A
C
B
P (A)
C
F
0.3
0.7
C
F
P (B|A)
C
F
0.1 0.9
0.6 0.4
C
C
F
F
C
F
C
F
P (C|A, B)
C
F
0.1
0.9
0.7
0.3
0.4
0.6
0.8
0.2
B
D
C
100
P (A)
P (C)
C
F
0.3
0.7
C
F
0.6
0.4
C
F
P (B|A)
C
F
0.2 0.8
0.4 0.6
C
C
F
F
C
F
C
F
P (D|B, C)
C
F
0.3
0.7
0.9
0.1
0.5
0.5
0.6
0.4
B
D
A
C
A
P (A)
C
F
0.7
0.3
C
F
P (B|A)
C
F
0.1 0.9
0.4 0.6
B
C
F
P (C|A, B)
C
F
0.5
0.5
0.2
0.8
C
C
F
F
C
F
C
F
P (D|B, C)
C
F
0.1
0.9
0.4
0.6
0.3
0.7
0.8
0.2
A
C
B
A
P (A)
C
F
0.6
0.4
C
F
P (B|A)
C
F
0.2 0.8
0.7 0.3
C
C
F
F
C
F
C
F
P (C|A, B)
C
F
0.1
0.9
0.5
0.5
0.3
0.7
0.4
0.6
C
C
F
P (D|C)
C
F
0.1 0.9
0.7 0.3
A
E
101
P (A)
C
F
0.3
0.4
C
F
P (B|A)
C
F
0.5 0.5
0.1 0.9
A
C
F
P (C|A)
C
F
0.4 0.6
0.2 0.8
C
C
F
P (D|C)
C
F
0.1 0.9
0.6 0.4
C
C
F
F
C
F
C
F
P (E|B, D)
C
F
0.4
0.6
0.1
0.9
0.2
0.8
0.5
0.5
A
D
P (A)
C
F
0.7
0.3
C
F
P (B|A)
C
F
0.6 0.4
0.8 0.2
A
C
F
P (C|A)
C
F
0.6 0.4
0.3 0.7
C
C
F
F
C
F
C
F
P (D|A, C)
C
F
0.4
0.6
0.8
0.2
0.3
0.7
0.5
0.5
C
C
F
F
C
F
C
F
P (E|B, D)
C
F
0.1
0.9
0.6
0.4
0.7
0.3
0.2
0.8
p2
S(p1,p2)
p1
P (p1)
p1
adj
adv
0.8
0.2
adj
adv
P (p2|p1)
nom verb
0.7
0.3
0.1
0.9
p1
p2
adj
adj
adv
adv
nom
ver
nom
ver
p3
S(p1, p2)
SN
nSN
P (p3|S(p1, p2))
nom
adj
0.7
0.3
0.2
0.8
Define la distribucin de probabilidad conjunta de P (p1, p2, p3, S(p1, p2)) que define la red y usa el
algoritmo de eliminacin de variables para calcular la probabilidad de P (p3|p1 = adj).
102
13. Una aplicacin bastante difunda de las redes bayesianas es la implementacin de asistentes de usuario,
como por ejemplo en un sistema operativo. Estos asistentes pueden recolectar informacin del funcionamiento del sistema y presentar recomendaciones y avisos al usuario para que atienda a posibles
problemas en su sistema.
Por ejemplo, podemos tener un asistente que cronometra la respuesta de la aplicacin en primer plano
(RA), el rendimiento de entrada/salida de los discos duros (RES) y el tamao de la cola de eventos
del interfaz del sistema operativo (EV) y usar estas informaciones para lanzar un mensaje sobre un
posible problema en la configuracin de drivers (PD).
Esta red bayesiana representara las relaciones entre estos conceptos.
RES
RA
EV
PD
Y estas tablas de probabilidades representaran las influencias de unos nodos sobre otros.
RES
P (RES)
RES
0.8
0.2
P (EV )
vaca llena
0.7
0.3
0.1
0.9
RES
EV
vaca
llena
vaca
llena
P (RA)
< 500ms
> 500ms
0.9
0.1
0.5
0.5
0.6
0.4
0.1
0.9
EV
RA
vaca
vaca
llena
llena
< 500ms
> 500ms
< 500ms
> 500ms
P (P D)
S
No
0.1 0.9
0.3 0.7
0.4 0.6
0.9 0.1
Define la distribucin de probabilidad conjunta de P (RES, EV, RA, P D) que representa la red y usa el
algoritmo de eliminacin de variables para calcular la probabilidad de P (RA|EV = llena, P D = S).
Molt
Baixa
Suau
Dreta
Esquerra
Baixa
Molt
Alta
Alta
Dreta
Km/h
Graus
45 30 15
15
30
45
20
40
60
80
100
120
103
a) Dna una interpretaci intutiva breu (una lnia) de les regles de control segent:
R1. si PV=centre i DD=dreta i V=alta llavors gir=suau-esquerra
R2. si PV=suau dreta i DD=dreta i V= baixa llavors gir=esquerra
b) Escriu 2 regles ms de la mateixa forma que tinguin sentit (com les que utilitzes tu quan condueixes
el teu cotxe i no vas begut !).
c) Dna el conjunt difs que sobt per a la variable gir a partir de les regles R1 i R2 quan tenim
els segents valors concrets: PV = 10, DD = dreta , V= 70.
2. Tenemos un robot que es capaz de desplazarse y girar sobre si mismo y tenemos un conjunto de reglas
difusas que le permiten avanzar hacia un objetivo y evitar obstculos. Estas reglas estn definidas
sobre cuatro atributos, distancia (cerca, media, lejos) al obstculo ms cercano y al objetivo, velocidad
del robot (baja, media, alta), ngulo de giro (todo a la izquierda, algo a la izquierda, algo a la derecha,
todo a la derecha) y posicin de un objeto respecto al robot (izquierda, frente, derecha). Las variables
distancia, velocidad y ngulo de giro son difusas y la definicin de sus valores es la que aparece en la
figura.
Cerca
0.4
Media
0.8
Baja
Lejos
1.2
1.6
Media
0.2
metros
0.4
Distancia
Todo izq
Alta
0.6
0.8
m/s
Velocidad
Algo izq
60 45 30 15
Algo der
0
Giro
15
30
Todo der
45
60
Las reglas que controlan la velocidad del robot y el ngulo de giro son las siguientes:
Velocidad:
RV1. Distancia(obstculo)=cerca velocidad=baja
RV2. Distancia(objetivo)=lejos (velocidad=baja velocidad=media) velocidad=alta
RV3. Distancia(obstculo)=media velocidad=alta velocidad=media
Giro:
RG1.
RG2.
RG3.
RG4.
RG5.
RG6.
En el momento actual el robot est a una distancia del objetivo de 3 metros y su posicin es a la
izquierda del robot, el obstculo ms cercano est a 0.5 metros y su posicin es frente al robot y la
velocidad del robot es 0.7 m/s. Cual ser (aproximadamente) la velocidad y el ngulo de giro que
se obtendrn mediante las reglas? (utiliza mximo y mnimo como funciones de combinacin de las
conectivas lgicas)
104
3. Dadas las siguientes variables con sus dominios difusos, las siguientes reglas y los siguientes valores
concretos de variables, cul es el valor concreto de cada una de las variables despus de aplicar
razonamiento aproximado? Presenta cada uno de los pasos del proceso utilizando la T-norma del
mnimo, la T-conorma del mximo y la funcin de negacin f(x)=1-x. Si se requiriese realizar la
fase de nitidificacin, tnganse en cuenta slo nmeros enteros (no decimales) como valores concretos
relativos a la variable a nitidificar.
Reglas
R1: luz = muy_claro y no lluvia = torrencial persiana = casi_bajada
R2: luz = claro y ( lluvia = poca o lluvia = nada ) persiana = intermedia
R3: luz = claro y lluvia > poca y lluvia < torrencial persiana = intermedia
oscuro
muy
oscuro
tenue
claro
LLUVIA
muy
claro
nada
poca
20
mucha
normal
40
60
80
100
torrencial
120
PERSIANA
casi
bajada
bajada
casi
subida
intermedia
subida
10
R1.
R2.
R3.
R4.
si
si
si
si
105
Frio
Normal
16
Calor
18 20 22 24
Temperatura
Baja
26
Moderada
Media
Alta
0 1 2 3 4 5 6 7 8 9 10
Insolacion
Bajar Poco
Subir Poco
Bajar
Mantener
Subir
Potencia
Adulto
Joven
10
15
Viejo
20
25
30
Bajo
35
50
100
Medio
150
Edad
Alto
350
400
Peso
Bajo
Normal
Alto
8 9 10 11 12 13 14 15 16
Aporte Vitaminico
Algunas de las reglas que permiten estimar el complemento vitamnico para cada individuo son:
R1. si peso = medio y edad = adulto entonces AV = normal
R2. si peso = alto y ( edad = adulto o edad = viejo) entonces AV = alto
R3. si peso = bajo y edad = joven entonces AV = alto
R4. si edad = joven entonces AV = normal
R5. si edad = viejo entonces AV = bajo
106
10.1 Bsqueda
1. Queremos conectar N ciudades con B autobuses. Cada autobs ha de comenzar su trayecto en la ciudad
C1 y finalizarlo en la ciudad CN . Conocemos las distancias entre cada par de ciudades y queremos que
el camino recorrido por cada autobs no exceda K kilmetros y que el nmero de paradas que haga
cada autobs no sea mayor que P .
Buscamos la solucin que conecte todas las ciudades sin que dos autobuses pasen por la misma ciudad
(exceptuando C1 y CN ) y recorriendo el mnimo nmero de kilmetros.
a) Queremos utilizar A . Definimos el estado como la asignacin de ciudades a autobuses. El estado
inicial consiste en asignar las ciudades C1 y CN a cada autobs. Tenemos un operador que asigna
una ciudad a un autobs y cuyo coste es la suma de las distancias entre la ciudad asignada con C1
y CN , slo podemos asignar una ciudad a un autobs si no excedemos el valor P . Como funcin
heurstica usamos la suma de las distancias de todas las ciudades por asignar con C1 y CN .
b) Aplicar un algoritmo de satisfaccin de restricciones. Las variables son las ciudades, los dominios
son los autobuses donde podemos asignarlas. Supondremos que no tenemos en cuenta las ciudades
C1 y CN ya que estarn asignadas a todos los autobuses. Como restricciones imponemos que un
autobs no est asignado a ms de P ciudades y que la longitud del camino mnimo que recorre
las ciudades asignadas a un autobs no sea mayor que K.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
2. Tenemos un problema de bioinfomtica que consiste en lo siguiente: Tenemos una cadena de ADN de
una longitud fija y un conjunto de subcadenas que tenemos que encajar en cualquier posicin de la
cadena donde coincidan las letras. Cada subcadena tiene una longitud (li ). El objetivo es buscar el
mnimo subconjunto de las subcadenas que permita cubrir la mayor longitud posible de la cadena, sin
que haya ningn solapamiento entre las posiciones que cubren las subcadenas escogidas.
a) Queremos utilizar A , consideramos el estado como las subcadenas que tenemos asignadas. El
estado inicial es no tener ninguna cadena asignada. Tenemos un operador que asigna una subcadena a alguna de las posiciones en las que coincide con la cadena, el coste de este operador es
uno. Como funcin heurstica usamos la suma de las longitudes de los trozos de la cadena que no
estn cubiertos.
b) Queremos utilizar satisfaccin de restricciones. Consideramos que las subcadenas son las variables
y los dominios son todas las posiciones donde se pueden encajar las subcadenas en la cadena.
Como restricciones tenemos que para cada par de cadenas no puede haber solapamiento entre las
posiciones que corresponden a sus asignaciones y que la suma de las longitudes de las subcadenas
que estn asignadas sea en la solucin mayor que un valor L.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
3. Queremos planificar cmo debemos integrar diferentes procesos individuales de fabricacin de diversos
productos en un nico proceso. Cada producto necesita utilizar un conjunto de mquinas en un orden
especfico que se puede describir mediante una secuencia de proceso. El uso de una mquina es un
107
108
4. En todo proyecto de desarrollo de una aplicaciones informticas es necesario determinar cuanto tiempo
y recursos va a ser necesario invertir. Una vez decididas las tareas, su duracin y la dependencia entre
ellas podemos determinar automticamente cuando se van a desarrollar y qu personas van a hacer
cada tarea.
Supondremos que hemos dividido el problema en tareas que tienen todas la misma duracin y hemos
determinado su grafo de dependencias, de manera que para cada una de ellas sabemos qu tareas han de
estar terminadas para poder empezarla. Disponemos tambin de un conjunto de programadores (prog1
a progn ) que podemos asignar a cada una de las tareas. Obviamente si asignamos el mismo programador
a dos tareas que pueden realizarse simultneamente tardaremos ms que si asignamos programadores
diferentes, pero siempre nos saldr ms barato usar un nmero menor de programadores.
El objetivo del problema es encontrar la menor asignacin de programadores a tareas que respete el
orden de dependencia de estas.
a) Queremos usar A definiendo el estado como la asignacin de programadores a tareas. El estado
inicial sera la asignacin vaca y el estado final sera la asignacin completa de programadores
a tareas. Como operador utilizamos asignar un programador cualquiera a una tarea cualquiera,
el coste del operador sera una unidad. La funcin heurstica es el nmero de tareas que quedan
por asignar que tengan alguna tarea de la que dependan que no est ya asignada.
b) Queremos usar satisfaccin de restricciones, donde las variables son las tareas a asignar y los
programadores los dominios de las variables. Las restricciones son las relaciones de dependencia
entre las diferentes tareas. Sobre estas restricciones imponemos adems que no pueda haber ms
de tres programadores diferentes en tareas que pueden realizarse en paralelo.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
10.1 Bsqueda
109
5. Despus de los incendios del verano se nos ha planteado redisear la ubicacin de los parques de
bomberos. Para solucionar el problema dividimos el rea en una cuadrcula de N M , cada posicin
tiene asignado un factor de accesibilidad A que toma un valor entero entre 1 y 3 (1 es una zona de
fcil acceso, 3 es un rea de difcil acceso).
Deseamos ubicar un total de P parques de bomberos, cada parque de bomberos puede tener entre uno
y tres camiones. Tenemos un total de C camiones para repartir (obviamente C > P ).
Definimos el factor de seguridad de una posicin como la suma para esa posicin y todas las que la
rodean del cociente entre el nmero de camiones de bomberos que hay en esa posicin y el factor de
accesibilidad de cada posicin.
El objetivo es ubicar todos los parques de bomberos y repartir entre ellos todos los camiones de manera
que el factor de seguridad global (la suma para todas las posiciones) sea el mximo posible.
a) Queremos utilizar A de manera que recorremos la cuadrcula de la esquina superior izquierda a la
inferior derecha. El estado es la asignacin que hemos hecho de parques de bomberos y camiones a
las reas recorridas. Utilizamos como operador poner un parque de bomberos, asignando uno, dos
o tres camiones en el caso de ponerlo, el coste del operador es el nmero de camiones asignados
ms uno, o no ponerlo con coste uno. La funcin heurstica es el nmero de reas que nos quedan
por visitar y vale infinito si ya hemos asignado ms de C camiones o P parques de bomberos.
b) Queremos utilizar bsqueda local generando una solucin inicial en la que repartimos al azar los
P parques de bomberos con un camin cada uno. Los operadores son aumentar o disminuir el
nmero de camiones de un parque y mover un parque con todos sus camiones a otra posicin.
La funcin heurstica que queremos optimizar es el factor de seguridad global ms una constante
por el nmero de camiones que quedan por asignar.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
6. Queremos asignar un conjunto de seminarios a una lista de aulas. Para cada seminario tenemos la
fecha tentativa en la que debera realizarse, pero sabemos que tenemos un margen de hasta tres das
que podemos usar para retrasar su inicio. Tambin disponemos de la duracin del seminario (1, 2 o 3
horas).
Para cada aula sabemos en qu fecha est disponible y durante cuntas horas (1, 2 o 3 horas). Un aula
slo se puede reservar para todo el periodo durante el que est disponible, por lo que si el seminario
dura menos estaremos perdiendo horas.
El objetivo sera asignar los seminarios a las aulas de manera que se minimice el nmero de horas
desperdiciadas y que los seminarios se retrasen lo mnimo posible. Supondremos que tenemos aulas
suficientes para asignar todos los seminarios y que hay muchas ms aulas que seminarios. Se nos
plantean las siguientes formas de solucionar el problema:
a) Queremos utilizar A de manera que ordenamos las aulas segn la fecha en las que estn disponibles (en caso de estar disponible en la misma fecha decidimos un criterio de ordenacin).
Procedemos a asignar los seminarios siguiendo el orden establecido utilizando dos operadores:
asignar un seminario que quepa en las horas disponibles y que no viole las restricciones de fecha de inicio (el coste sera las horas disponibles del aula) o no asignar nada al aula (el coste
sera cero). Como funcin heurstica utilizaremos la suma de horas de seminario que quedan por
asignar.
b) Queremos usar satisfaccin de restricciones para resolver el problema, para ello elegimos como
variables los seminarios y para cada seminario calculamos su dominio seleccionando todas las aulas
en la que puede ubicarse cumpliendo las restricciones de fechas y de horas necesarias. Aadimos
dos restricciones adicionales al problema, la primera es que la suma de retrasos de los seminarios
ha de ser menor que el valor R y que la diferencia entre las horas que dura cada seminario y las
horas libres del aula en el que es ubicado ha de ser menor o igual que uno.
110
D(T
)
j
k
i=1
i=1 Tj Abast(Ai )
Tj Abast(Ai )
k
X
i, j(i 6= j)
D(Ta )
Ta Abast(Ai )
D(Tb ) 1.05
Tb Abast(Aj )
Para cualquier almacn, la suma de las distancias de las tiendas asignadas a l no puede
ser mayor en un 5 % a la suma de las distancias de las tiendas asignadas a cualquiera otro
almacn.
i, j(i 6= j)
X
Ta Abast(Ai )
Dist(Ta , Ai )
Dist(Tb , Aj ) 1.05
Tb Abast(Aj )
8. El ayuntamiento de una pequea ciudad quiere ofrecer a sus ciudadanos un servicio similar al Bicing
barcelons, pero a menor escala. Uno de los problemas a resolver es como mover las bicicletas de un
punto de recogida a otro para intentar que en toda estacin haya algunos puestos libres para dejar
bicicletas, y que en toda estacin haya alguna bicicleta disponible. El ayuntamiento ya tiene un sistema
que decide que bicicletas hay que mover de una estacin a otra, y ha subcontratado los servicios de
un camin, que puede llevar un mximo de B bicicletas a la vez. Cada hora el camin ha de recoger
y dejar bicicletas en diferentes estaciones del servicio distribuidas por la ciudad, siguiendo un listado
del ayuntamiento de pares (estacin_origen, estacin_destino), y ha de hacerlo realizando el recorrido
ms corto posible, sin que se sobrepase en ningn momento el mximo de bicicletas que el camin
puede cargar. Cada hora partimos de cierto punto de origen y volvemos a l, habiendo movido todas las
10.1 Bsqueda
111
bicicletas que el ayuntamiento ha solicitado de su estacin origen a su estacin destino. Para obtener
el recorrido se dispone de un mapa de la ciudad que indica la distancia mnima entre cada par de
estaciones por las que ha de pasar el camin.
Puedes resolverlo mediante:
a) El algoritmo de A*. El estado es el camino recorrido. Utilizamos como coste la longitud del camino
actual. La funcin heurstica vale infinito si el camin en el estado actual supera el nmero B de
bicicletas que puede transportar y, en caso contrario, es la suma de las distancias de las estaciones
por recorrer al origen. El operador aplicable es pasar de la estacin actual a otra no visitada.
Para evitar la necesidad de otro operador, el punto de origen y final del camin se modela como
una estacin ms.
b) Satisfaccin de restricciones, donde las variables son todas las aristas del grafo de conexiones
entre las estaciones a recorrer, stas son variables booleanas e indican si pertenecen al camino a
recorrer o no. Las restricciones son que debe haber exactamente dos aristas de un mismo vrtice
en la solucin y que no se sobrepase el nmero B de bicicletas que el camin puede llevar a la
vez en el recorrido formado por las aristas.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
9. Deseamos construir un circuito integrado de manera que la intensidad de corriente necesaria por los
diferentes elementos est equilibrada en todo el circuito. Para simplificar el problema hemos supuesto
que el circuito es una cuadrcula de N M . Los diferentes elementos que queremos colocar en el
circuito son de K tipos diferentes y tenemos que colocar un nmero ek de cada uno de ellos. Cada tipo
de elemento necesita una intensidad de corriente especfica.
Cada posicin del circuito puede albergar P elementos de cualquier tipo y hemos de colocar todos los
elementos.
Lo que hemos de conseguir es que la suma de las intensidades que necesitan los elementos para cada
fila y cada columna no supere un valor I y que la diferencia de intensidad de corriente entre una celda
y cada una de sus cuatro vecinas contiguas no sea mayor que un valor V .
Se nos plantean las siguientes alternativas:
a) Queremos utilizar satisfaccin de restricciones donde las variables son los diferentes elementos
a colocar y los valores son las coordenadas (i, j) de la cuadrcula. Las restricciones aparecern
entre los elementos de manera que la suma de las intensidades de los elementos que compartan
la misma fila y los que compartan la misma columna sea menor que I y que la diferencia entre
la suma de las intensidades de los elementos de una celda con la suma de las intensidades de los
elementos de las celdas vecinas contiguas no sea superior en V .
b) Queremos utilizar A , para ello recorremos secuencialmente la cuadrcula desde la esquina superior
izquierda hasta la esquina inferior derecha. Usamos como operador el colocar de 0 a P elementos en
la casilla actual, el coste del operador es el nmero de elementos colocados. La funcin heurstica
es el nmero de elementos por colocar o infinito si la suma de intensidades de los elementos de
alguna fila o columna supera el valor I o la diferencia entre la suma de las intensidades de los
elementos de una celda con la suma de las intensidades de los elementos de las celdas vecinas
contiguas no sea superior en V .
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
10. Para hacer presin ante RENFE, los sindicatos de conductores de Cercanas en Barcelona quieren
encontrar la forma de cumplir los requisitos mnimos que se les imponen sobre nmero de trenes, pero
afectando al mayor nmero de usuarios, para que sus reclamaciones les den a ellos mayor poder en las
112
11. El rea de Parques y Jardines del Ayuntamiento de Barcelona quiere modernizar su flota de minifurgonetas con una nueva, experimental, impulsada por hidrgeno, que tiene la ventaja de ser altamente
ecolgica y fcil de mantener pero que tiene una autonoma muy limitada. Para resolver el problema
de la autonoma se han colocado 3 surtidores de hidrgeno por diferentes partes de la ciudad para que
la mini-furgoneta pueda repostar.
Queremos planificar el recorrido diario de esta mini-furgoneta por los diferentes parques de la ciudad de
forma que pueda pasar por todos los parques una vez, tardando el mnimo tiempo posible y pasando por
uno de los surtidores cada vez que se le est acabando el hidrgeno. Como datos para esta planificacin
disponemos de una tabla que nos indica las posiciones de todos los parques y jardines a visitar y de los
tres surtidores, as como la distancia entre cada uno de estos puntos en la ciudad. Sabemos tambin
que la mini-furgoneta experimental tiene un tanque de n litros de hidrgeno y que su consumo es de
x litros de hidrgeno por kilometro.
Se nos plantean las siguientes alternativas:
a) Queremos utilizar A* para minimizar el nmero de kilometros recorridos por la furgoneta y
reducir el nmero de repostajes al mnimo. Utilizaremos como funcin de coste la longitud del
camino (usando la tabla de distancias antes mencionada), donde la funcin heurstica vale infinito
si la mini-furgoneta no tiene suficiente combustible para ir del punto actual a un surtidor, y en
caso contrario es la suma de las distancias de los puntos por recorrer al punto actual. El operador
aplicable es pasar del punto actual a otro punto.
b) Queremos utilizar busqueda local para minimizar el nmero de kilometros recorridos por la minifurgoneta y reducir el nmero de repostajes al mnimo. Partimos de una solucin inicial en la
que intercalamos un paso por el surtidor de hidrgeno entre parque y parque. Se dispone de dos
operadores de modificacin de la solucin: uno para eliminar del camino un paso por el surtidor,
y otro para modificar el orden en el que visitamos alguno de los puntos del camino (ya sea parque
o surtidor). La funcin heurstica es la longitud del camino recorrido + 2 kilmetros extra de
penalizacin por cada paso por un surtidor.
Comenta cada una de las posibilidades indicando si resuelven o no el problema y qu ventajas e
inconvenientes tiene cada una de ellas. Justifica la respuesta.
10.1 Bsqueda
113
12. Un pequeo aeropuerto necesita organizar el horario de los vuelos de un da. El aeropuerto puede
aceptar 10 vuelos cada hora y esta abierto 15 horas al da. Para establecer el horario de vuelos, el
aeropuerto puede escoger vuelos de 10 compaas diferentes y cada compaa ofrece vuelos a 10 destinos
diferentes.
El horario no puede tener ms de dos vuelos de la misma compaa a la misma hora y dos vuelos hacia
el mismo destino de una compaa han de estar separados al menos seis horas.
La ganancia que obtiene el aeropuerto por tener un vuelo de una compaa a un destino depende de
su demanda. Queremos maximizar la ganancia del aeropuerto cumpliendo las restricciones. Podemos
resolver el problema de dos formas diferentes:
a) Usando A , definiendo como estado la asignacin de vuelos al horario. El estado inicial es el
horario vaco, el estado final se obtiene cuando el horario est lleno. Como operador de bsqueda
usamos la asignacin de un vuelo de una compaa a un destino a una hora especfica del horario,
el coste ser el dinero que el aeropuerto gana con este vuelo. Como funcin heurstica usamos el
nmero de vuelos que an se han de asignar al estado.
b) Usando satisfaccin de restricciones. Asumimos que un vuelo de una compaa a un destino
puede ser asignado como mucho a tres diferentes horas. Creamos un grafo de restricciones que
tiene como variables las tres posibles horas a las que un vuelo de una compaa a un destino
puede ser asignado. El dominio de una variable es las horas que pueden asignarse a un vuelo y
vaco para el caso en el que no se le asigna a ninguna hora. Hay una restriccin entre las variables
de un vuelo a un destino de una compaa que impide que la diferencia entre las horas asignadas
sea menos que seis horas y una restriccin entre todos los vuelos de una compaa que impide
que haya mas de dos vuelos a la misma hora.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
13. Un problema logstico en el 9-N es asegurar transporte para los voluntarios que no disponen de vehculo
propio y que han de desplazarse por zonas del territorio con pocas opciones de transporte pblico. Por
ello varias asociaciones del Alt Urgell han alquilado de forma conjunta un autocar con 35 plazas, y nos
han pedido crear un programa que, dada la informacin sobre el punto de recogida de cada voluntario
y su punto de destino (ambos dentro de la comarca) calcule el recorrido ms corto posible que debe
hacer el camin para recoger y dejar a todos los voluntarios, sin que se sobrepase en ningn momento
el nmero de plazas disponibles en el autocar.
El autocar parte desde cierto punto de origen y ha de volver a l al final del recorrido, habiendo
dejado todos los voluntarios en sus puntos de destino. En ningn punto de recogida habr ms de 35
voluntarios por recoger. Para obtener el recorrido se dispone de un mapa de la comarca que indica la
longitud del camino mnimo entre cada dos puntos por los que ha de pasar el autocar.
a) Queremos utilizar A . Usaremos como coste la longitud del camino. La funcion heurstica vale
infinito si el autocar supera el numero mximo de pasajeros y en caso contrario, es la suma de las
distancias de los puntos por recorrer al origen. El operador aplicable es pasar del punto actual a
otro no visitado (se supone que en cada punto visitado se recoge o deja a todos los voluntarios
que toca, no se puede recoger solo a una parte de los voluntarios y volver ms tarde a por el
resto).
b) Aplicar un algoritmo de satisfaccin de restricciones. Las variables son todas las aristas del grafo
de conexiones entre los puntos a recorrer, stas son booleanas e indican si pertenecen al camino a
recorrer o no. Las restricciones son que debe haber exactamente dos aristas de un mismo vrtice
en la solucin y que no se sobrepase el numero mximo de pasajeros del autocar en el recorrido.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
114
14. Tras las numerosas crticas y movilizaciones de los taxistas por el mecanismo de turnos que ha implantado recientemente el Ajuntament de Barcelona para el sector, un grupo de trabajo formado por
representantes de los taxistas y del Ajuntament nos ha pedido crear un sistema que adapte el nmero
de taxis ciculando por el rea metropolitana a la demanda estimada y al nivel de contaminacin diaria
(medida en gr. de CO2 emitidos a la atmsfera.
Segn nos cuentan, en estos momentos hay un nmero T de taxis registrados en el rea metropolitana.
Nos han contado que en vez de controlar el nmero de pasajeros que lleva cada taxi, el sistema
controlar el nmero de servicios (un servicio es un viaje del taxi que recoge a un cierto nmero
de pasajeros en un lugar de origen y los deja en un lugar de destino). Para simplificar el problema
consideraremos que cada servicio dura unos 15 minutos de media. Se establece que el sistema asignar a
cada taxi como mnimo N S servicios a la semana. Para cada taxi t disponemos del valor COt que mide
el grado de contaminacin que produce (medido en gr. de CO2 emitidos por minuto). El Ajuntament
nos dice que en ningun momento los taxis en servicio han de superar la cota mxima M AX_CO_H
de gramos de CO2 generados en una hora, y que en un da la cantidad de gramos de CO2 emitidos no
puede superar la cota M AX_CO_D. Con el nmero T de taxis disponibles es fcil superar ambas
cotas. zona, tenemos una tabla semanal en la que, para cada zona z, dia d y hora h se tiene una
estimacin del nmero de servicios (Sz,d,h ) que se suelen originar en esa zona, para cada hora del da.
Para modelar la demanda esperada de taxis tenemos una tabla semanal en la que, para cada da d y
hora h se tiene una estimacin del nmero de servicios (Sd,h ) que se suelen realizar.
El objetivo es decidir de forma dinmica los taxis que han de circular por el rea metropolitana, de
forma que se minimicen los niveles de contaminacin diaria (nunca se pueden superar los lmites) y se
maximice el nmero de servicios realizados (pero podemos dejar usuarios sin servir, si aadir servicios
implica superar los lmites de contaminacin). Se nos plantean las siguientes alternativas:
a) Queremos utilizar A*. Definimos el estado como la asignacin de taxis a horas del da. El estado
inicial consiste en asignar de forma ordenada a cada taxi un nmero mnimo de servicios N S
distribuidos de forma aleatoria en las horas de la semana. Tenemos un operador que asigna un
nuevo servicio a un taxi t en un dia d y hora h determinados, el coste sern los gramos COt
emitidos en los 15 minutos del servicio. Como funcin heurstica usamos la suma del numero de
servicios estimados en la tabla de demanda y que aun no hemos servido, o infinito si no se supera
la cota Sd,h .
b) Queremos utilizar Hill Climbing, donde se genera una solucin inicial asignando al azar suficientes
taxis a servicios hasta llegar a servir toda la demanda estimada en cada hora. Los operadores de
modificacin de la solucin consisten en intercambiar dos taxis entre servicios que pertenezcan a
horas diferentes, y eliminar un servicio asignado a un taxi (siempre que no quedemos por debajo
del lmite N S de servicios mnimos asignados a ese taxi). Como funcin de evaluacin usaremos el
sumatorio de los gramos de CO2 emitidos por todos los taxis asignados a servicios en la solucin
actual.
Comenta cada una de las posibilidades indicando si resuelven o no el problema y qu ventajas e
inconvenientes tiene cada una de ellas. Justifica la respuesta.
15. El Ministerio de Sanidad y Consumo espaol quiere mejorar el sistema de asignacin de plazas de
mdicos a centros hospitalarios. Cada mdico mi tiene una especialidad, acepta un sueldo mnimo
determinado (P mi ) y acepta una distancia mxima a recorrer entre su casa y su trabajo (Dmi ).
Cada centro ci dispone de xj plazas nuevas por cada especialidad j. El ministerio paga cada plaza de
especialidad j a un precio mximo determinado (Pj ), y dispone de un mapa de distancias entre las
viviendas de los mdicos y los centros hospitalarios.
Se quiere asignar mdicos a centros de manera que se cubra el mximo nmero de plazas nuevas.
Supondremos que el nmero de mdicos que solicitan plaza es mucho mayor que el numero de plazas.
Se nos plantean las siguientes formas de solucionar automticamente este problema:
a) Queremos usar satisfaccin de restricciones donde las variables son las plazas a cubrir, y sus
dominios son el conjunto de mdicos solicitantes mi . Las restricciones son la especialidad, el
sueldo y la distancia convenientes para los mdicos y los centros.
10.1 Bsqueda
115
b) Queremos utilizar A* de manera que se pueda asignar un mdico a una plaza (si las especialidades
son las mismas y si el sueldo y la distancia son convenientes), y desasignar un mdico de una
plaza, ambas operaciones con coste 1. La funcin heurstica h que se pretende usar es el numero
de plazas cubiertas.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
16. Tenemos un sistema P2P que utiliza un mecanismo centralizado para asignar a cada cliente qu otros
clientes son los que le envan las partes del fichero que le faltan. Cada cliente calcula una lista con los
retardos medios de transmisin a cada uno de los clientes que conoce (en milisegundos). El mecanismo
centralizado conoce el ancho de banda disponible de cada cliente tanto de subida como de bajada (en
Kb/s) para el fichero que se quiere transmitir. Cada cierto tiempo el mecanismo centralizado distribuye
a los clientes con qu otros clientes debe conectarse para recibir partes del fichero y qu ancho de banda
dedicar. Para cada cliente conocemos qu partes del fichero tiene, por lo que podemos saber si puede
enviar o no a un cliente. La idea es que minimicemos el tiempo de retardo total de las transmisiones
y utilicemos el mximo ancho de banda de bajada disponible de cada cliente.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
a) Queremos utilizar A de manera que recorremos la lista de clientes en un orden preestablecido. El
estado es la asignacin que hemos hecho de clientes y sus anchos de banda a los clientes recorridos.
Utilizamos como operador asignar a un cliente uno de los que conoce (siempre que tenga partes
del fichero que el cliente actual no tenga) y su mximo ancho de banda de subida al cliente actual,
cuando el ancho de banda de bajada del cliente actual es superado por la suma de los anchos de
banda de subida de los clientes asignados pasamos al siguiente cliente. Evidentemente una vez
asignado un cliente para transmitir partes del fichero no lo podemos asignar ms veces. El coste
del operador es el retardo del cliente asignado. La funcin heurstica es la suma para los clientes
que quedan por recorrer de los retardos a los clientes que conocen.
b) Queremos utilizar bsqueda local generando una solucin inicial en la que cada cliente recibe de
todos los clientes que conoce que tienen partes del fichero que le faltan con un ancho de banda
de 1 Kb/s. Como operadores tenemos aumentar o disminuir el ancho de banda de un cliente que
transmite a otro en 1 Kb/s. La funcin heurstica es la suma para cada cliente de los retardos de
los clientes que le transmiten con un ancho de banda superior a 0 Kb/s.
17. Se quiere planificar cmo componer S servicios Web en un nico servicio de orden superior (metaservicio). Cada servicio Web usa un conjunto de agentes informticos que deben ejecutarse en un orden
especfico para cumplir la tarea que realiza el servicio, estos agentes pueden trabajar en paralelo. Se
supone que la accin que realiza cada agente tiene la misma duracin (un paso) y hay que tener en
cuenta que un servicio puede necesitar un mismo agente en diferentes pasos de su ejecucin. Se dispone
de un agente de cada tipo, teniendo un total de A agentes. El meta-servicio se considera completo
cuando se haya completado cada servicio que lo compone. Se plantean las siguientes alternativas para
minimizar el nmero total de pasos de ejecucin del meta-servicio:
a) Queremos utilizar A*. Definiremos el estado como la asignacin de pasos de los S servicios individuales a uno de los A agentes en cada paso del meta-servicio. El estado inicial es tener un nico
paso del meta-servicio donde ninguno de los agentes tiene un servicio asignado.
Los operadores de cambio de estado consisten en:
1) Asignar el primer paso no ejecutado de alguno de los servicios a un agente libre en el paso
actual del meta-servicio, con coste uno
2) Aadir un paso nuevo al meta-servicio, con coste uno
116
18. En la pasarela Gaud han de organizar diez desfiles para diez diseadores, dos por da, sabiendo que
algunos diseadores se niegan a desfilar el mismo da que algn otro. Se han de asignar las y los
modelos a los desfiles (m por desfile) sin que la misma persona desfile ms de tres veces en total. Cada
diseador tiene tambin unas restricciones de altura y peso para sus modelos. Los organizadores de la
pasarela han de pagar a los modelos y cada uno tiene su tarifa por participar en un desfile. Obviamente,
los organizadores quieren pagar lo menos posible. La organizacin se plantea tres estrategias distintas
para resolver el problema de la pasarela:
a) Usar un algoritmo de bsqueda local intentando minimizar el coste de la pasarela. La funcin
heurstica es la suma de las tarifas de los que participan en los desfiles mas una constante K por
cada restriccin entre diseadores o modelos que no se cumpla. La solucin de partida coloca dos
diseadores cualesquiera en cada uno de los das y m modelos por desfile. Los operadores de cambio
de estado son intercambiar_desfile, que intercambia los das en que desfilan dos diseadores,
aadir_modelo a un desfile concreto, quitar_modelo de un desfile e intercambiar_modelo entre
dos desfiles.
b) Resolvemos primero el problema de asignar los diseadores a los desfiles mediante un algoritmo de
satisfaccin de restricciones. A partir de esa asignacin usamos el algoritmo de A para solucionar
la asignacin de los modelos a los desfiles. El estado es una asignacin parcial de modelos a
desfiles. Utilizamos como operador aadir_modelo a un desfile concreto que comprueba que
no haya ms de m modelos en el desfile y que se cumplan las restricciones del diseador e
intercambiar_modelo entre dos desfiles que tambien comprueba las restricciones del diseador,
el coste del operador asignar es la tarifa del modelo asignado, la del operador intercambiar es la
del modelo mas caro de los dos. Como funcin heurstica usamos el nmero de modelos que falta
incluir en los desfiles multiplicado por la tarifa del modelo mas caro.
c) Usar un algoritmo de satisfaccin de restricciones. Primero resolver el problema de asignar modelos a cada uno de los desfiles, teniendo en cuenta las restricciones de cada diseador, y luego,
una vez determinada la composicin de cada desfile, montar el calendario (qu dos desfiles tocan
cada da) teniendo en cuenta que no se emparejen dos diseadores que no se pueden ver y que no
haya modelos que desfilen ms de tres veces.
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
19. Queremos transmitir X Kbits entre dos mquinas MI y MF , para ello hemos de establecer C canales
de comunicacin que han de atravesar N mquinas (M1 , M2 , ... MN ) que hacen de puntos intermedios
(C N ), los X Kbits los dividimos a partes iguales por cada canal. Conocemos la velocidad en kbps
del canal que se puede establecer entre cada par de mquinas (incluidas MI y MF ), queremos que la
velocidad media de un canal sea como mnimo V Kbps y que un canal no atraviese ms de P mquinas.
10.1 Bsqueda
117
Buscamos la solucin que conecte todas las mquinas sin que dos canales pasen por la misma mquina
(exceptuando MI y MF ) tardando lo menos posible en transmitir los X Kbits.
a) Queremos utilizar A . Definimos el estado como la asignacin de mquinas a canales. El estado
inicial consiste en asignar las mquinas MI y MF a cada canal. Tenemos un operador que asigna
una mquina a un canal y cuyo coste es la velocidad media del canal que empieza en MI , pasa
por la mquina y acaba en MF , solo podemos asignar una mquina a un canal si no excedemos el
valor P . Como funcin heurstica usamos la suma de las velocidades medias de todos los canales
que se obtienen poniendo cada mquina que queda por conectar como nico nodo intermedio
entre MI y MF .
b) Aplicar un algoritmo de satisfaccin de restricciones. Las variables son las mquinas, los dominios
son los canales donde podemos asignarlas. Supondremos que no tenemos en cuenta las mquinas
MI y MF ya que estarn asignadas a todos los canales. Como restricciones imponemos que un
canal no est asignado a ms de P mquinas y que la velocidad media mnima del canal que
incluye las mquinas asignadas sea mayor que V .
Comenta cada una de las posibilidades indicando si resuelven o no el problema, qu errores te parece
que tiene cada solucin y cmo se podran corregir, y qu ventajas e inconvenientes tienen cada una
de ellas. Justifica la respuesta.
20. Una empresa pesquera y conservera enva sus N barcos {bi } con capacidades para C(bi ) pescadores
a sus D destinos internacionales {di } (N > D) para 180 dias de pesca. Algunos de sus M pescadores
P
{pi } (M > C(bi )) son asignados a los barcos y son enviados a los destinos en el barco asignado. El
coste por marinero del viaje en el barco bi a un destino dj es Kb (dj , bi ). Cada pescador pi proporciona
a la empresa una ganancia de g(pi ) euros/da en media y cuesta a la empresa k(pi ) euros/da en media.
La empresa requiere una planificacin que cubra todos sus destinos sin prdidas.
En los siguientes apartados se proponen diferentes alternativas para algunos de los elementos necesarios
para plantear la bsqueda (solucin inicial, operadores, funcin heurstica). Comenta la solucin que se
propone respecto a si es correcta, es eficiente, y es mejor o peor en comparacin con otras alternativas.
Justifica todas las respuestas.
a) Aplicar bsqueda local. La solucin inicial consiste en: 1) asignar secuencialmente N divD barcos
a cada destino, repartiendo los N modD restantes equitativamente entre los primeros N modD
destinos; 2) asignar aleatriamente C(bi ) pescadores a cada barco bi . Los operadores son: cambiar
el destino de un barco (y el de todos sus pescadores) e intercambiar dos pescadores entre dos
barcos de destinos diferentes. Como funcin heurstica usamos:
h0 (n) =
D
X
Kb (di , bj ) + 180
i=1 bj Asig(di ))
pi O(bj )
donde O(bj ) es la asignacin de marineros del barco bj (|O(bj )| C(bj )) y Asig(di ) son los barcos
asignados al destino di .
b) Aplicar satisfaccin de restricciones. Las variables son todos los posibles pares < pi , dj > (pescador, destino). Todas las variables tienen como dominio el conjunto {bi , undef }. El primer valor
denota que el barco bi se asigna al destino y que el pescador llegar en l. El segundo valor denota
que el pescador no viaja al destino. Las restricciones son:
R1 : i |O(bi )| C(bi )
R2 :
N
X
j=1 pi O(bj )
(k(pi ) g(pi )) 0
118
10.2 Representacin
1. Dentro de la representacin del conocimiento basada en Frames Que caractersticas debe cumplir una
relacin para que sea transitiva? Pon un ejemplo.
2. Dada la red de frames de la figura, responde a las siguientes preguntas, justificando tu respuesta:
A1
sA1
sA
A2
sA2
a) Suponiendo que tengamos un slot sA en el frame A y un slot sA1 en el frame A1. Dada una
instancia iA del frame A Cmo podemos obtener el valor del slot sA1?
b) Suponiendo que tengamos un slot sA en el frame A y un slot sA2 en el frame A2. Dada una
instancia iA2 del frame A2 Cmo podemos obtener el valor del slot sA?
c) Define un mtodo en A con un parmetro p, que tiene el mismo tipo que el rango del slot sA, que
retorne todas las instancias de A1 y A2 que tienen el valor p en el slot sA.
d) Suponiendo que tenemos una relacin de usuario r_A2_B definida entre el frame A2 y el frame B,
cuya inversa es r_B_A2. Define un slot sB que, para una instancia de B, nos de todas las instancias
de A2 con las que est relacionado mediante r_A2_B, que tengan en el slot sA el mismo valor que
alguna instancia del frame A1
e) Supongamos que definimos una relacin r_A1_A2 que permite la herencia de los slots sA1 y sA2.
Define esta relacin. Esta relacin te permitira implementar de forma ms sencilla el slot sB del
apartado anterior? Por qu?
3. Nuestra base de conocimientos consta de las clases A y B que tienen, respectivamente, los slots que
aparecen en la figura siguiente:
A
slotA1
slotA2
B
slotB1
slotB2
a) Qu hay que hacer para que la clase A herede el slotB1 de la clase B? posibilidades Describe
detalladamente todas las alternativas que se te ocuu mecanismo de los que has descrito te parece
el ms adecuado.
b) Supn que tenemos n instancias directas de A y m instancias directas de B con n>m y que
A hereda el slotB1 de B. Explica en qu circunstancias es cierta la afirmacin siguiente las n
instancias de A tienen el atributo slotB1. Considera las distintas posiblilidades que has dado en
el primer apartado.
c) Nos hemos enterado de que la clase A y la B son ambas subclases de la clase C. Cambiaras
alguna de las respuestas anteriores teniendo esta informacin? Justifcalo.
10.2 Representacin
119
d) Hemos de ubicar un mtodo que liste todos los valores distintos del slotB1 que tienen las instancias
de A y de B. Dnde lo colocaras? Justifcalo.
4. La empresa AMC Entertainment quiere ampliar los servicios que presta y ha decidido construir una
aplicacin que soporte consultas complejas sobre la gran cantidad de vdeos que almacena. La siguiente
figura muestra la ontologa bsica de esta nueva aplicacin y algunos de los descriptores que han
considerado necesarios.
Nombre
Calificacion
Duracion
Color
Video
Productora
Persona
Nacionalidad
Director
Nombre
Fecha nacimiento
Actor
a) La empresa sabe que los vdeos pueden estar clasificados por distintos criterios, como por ejemplo,
el tipo de programa (pelcula, documental, serie, deporte, noticias, ...), el gnero (drama, comedia,
accin, histrica, ...), su temtica (naturaleza, noticias generales, historia, ciencia, ...), etc. Ahora
bien, no saben si merece la pena hacer una subclasificacin de los vdeos, incluyendo todas las
subclases que haga falta, o es suficiente con incluir en el frame VIDEO tres slots, tipo, gnero,
temtica y ya est. Cul de las dos alternativas te parece ms aconsejable? Justifica la respuesta.
b) Define, usando el lenguaje visto en clase, las relaciones necesarias para saber quin es actor de
un vdeo, quin es el director y quin dirige a un actor.
c) La empresa considera que la nacionalidad de un vdeo es, directamente, la de su productora.
Como mnimo hay dos mecanismos razonables para que un vdeo asuma esa nacionalidad:
por HERENCIA, que se obtiene cuando se consulta la nacionalidad del vdeo.
por COPIA en el momento en que se relacionan el vdeo y su productora.
Implementa completamente ambas opciones y comenta, brevemente, las ventajas y desventajas
de cada una de ellas.
d) Piensan que una consulta frecuente ser la de querer todos los vdeos del director X, del perodo
Y y del gnero G. Escribe el mtodo correspondiente indicando dnde lo ubicaras. Cambiara
la ubicacin del mtodo en funcin de las dos posibilidades ontolgicas del apartado a)? Justifica
la respuesta.
5. La siguiente red de frames representa una parte de las diferentes entidades necesarias para definir
historias
Vinculo
Personaje
Personaje
Humano
Personaje
no humano
Vinculo
Afectivo
Amistad
Suceso
Vinculo
Familiar
Parental
Enemistad
Amor
Fraternal
Pelea
Encuentro
120
6. Dada la siguiente red de frames, responde a las siguientes preguntas, justificando tu respuesta:
r_A_A
r_B_A
B2
slB
B1
A1
A2
A3
slA2
A4
slA4
r_A2_A4
a) Tenemos la instancia iA1 que es instancia de A, en que circunstancias tiene los slots slA2 y
slA4?
b) Es la relacin r_A_A transitiva? Lo podra ser la relacin r_B_A?
c) Puede tener la relacin r_A2_A4 slots heredables?
d) Como habra que definir la relacin r_B_A para que el slot slA4 se pudiera obtener por herencia
en las instancias de B? y para obtener el slot slB en las instancias de A?
7. Una empresa de mensajera quiere gestionar los envos que realiza. La siguiente ontologa muestra los
elementos ms importantes que maneja:
Envo
Paquete
Cliente
Correo
Empresa
Almacn
Particular
Centro
Reparto
Centro
Distribucin
Para calcular el coste de los envos se aplican tarifas distintas en funcin tanto del tipo de envo como
de la categora del cliente emisor y de la distancia entre los centros de reparto asociados al cliente
emisor y al receptor. El sistema dispone de tablas de tarifas y de distancias entre almacenes.
a) Aade lo necesario para que se pueda representar qu cliente hace cada envo y qu cliente lo ha
de recibir. Aade lo necesario para que se pueda calcular el coste de un envo concreto.
10.2 Representacin
121
b) Un envo llega a un centro de reparto origen y puede pasar por varios de distribucin intermedios
hasta llegar al centro de reparto destino en que lo recoger el cliente receptor. El envo de paquetes
es especialmente crtico para la empresa de mensajera. Cada vez que un envo tipo paquete
llega a un almacn, el operario informa al sistema de que el paquete ha cambiado de ubicacin:
ahora se encuentra en ese almacn y ha dejado de estar en el almacn anterior en la secuencia
de almacenes recorridos. Cuando el envo ha sido recogido por el cliente destinatario, se anota
convenientemente este acontecimiento en el sistema. Qu haras para que se pudiera recuperar la
ruta que ha seguido el envo? Describe detalladamente tu propuesta, definiendo completamente
todos los elementos que deban incorporarse a la representacin.
c) Desde que un paquete entra en el centro de reparto origen y hasta que finalmente lo recoge
el cliente destinatario queremos que tenga asociado un nmero de telfono que corresponda al
nmero de telfono del almacn donde est ubicado en el momento de consulta. Cmo debe
modificarse la representacin para que el sistema pueda deducir esta informacin? Un mecanismo
de herencia sera vdido?
d) Define el mtodo inventario que, para un almacn, haga un listado de los envos de un determinado
tipo que tiene asignados en el momento de la consulta, indicando el nombre del cliente que ha de
recibirlo y si el almacn es el centro de reparto origen, el centro de reparto destino o un centro
intermedio. Ubica adecuadamente el mtodo. Define lo que creas necesario para que se pueda
implementar el mtodo. Existe algn problema con lo definido en el apartado b? Es heredable
este mtodo?
8. La Federacin Catalana de Natacin desea gestionar toda la informacin relacionada con las competiciones de natacin mediante un sistema basado en frames. Los conceptos bsicos que maneja son:
Nombre
Entidad
Club
Razn Social
Identificador
Telfono
rbitro
Num. Registo
Categora
Evento
Persona
Direccin
F. Nacimiento
Cronometrador
Nadador
Num. federado
Num. Registo
Prebenjamn
Competicin
Prueba
Serie
Nombre
Lugar
Fecha
Hora
Categora
Distancia
Estilo
Sexo
Nmero
Absoluto
Benjamn
Infantil
Alevn
Cada competicin tiene un nombre que la identifica (Trofeo Sant Jordi, Jornada n.3 Liga Infantil,
...) y est organizada en pruebas segn categoras de los nadadores (pre-benjamn, benjamn, alevn,
infantil, jnior, absoluta), estilo, distancia y sexo. Cada prueba puede tener una o ms series, dependiendo del nmero de nadadores que tienen que nadarla (en cada serie puede nadar un mximo de 8
nadadores). Para cada competicin se asigna un jurado que consta de 4 rbitros (el juez rbitro, el
juez de salidas, el juez de llegadas y el secretario) y N cronometradores (el jefe de cronometradores y
entre 3 y 8 cronometradores).
a) Define las relaciones necesarias para identificar el juez rbitro de cada competicin, las pruebas
de cada competicin y los nadadores de cada serie. Esta ltima relacin debe controlar que no se
asigne a una serie un nadador de un club que no figura como club participante en la competicin
correspondiente (aade lo que sea necesario).
b) Define un mtodo, con un parmetro, que nos permita obtener los nombres de todos los nadadores
de una determinada categora que pertenecen a un club concreto y por cada nadador nos indique
122
9. El anlisis de una organizacin como una universidad nos ha permitido identificar, entre otros, el
siguiente conjunto de frames y sus relaciones jerrquicas.
Unidad
Estructural
Departamento
Centro
Asignatura
Instituto
Titulacion
T_Grado
Persona
Profesor
Estudiante
PAS
T_Tecnica
Nivel
Nivel=grado
T_Superior
T_Postgrado
T_Master
Nivel=postgrado
T_Doctorado
Tenemos que una universidad se compone de unidades estructurales que podemos clasificar en departamentos, centros docentes e institutos de investigacin. Por otro lado, tambin se han identificado
tres categoras de personas miembros de la universidad: profesores, estudiantes y personal de administracin y servicios. Y en ltimo lugar, una universidad oferta titulaciones que pueden ser de grado o de
postgrado. Dentro del primer tipo encontramos las titulaciones tcnicas y las titulaciones superiores y
dentro del segundo tenemos los masters y los programas de doctorado.
a) A partir del diagrama de frames descrito anteriormente, incorpora y define todo lo necesario para
que se pueda determinar:
1) A qu titulaciones pertenece una asignatura (la misma asignatura puede pertenecer a ms
de una titulacin del mismo centro),
2) Qu titulaciones imparte cada uno de los centros docentes (asumimos que una titulacin es
impartida por un nico centro),
3) En qu centro docente se imparte una asignatura,
4) A qu departamento pertenece un profesor,
5) Quin es el profesor responsable de una determinada asignatura. Para esta cuestin hay que
tener en cuenta que un centro encarga docencia a algunos departamentos y, por tanto, el
profesor responsable de una asignatura ha de pertenecer necesariamente a un departamento
que tenga encargada docencia por parte del centro en el cual se imparte la asignatura.
b) Queremos un listado que, dado un centro y una de sus titulaciones, nos indique qu asignaturas
pertenecen a esa titulacin y para cada una de ellas quin es el profesor responsable y a qu
departamento pertenece.
Incorpora y define todo lo necesario para que se pueda obtener esa informacin. Justifica las
decisiones tomadas.
c) Se nos plantea la necesidad de que una asignatura herede el nivel de la titulacin a la que
pertenece. Analiza si eso es posible. En el caso de que consideres que s es posible, modifica lo
necesario y detalla cmo funcionara el mecanismo de herencia.
10.2 Representacin
123
Alternativamente a este mecanismo, se podra considerar la existencia de un slot nivel en asignatura cuyo valor fuera el mayor de los niveles de las titulaciones a las que pertenece (asumimos
que grado<postgrado). Define todo lo necesario para implementar esta otra opcin.
10. Tenemos tres frames A, B, C y las definiciones de las siguientes relaciones:
Dominio
Rango
Cardinalidad
Inversa
Transitiva
RAB
A
B
N
R1
AB (1)
no
RBC
B
C
1
R1
BC (N)
no
RCC
C
C
1
R1
CC (1)
no
124
13. Foursquare es una red social que permite compartir localizaciones entre usuarios, de manera que puede
servir como un sistema de geolocalizacin y como un sistema para recomendar lugares que se visitan con
frecuencia. Los usuarios de este servicio se pueden categorizar en usuarios espordicos, solo comparten
lugares de vez en cuando, y los que marcan tendencia (trenders), que comparten continuamente los
lugares por los que pasan. Tambin hay empresas que se promocionan y comparten su localizacin
con los usuarios para atraer ms pblico.
Los lugares que hay en el servicio se pueden clasificar segn su localizacin geogrfica en lugares urbanos (ciudades, pueblos, urbanizaciones) y naturaleza (montaa, playa, ...). Estos tambin se pueden
clasificar segn su temtica en lugares de restauracin (bares, restaurantes), ocio (cines, discotecas,
teatros, musica, ...), cultura (museos, conciertos, bibliotecas), turismo (monumentos, edificios, lugares
pintorescos, playas, ...), compras (ropa, alimentacin, libros, ...), etc.
Finalmente, tambin se representan las visitas de los usuarios a los lugares, para las cuales registra
la fecha y hora de la visita y el tiempo que se ha estado en el lugar. Las visitas se clasifican en cortas
y largas segn si su duracin es mayor o menor a dos horas.
a) Define completamente las siguientes relaciones:
Recomienda, entre usuario y lugar, indicando que el usuario recomienda el lugar
Amigo, entre usuarios, indicando que los usuarios tienen una relacin de amistad
Realiza, entre usuario y visita, indicando que el usuario ha realizado una visita y al lugar,
entre visita y lugar, indicando que la visita se realiza al lugar
b) Define el slot seguidores, en usuario que retorne todos los amigos que han visitado alguno de los
lugares que ha recomendado.
c) Define la relacin ahora entre usuario y lugar, indicando que el usuario est actualmente en ese
lugar. Define un slot estan_aqu que se actualice con la lista de sus amigos que estn en ese lugar
cuando se crea la relacin ahora y que sea vaca cuando se destruye. Que ventajas/inconvenientes
tendra el usar un mtodo en lugar del slot propuesto?
d) Define el slot gratis en lugar, indicando si el lugar es o no gratuito. Define lo necesario para que el
concepto visita herede este slot, indicando que la visita ha sido gratuita. Define el slot sin_blanca
en usuario que sea cierto si ms de la mitad de las visitas del usuario han sido gratuitas.
14. La compaa de subastas on-line eBay quiere crear aplicaciones para poder tratar todas las transacciones que realizan sus usuarios y como paso inicial quiere definir una ontologa que describa toda la
informacin que maneja.
10.2 Representacin
125
El primer concepto que quiere usar es el de usuario, que puede especializarse en vendedor y comprador
(un usuario puede pertenecer a ambas categoras). El segundo es el de producto, que puede clasificarse
en electrnica (ordenadores, cmaras, consolas, mviles, ...), coleccionables (monedas, sellos, comics,
...), entretenimiento (cine, msica, ...), motor (coches, motos, barcos, ...), juguetes (radio control,
trenes, infantiles, ...), ... El tercero es la subasta, que puede especializarse en subastas rpidas (menos
de 24 horas) y subastas largas. El ltimo es la puja, que representa que un usuario comprador ha
pujado en una subasta cierta cantidad de dinero.
a) Estan considerando las siguientes relaciones, la relacin abre entre vendedor y subasta, la relacin
vende entre subasta y producto, la relacin enva entre comprador y puja y la relacin oferta entre
puja y subasta. En una subasta se vende un nico producto que, si no se adjudica a nadie, no se
puede volver a subastar. Define completamente estas relaciones utilizando el lenguaje de frames
visto en clase.
b) Cuando un vendedor quiere vender un producto, ha de crear su descripcin en eBay, es decir,
primero ha de ponerlo a la venta dando una descripcin para luego poder subastarlo. Define la
relacin en venta entre vendedor y producto. Define el slot pendientes en vendedor que retorne
el nmero de productos que un vendedor an no ha subastado.
c) Una subasta tiene una fecha de inicio, una fecha de final y un precio inicial. Una puja tiene una
cantidad ofrecida y una fecha. Asumiendo que el mtodo de subasta es al alza, define lo necesario
para que se compruebe que una puja sea correcta, es decir, que una puja ofrezca una cantidad
mayor que la ltima que se ofreci.
d) Los usuarios vendedores tienen un slot que indica su indice de fiabilidad (cmo es el producto real
respecto a lo que dice en su oferta) que es un valor entero entre 0 y 5. Modifica lo necesario para
que una subasta herede el ndice de fiabilidad de su vendedor. Sera posible redefinir la relacin
vende para heredar este slot en producto? Explica tu respuesta.
e) Implementa un mtodo envos que nos retorne una lista con el identificador de los compradores
que han ganado las subastas de un da concreto junto con el identificador de los productos que
han comprado. Indica donde se definira este mtodo, aadiendo los elementos que sean necesarios
a la representacin.
126
11. Planificaci
1. Traducir el siguiente modelo del problema del mundo de los bloques de una codificacin STRIPS a
una codificacin en PDDL.
Operadores:
OP: pick-up(x):
PRE: clear(x),ontable(x),handempty().
DEL: clear(x),ontable(x),handempty().
ADD: holding(x).
OP: put-down(x):
PRE: holding(x).
DEL: holding(x).
ADD:clear(x),handempty(),ontable(x).
OP: stack(x,y):
PRE: holding(x),clear(y).
DEL: holding(x),clear(y).
ADD: clear(x),handempty(),on(x,y).
OP: unstack(x,y):
PRE: on(x,y),clear(x),handempty().
DEL: on(x,y),clear(x),handempty().
ADD: holding(x),clear(y).
Problema:
clear(A),clear(B),clear(E),clear(C),clear(D),ontable(F),ontable(B),
ontable(E),ontable(C),ontable(D),on(A,F),handempty().
on(E,F),on(F,C),on(C,B),on(B,A),on(A,D).
2. Tenemos un vector de tres posiciones. Queremos crear un modelo de dominio que permita darle a un
planificador una configuracin inicial de valores del vector (ej: |a|b|c|) y una configuracin final de esos
valores en el vector (ej: |c|b|a|) y que un planificador estilo Fast Forward encuentre los movimientos
necesarios a realizar.
3. Un equipo de investigadores en robtica necesita dotar a su robot de la capacidad de planificar acciones
para poder probar su habilidad de reconocimiento de objetos y colores. Para empezar las pruebas
quieren hacer un planificador simple que le diga al robot cmo apilar y desapilar vasos en una mesa.
Los vasos pueden ser de dos colores: blanco y negro. En la mesa se han pintado cuatro casillas, dos
blancas y dos negras. Las restricciones que se imponen son las siguientes:
El robot solo puede usar uno de sus brazos, y coger un vaso a la vez.
127
128
Estado final
Estado inicial
c) Ahora supongamos que hemos pintado en la mesa un tablero de 24 24 casillas, la mitad blancas
y la mitad negras, y que tenemos 600 vasos blancos y 600 vasos negros. Cual seria el factor de
ramificacin de vuestros operadores? Se os ocurre una forma de mejorar el modelo que habis
hecho? Razonad vuestra respuesta (no hace falta que cambiis vuestro modelo, slo que indiquis
que cambios habra que hacer.).
4. Como parte de la resolucin de un desastre natural provocado por un monzn en China, hemos de
resolver el problema de logstica producido por el derrumbe de todos los puentes en la confluencia
de los rios Xi y Beijang. Tenemos varios camiones que han de transportar vveres y material diverso
entre 3 ciudades (Zhaoging, Gaoming y Foshan). Disponemos de una flota limitada de ferries que han
sobrevivido al monzn, para llevar los camiones de una ciudad a otra. Pero estos ferries solo puede
llevar cada vez como mximo dos camiones a bordo. Nos piden hacer un planificador simple que genere
un plan para mover los camiones de su ciudad origen a su ciudad destino por el rio mediante los ferries
disponibles.
a) Describe el dominio (incluyendo predicados, acciones, etc...) usando PDDL. Da una explicacin
razonada de los elementos que has escogido. Ten en cuenta que el modelo del dominio ha de
poderse extender a ms o menos ciudades y ms o menos ferries.
b) El jefe de logstica nos ha proporcionado una tabla con los camiones que hay que transportar entre
Zhaoging (Zh), Gaoming (Gm) y Foshan (Fs). Tambin nos dice que en este momento tenemos
slo un ferry disponible atracado en el puerto de Foshan. Nos pide que el planificador genere un
plan en el que el ferry acabe llevando todos los camiones a su ciudad de destino.
camion
c1
c2
c3
c4
c5
c6
c7
c8
origen
Zhaoging
Zhaoging
Zhaoging
Gaoming
Gaoming
Gaoming
Foshan
Foshan
destino
Gaoming
Foshan
Foshan
Zhaoging
Zhaoging
Zhaoging
Gaoming
Zhaoging
Describe este problema usando PDDL. Da una breve explicacin de cmo modelas el problema.
129
5. La FIB nos ha pedido una herramienta sencilla en que los alumnos puedan decir que asignaturas quieren
cursar en los ltimos semestres de la carrera y les haga un plan de matriculacin que, basndose en
las asignaturas que ya tienen cursadas, les diga de que asignaturas se han de matricular como mnimo
los prximos semestres para poder llegar a matricularse de las asignaturas que no se desean perder.
El sistema tendr conocimiento sobre las asignaturas del plan de estudios, sus pre-requisitos, sus precorequisitos (si los hay), las asignaturas que el alumno ya ha cursado y las asignaturas que el alumno
quiere cursar. El resultado es un plan de matriculacin que 1) refleja las asignaturas mnimas que el
alumno ha de matricular, 2) para cada asignatura, indica en que semestre ha de hacerla, 3) para todas
las asignaturas del plan se cumplen en todo momento los pre-requisitos y/o pre-corequisitos necesarios
para cursarlas
Para simplificar el problema, 1) no pondremos un lmite de crditos matriculables por semestre, 2) del
sistema de pre/co/pre-corequisitos solo modelaremos dos tipos de requisitos entre asignaturas
pre-requisito: Si una asignatura A es prerequisito de una asignatura B, para poder matricularse
de B se ha de haber cursado la asignatura A en un semestre anterior. Ejemplos de prerequisitos: PRO1BD, PRO1EDA,PRO2BD, PRO2EDA, BDIES, IESAS, ASECSDI,
M1PE, M2PE, ECSO, ICSO, AAA, EDAIDI, EDAIA, EDAPROP, EDALI,
EDATC, EDAPAR, SOPAR
pre-corequisito: Si una asignatura A es pre-corequisito de una asignatura B, para poder matricularse de B se ha de haber cursado la asignatura A en un semestre anterior o matricularla
en el mismo semestre que A (es decir, matricular A y B a la vez). Ejemplos de pre-corequisitos:
BD7PROP, PE7A, PROP7IA, PROP7LI, PROP7TC, PROP7A, PE7A
a) Describe el dominio (incluyendo predicados, acciones, etc.) usando PDDL. Da una explicacin
razonada de los elementos que has escogido.
b) Como primera prueba del sistema nos dan un alumno de la FIB que solo ha aprobado PRO1,
PRO2, EC, IES y EDA. Nos pide que el planificador genere un plan de matriculacin en el que
pueda llegar a cursar las asignaturas ECSDI, AA y PAR. Describe este problema usando PDDL.
Da una breve explicacin de cmo modelas el problema.
6. Hace aos la burbuja inmobiliaria y de infraestructuras junto a los delirios de grandeza de algunos
polticos provoc la creacin de mltiples aeropuertos distribuidos por la geografia espaola. Sin embargo la crisis econmica ha obligado ahora al Gobierno a tomar medidas y exigir a estos aeropuertos
un plan de viabilidad para evitar su cierre. Por eso los gestores de un pequeo aeropuerto de la costa
Mediterrnea nos piden participar en un proyecto piloto de automatizacin de la torre de control del
aeropuerto usando tcnicas de inteligencia artificial. En concreto nos piden un sistema automtico que,
cada media hora, recibe la lista de vuelos que estn pendientes de aterrizar o despegar del aeropuerto
(y en el caso de los pendientes de despegue, la puerta de embarque que ocupan) y ha de generar un
plan que diga en que orden han de despegar o aterrizar los aviones (y en el caso de los que aterrizan,
en que puerta de embarque han de desembarcar).
El aeropuerto dispone de dos pequeas terminales (A y B) con cinco puertas de embarque (A1, A2,
B1, B2 y B3). Dispone tambin de dos pistas para el despegue y aterrizaje de aviones (ps1 y ps2),
pero los fuertes vientos de la zona hacen que a veces no se pueda usar una de ellas. Nunca puede
haber dos aviones a la vez en la misma pista (por ejemplo un avin no puede aterrizar si hay otro
avin que acaba de aterrizar o un avin a punto de despegar; un avin no puede entrar en la pista
para despegar si hay otro a punto de despegar o un avin aterrizando que no ha salido de la pista).
Como las pistas estn muy cerca de las puertas de embarque y hay poco espacio para maniobrar, por
motivos de seguridad no se permite a un avin en tierra desconectarse de una puerta de embarque e
ir a una pista si la pista no est libre de aviones, ni a un avin que acaba de aterrizar dirigirse a una
puerta de embarque si esta tiene un avin).
Para simplificar el problema y no tener que modelar tiempos de despegue, aterrizaje o desplazamiento
entre pistas y puertas de embarque, aprovechando que el aeropuerto es tan pequeo (y que se han de
observar unas distancias de seguridad entre aviones) consideraremos que un avin que ha de despegar
solo puede estar o bien en la puerta de embarque, o bien en la pista a punto de despegar o bien ya
130
vuelo
IB0051
BA6136
AF0700
AL8860
SALIDAS
destino
Madrid
Londres
Lyon
Miln
puerta
A1
B1
B2
B3
vuelo
IB0121
VY0256
KL0333
LH4044
LLEGADAS
procedente de
Mlaga
Barcelona
Amsterdam
Berln
puerta
Describe este problema usando PDDL. Da una breve explicacin de cmo modelas el problema.
7. Una asociacin de fans de la serie britnica Doctor Who nos pide una aplicacin para movil que ayude
a los nuevos miembros de la asociacin a visionar los captulos de las diferentes temporadas de las
series Doctor Who (DW), Torchwood (TW) y The Sarah Jane Adventures (SJ) en el orden adecuado,
teniendo en cuenta que a menudo cruzan historias y subtramas entre ellas y que a veces las series se
cruzan por completo en captulos crossover (por ejemplo, en el final de la 4a temporada de Doctor
Who aparecen todos los personajes principales de las tres series).
La app ha de tener en cuenta, por un lado, los captulos de las tres series que el usuario ha visto
ya, y por el otro un listado de captulos que quiere ver en los prximos das, haciendo un plan de
visionado diario en el que se le recomiende en que orden ha de ver los captulos teniendo en cuenta
sus dependencias:
dependencias dentro de la misma serie: para cada temporada i de cada una de las series Sk, cada
captulo Sk : i j, (j > 1) tiene como predecesor el captulo previo Sk : i j 1 dentro de
la temporada (por ejemplo, DW:14 DW:15) y el primer captulo tiene como predecesor el
ltimo captulo de la temporada anterior (por ejemplo, TW:213TW:31). Cada temporada
de Doctor Who tiene 14 episodios (excepto la 4a temporada, que tiene 18). Cada temporada
de Torchwood tiene 13 episodios (excepto la 3a temporada, que tiene 5, y la 4a temporada, que
tiene 10). Las 4 primeras temporadas de The Sarah Jane Adventures tienen 6 captulos y la 5a
temporada tiene solo 3 captulos.
dependencias entre series: son dependencias entre pares de captulos de series diferentes. Por
ejemplo:
DW:23SJ:11
SJ:16DW:412
SJ:26DW:417
SJ:36DW:51
DW:613SJ:51
DW:213TW:11
TW:213DW:412
TW:35DW:417
DW:514SJ:41
TW:113DW:311
DW:413SJ:21
DW:418SJ:31
SJ:46DW:611
DW:313TW:21
DW:413TW:31
DW:418TW:41
TW:410DW:611
131
visto los captulos de la 1a y 2a temporada de la serie clsica de Star Trek, el planificador ha de
incluir en el plan de visionado todos los captulos de la 3a temporada (en el orden correcto) y
las dos primeras pelculas de Star Trek. universos ficticios donde las historias no solo pasan una
despus de la otra, sino tambin en paralelo, por lo que es bueno ver las historias ms o menos en
el orden en el que ocurren. Este fenmeno es muy tpico de algunas series que han tenido varias
subseries emitindose a la vez (Stargate, Star Trek, CSI, NCIS, Doctor Who/Torchwood...) y que
a veces incluso cruzan historias y subtramas entre ellas.
El resultado es un plan de visionado que lista los captulos mnimos que el usuario ha de ver para
llegar a ver los que quiere en las mejores condiciones, indicando para cada captulo en que da ha de
verlo. El sistema recomendar un mximo de tres captulos al da, y para todos los captulos dentro
del plan se ha de cumplir que sus predecesores se ven en el mismo da (antes del captulo en cuestin)
o en das anteriores. El plan de visionado no tiene porque llenar los tres slots de visionado cada da,
solo ha de intentar hacer un plan factible. Si el usuario tiene pocos captulos como objetivo el plan
puede llegar a ser un solo contenido al da unos pocos das.
a) Describe el dominio (incluyendo predicados, acciones, etc...) usando PDDL. Da una explicacin
razonada de los elementos que has escogido. Ten en cuenta que el modelo del dominio ha de
poderse extender no slo a ms o menos captulos y temporadas sin tambin a ms o menos
series (por si en el futuro se crean ms series paralelas) y a ms o menos das de visionado.
b) Para probar el sistema nos piden que nos centremos en las temporadas 3, 4 y 5 de Doctor Who,
las temporadas 2, 3 y 4 de Torchwood y las temporadas 1, 2 y 3 de The Sarah Jane Adventures,
que es donde hay ms lo de cruce de historias entre las series. Queremos simular a un usuario que
ha visto ya la la 2a temporada de Torchwood*, la 1a temporada de The Sarah Jane Adventures,
la 3a temporada de Doctor Who* y los primeros 11 captulos de la 4a . Durante la semana que
viene (7 das) quiere llegar a ver los tres primeros captulos de la 4a temporada de Torchwood.
Describe este problema usando PDDL, incluyendo las dependencias entre captulos que menciona
el enunciado. Da una breve explicacin de cmo modelas el problema.
*No hace falta modelar las temporadas 1 y 2 de Doctor Who o la temporada 1 de Torchwood,
asumimos que si ha visto una temporada tambin ha visto las anteriores.
8. Una coctelera de gran xito ha decidido ampliar el local para poder colocar muchas ms mesas y varias
barras en las que preparar los ccteles. Para poder controlar los pedidos en un local tan grande, han
decidido crear un sistema informtico que conecta a todo el personal en todo momento. Los clientes, en
vez de pedir en una de las barras, piden directamente en la mesa, donde un empleado entra el pedido
en una tablet. A partir de ah el sistema ha de planificar las tareas de barmans y camareros. Como ya
se ha dicho el local tiene ms de una barra, y en cada barra puede haber uno o ms barmans. Cada
cctel pedido por un cliente en una mesa es luego creado por cualquiera de los barmans (pero solo
uno, se debe evitar que dos barmans creen el mismo coctel para el mismo pedido). Supondremos que
un mismo cliente no pedir dos veces el mismo coctel. Una vez el barman ha creado un cctel lo deja
en su barra. En el local hay varios camareros, y cualquiera puede venir a coger el cctel de la barra,
ponerlo en su bandeja, llevarlo a la mesa y servirlo (cuidado, ha de saber a que persona de la mesa lo
ha de servir). Cada camarero puede llevar en todo momento como mximo tres ccteles en la bandeja
con la que se mueven por el local, y en un mismo viaje puede coger ccteles en ms de una barra y
servirlos en mesas diferentes. El objetivo del planificador es crear el plan en el que todos los pedidos
realizados han sido servidos.
a) Describe el dominio (incluyendo predicados, acciones, etc...) usando PDDL. Da una explicacin
razonada de los elementos que has escogido. Ten en cuenta que el modelo del dominio ha de
poderse extender no slo a ms o menos personal (barmans y camareros) sin tambin a ms o
menos barras y mesas (por si en el futuro se vuelve a ampliar el local).
b) Para probar el sistema nos piden que modelemos un local con tres barmans (Manuel, Jorge y
Alfonso), dos barras (Manuel y Jorge estn juntos en una de las barras), dos camareros (Rosita y
Camilo) y diez mesas (M1 a M10). Como ejemplo del tipo de pedidos nos dan la siguiente tabla:
132
cliente
Irene
Oscar
Aida
Berto
Pau
coctel
Mojito
SexOnTheBeach
Margarita
Daiquiri
Daiquiri
mesa
M1
M5
M7
M8
M8
cliente
Pep
Marta
Montse
Alex
Carla
coctel
TequilaSunrise
PiaColada
SanFrancisco
BloodyMary
Mojito
Describe este problema en PDDL. Por favor incluye una corta explicacin sobre como modelas el
problema.
9. La empresa de aplicaciones para movil SmartApps necesita nuestra ayuda para desarrollar el mdulo de
IA de su nueva app, ShareBath. En los pisos pequeos con un solo cuarto de bao suele haber muchos
conflictos sobre el uso del bao, especialmente por las maanas cuando todos tienen que lavarse y
arreglarse en un espacio pequeo. Por ello han pensado en una app para familias y estudiantes que
comparten piso de un solo bao que les ayude a planificar el orden en el que cada persona ha de hacer
sus tareas.
ducha, una delante del lavamanos con espejo y una en el sanitario. Cada persona se ha de duchar,
peinar y usar el sanitario. Otras acciones opcionales que dependen de la persona son afeitarse, secar
el pelo y maquillarse (las tres requieren el uso del espejo). Las acciones de peinar, secar el pelo y
maquillarse se deben hacer siempre despus de ducharse (si hay que secar el pelo, peinar es una accin
previa para desenredar el pelo y el peinado se acaba durante el secado). Cada persona tiene su propio
peine, toalla, maquina de afeitar y maquillaje, pero otras cosas se han de compartir como el sanitario,
la ducha, el lavamanos con espejo y el secador de pelo. Para las cosas que se comparten nos piden que se
modele explicitamente las acciones de coger y dejar ese recurso, evitando que la app recomiende cosas
incompatibles como dos personas secndose el pelo con el mismo secador o una persona afeitndose y
otra maquillndose delante del mismo lavamanos con espejo.
En el momento de registrarse en la app el usuario ha de hacer un inventario de los elementos del lavabo
que se comparten (sanitario, ducha, lavamanos con espejo, secador) y para cada individuo ha de decir
que tareas ha de realizar cada maana (pensad que no todos los hombres necesitan afeitarse, y que el
secador no lo usan solo mujeres, sino tambin hombres con el pelo largo). El resultado es un plan que
lista en que orden han de realizar sus tareas cada uno de los individuos dentro del bao compartido,
evitando conflictos. Solo se pide un orden de las tareas, no se tiene que modelar su duracin o hacer
una planificacin minuto a minuto.
a) Describe el dominio (incluyendo predicados, acciones, etc...) usando PDDL. Da una explicacin
razonada de los elementos que has escogido. Ten en cuenta que el modelo del dominio ha de
poderse extender no slo a ms o menos usuarios del bao sin tambin a ms o menos cosas
compartidas (por ejemplo baos con dos lavamanos o con dos secadores de pelo).
b) Para probar el sistema nos dan el caso particular de una familia numerosa de 7 personas que
comparte un bao con un sanitario, una ducha, dos lavamanos con espejo y un secador de pelo.
segundo secador que tenan se ha estropeado). En el momento del registro la familia nos ha pasado
la siguiente lista de tareas para cada individuo (cuidado, la lista no est ordenada).
persona
Juan
Montse
Pablo
Miguel
Jesus
Martina
Oscar
edad
48
45
22
19
17
14
12
tareas
afeitarse, ducharse, peinarse, usar sanitario
ducharse, maquillarse, secar el pelo, peinarse, usar sanitario
afeitarse, ducharse, secar el pelo, peinarse, usar sanitario
afeitarse, ducharse, peinarse, usar sanitario
ducharse, peinarse, usar sanitario
ducharse, secar el pelo, peinarse, usar sanitario
ducharse, peinarse, usar sanitario
Describe este problema usando PDDL. Da una breve explicacin de cmo modelas el problema.