Examen solucionado 2011-2012 (1er parcial) (2017)

Examen Catalán
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Gestión Aeronáutica - 2º curso
Asignatura IA - Inteligencia Artificial
Año del apunte 2017
Páginas 7
Fecha de subida 15/06/2017
Descargas 0
Subido por

Vista previa del texto

INTEL·LIGÈNCIA ARTIFICIAL – GESTIÓ AERONÀUTICA CURS 2011-2012 – 1er PARCIAL Cognoms i nom: _____________________ SOLUCIONS ______________________ 1.- (2 punts) Responeu de forma breu les següents qüestions: a) Què és un agent intel·ligent o racional? Un agent intel·ligent o racional és un programa/màquina que actua per aconseguir el millor resultat que es pugui segons un criteri d’èxit en un objectiu concret, Un agent intel·ligent està format per una arquitectura i un programa que no és un programa qualsevol. Perseguirem programes que en la mesura del possible reprodueixin un comportament racional a partir d’una petita quantitat de codi, en lloc d’un codi que contempli una gran taula de possibles estats d’entrada.
b) Respecte el problema de la representació del coneixement, què diu el Principi de la Representació? El principi de la representació proposat per en Patrick Winston ens diu que, en molts casos, un cop el problema s'ha descrit amb una representació adequada, el problema està quasi solucionat.
c) Quins camins expandeix primer l’algorisme de cerca en profunditat? I quins expandeix primer l’algorisme de cerca de cost uniforme? L’algorisme de cerca en profunditat expandeix primer els camins més profunds.
Per aconseguir-ho, l’algorisme insereix els camins expandits al principi de la llista de camins i en el següent pas sempre expandeix el primer camí de la llista.
L’algorisme de cerca de cost uniforme expandeix primer els camins amb menor cost acumulat. Per aconseguir-ho, l’algorisme utilitza una llista de camins ordenada segons el cost acumulat de menor a major i expandeix sempre el primer camí de la llista.
d) Quina és la diferència principal entre els algorismes GBFS i A*? L’algorisme de cerca GBFS (Greedy Best First Search) expandeix primer els camins que estima que són més propers a la solució segons la funció heurística h(n) que estima el cost per arribar a l’objectiu des del node n.
L’algorisme de cerca A* expandeix primer els camins que estima com a òptims segons la funció f(n)=g(n)+h(n), on g(n) és el cost acumulat fins el node n i h(n) és la funció heurística.
2.- (1.5 punts) En un aeroport, hem de distribuir els espais que ocuparan els serveis als passatgers dins d’una nova terminal. Un d’aquests serveis són les pantalles amb la informació dels vols. El plànol de la terminal s’ha dividit en àrees tal com es veu a la figura. Cadascuna d’aquestes àrees s’identifica per unes coordenades (x,y).
  Y  6                                      5                                      4                                      3                                      2                                      1           entrada        entrada           0  1  2     3  4  comerços  5  6  7     8  9  10  11  12  X  taulells de facturació    Es volen posar 4 pantalles d’informació i volem posar-les de tal forma que la suma de les distàncies (al quadrat) des de qualsevol àrea de la terminal a la pantalla més propera sigui mínima. La posició de les pantalles queda definida per les coordenades (x,y) de l’àrea en la que estan situades.
Plantegeu la solució a aquest problema resolent les següents qüestions: a) Quin tipus de cerca és el més adequat per resoldre el problema? La cerca local. Aquest és un problema d’optimització en el qual no hi ha un objectiu final determinat.
b) Què representaran els nodes en l’arbre de cerca? El nodes representen les posicions de les 4 pantalles. Els estats del problema corresponen a les coordenades de les posicions de les pantalles (x1,y1,x2,y2,x3,y3,x4,y4).
c) Què representaran les branques en l’arbre de cerca? Les branques representen modificacions en els valors de les coordenades de les posicions de les pantalles: sumar o restar 1 al valor d’una de les coordenades de les pantalles.
d) Quina serà la dimensió de l’espai d’estats del problema? La dimensió de l’espai d’estat és 8 perquè tenim 2 coordenades per cadascuna de les 4 pantalles. Els estats del problema contenen 8 valors.
e) Quin serà el factor de ramificació de l’arbre? La modificació dels valors de les coordenades es pot fer de diferents formes. La més senzilla seria sumar o restar 1 al valor d’una de les coordenades de les pantalles. En aquest cas, el factor de ramificació seria b=16.
També es podria permetre variar en més de 1 el valor de cada coordenada, o modificar més d’una coordenada cada vegada. En aquest cas, el factor de ramificació seria més gran.
f) Quina serà la funció heurística del problema? L’heurística del problema (el valor que volem minimitzar) és la suma de les distàncies al quadrat de totes les posicions de la terminal a la pantalla més propera.
La fórmula corresponent seria: h( E ) dist xi , y i , x p , y p 2 i xi xp 2 yi yp 2 2 i on (xp,yp) són les coordenades de la pantalla més propera a la casella (xi,yi).
3.- (1.5 punts) En la nova terminal, també cal fer l’assignació de portes als vols de les companyies que hi operen. La terminal té 30 portes i les companyies fan un total de 27 vols (per facilitar la feina, suposeu que els vols s’identifiquen amb un número que va del 1 al 27).
Cada vol té capacitat per un determinat nombre de passatgers i cada porta pot assumir un número màxim de passatgers. Per aquest motiu, hi ha vols que no poden sortir d’algunes portes i l’assignació s’ha de fer tenint en compte la següent informació: Les portes de la 1 a la 10 tenen capacitat per 150 passatgers.
Les portes de la 11 a la 20 tenen capacitat per 300 passatgers.
Les portes de la 21 a la 27 tenen capacitat per 450 passatgers.
Les portes de la 28 a la 30 tenen capacitat per 600 passatgers.
Els vols del 1 al 15 tenen 125 passatgers.
Els vols del 16 al 25 tenen 280 passatgers.
El vol 26 té 400 passatgers.
El vol 27 té 525 passatgers.
Plantegeu aquest problema resolent les següents qüestions: a) Quin tipus de cerca s’hauria d`implementar per resoldre aquest problema? La cerca per a satisfacció de restriccions.
b) Què representen i quines són les variables en aquest problema? Les variables del problema representen les 30 portes d’embarcament.
El conjunt de variables està format per: Variables={P1,...,P30} c) Què representa i quin és el domini dels valors en aquest problema? El domini dels valors representa als vols.
El domini del problema és: Domini={1,...,27} d) Què falta definir per acabar de plantejar el problema? Feu-ho.
Falten per definir les restriccions del problema.
Restriccions: No hi pot haver dues portes amb el mateix valor (vol) assignat: Pi ≠ Pj per i≠j Les portes de la 1-10 poden tenir assignats els vols del 1 al 15: Pi ≤ 15 per 1 ≤ i ≤ 10 Les portes de la 11-20 poden tenir assignats els vols del 1 al 25: Pi ≤ 25 per 11 ≤ i ≤ 20 Les portes de la 21-27 poden tenir assignats els vols del 1 al 26: Pi ≤ 26 per 21 ≤ i ≤ 27 e) Dibuixeu de forma esquemàtica l’arbre de cerca corresponent als 3 primers passos que faria l’algorisme per solucionar aquest problema (1 pas = expansió d’un node de l’arbre).
f) En l’arbre de cerca dibuixat a e), què representen els nodes? I les branques? Els nodes representen les variables que ja tenen un valor assignat. A més, als nodes es fa la comprovació de les restriccions sobre les variables que ja han estat assignades.
Les branques representen les assignacions de valors a les variables.
4.- (2 punts) Dues companyies (C1 i C2) fan una mateixa ruta, de forma que competeixen entre elles pel mateix mercat. Un canvi en el preu dels bitllets d’una d’elles té un gran impacte en la demanda de l’altra.
El benefici (B1 i B2) que obté cada companyia depèn dels seus preus i dels de la competència.
Aquest benefici ve donat per: B1 10 p1 p1 2 0 .5 p 2 B2 20 p2 2 p2 2 2 p1 on p1 i p2 són els preus dels bitllets de C1 i C2 respectivament.
Suposeu que sou els responsables de la política de preus de la companyia C1 i us heu assabentat que C2 planeja un canvi de preus. Davant aquesta situació, us voleu avançar i estudiar un possible canvi dels vostres preus per tal de reduir els possibles efectes que pugui tenir el canvi de preus en la vostra posició al mercat.
Plantegeu el problema com un problema de cerca amb adversaris, on l’heurística és la diferència de beneficis entre les companyies: H ( p1 , p2 ) B1 B2 Actualment, els preus dels bitllets són: p1=4€ i p2=9€. Per simplificar, suposeu que en cada revisió de preus, aquests només es poden pujar 1€, baixar 1€ o deixar igual.
a) Representeu l’arbre de cerca fins a una profunditat de 2. (Al node inicial l’arbre té profunditat 0) b) Apliqueu l’algorisme Minimax sobre l’arbre del punt anterior per decidir què li convé més a la companyia C1: Pujar el preu del bitllet? Baixar-lo? Mantenir-lo? Ajuda: Taules per fer el càlcul de B1, B2 i H(p1,p2) en funció de p1 i p2: B1 p1 3 4 5 8 25 28 29 p2 9 25,5 28,5 29,5 B2 10 26 29 30 p1 3 4 5 8 38 40 42 p2 9 24 26 28 B1‐B2 10 6 8 10 p1 3 4 5 8 ‐13 ‐12 ‐13 p2 9 1,5 2,5 1,5 10 20 21 20 Solució: A la companyia C1, li convé mantenir el preu donat que aquesta decisió és la que li garanteix el menor desavantatge respecte C2, quan aquesta modifiqui el seu preu.
5.- (3 Punts) Una empresa americana de transport de mercaderies per avió vol implementar un sistema basat en l’algorisme A* que li permeti optimitzar les rutes que realitza. Els avions de l’empresa han d’anar fent escales per proveir-se de combustible i l’objectiu és que el sistema sempre trobi la ruta més curta entre les ciutats d’origen i destí. El programa utilitza la distància en línia recta com heurística per trobar la ruta a seguir.
La xarxa de trajectes disponibles ve donada per la següent matriu de costos on el cost és la distància entre ciutats.
1 NY 1-Nova York 2-Miami 3-Chicago 4-Atlanta 5-Dallas 6-Phoenix 7-Denver 8-Seattle 9-San Francisco 10-Los Angeles 1750 1150 1200 2 MIA 1750 970 3 CHI 1150 950 1300 4 ATL 1200 970 950 5 DAL 6 PHO 7 DEN 1400 1050 950 8 SEA 9 SFA 10 LAN 1300 1150 1150 1400 1050 600 950 1550 1100 1550 600 1100 550 550 Es vol trobar la millor ruta per anar de Nova York a San Francisco.
a) Dibuixeu l’arbre de cerca (només fins una profunditat igual a 4) que representa els camins que es poden anar generant des de la ciutat de sortida. Considereu que s’eliminen els cicles i que el node arrel està a profunditat 0.
b) Genereu les llistes de camins corresponents a l’algorisme A* per calcular la ruta entre Nova York i San Francisco. Per a cada camí, doneu el valor de la funció de cost f(n). Elimineu cicles i camins redundants. Quan elimineu un camí redundant, indiqueu-ho d’alguna forma.
c) La trajectòria que trobi aquest agent, serà la més curta possible? Justifiqueu la vostra resposta.
Consells: dibuixeu-vos la xarxa amb les distàncies sobre els arcs que uneixen les ciutats utilitzeu els números identificadors de les ciutats o les abreviatures dels noms per treballar amb les llistes de camins Per poder calcular l’heurística, se us proporciona la distància en línia recta de totes les ciutats de la xarxa al destí San Francisco.
1 - New York 2 - Miami 3 - Chicago 4 - Atlanta 5 - Dallas 6 - Phoenix 7 - Denver 8 - Seattle 9 - San Francisco 10 - Los Angeles Distància a San Francisco 4150 4200 3000 3450 2400 1050 1550 1100 0 550 b) Iteració 0: NY 0 + 4150 = 4150 Iteració 1: NY-CHI NY-ATL NY-MIA 1150 + 3000 = 4150 1200 + 3450 = 4650 1750 + 4200 = 5950 Iteració 2: NY-ATL NY-CHI-DAL NY-CHI-ATL NY-MIA 1200 + 3450 = 4650 2450 + 2400 = 4850 2100 + 3450 = 5550 (camí redundant) 1750 + 4200 = 5950 Iteració 3: NY-ATL-DAL NY-CHI-DAL NY-ATL-CHI NY-MIA NY-ATL-MIA 2350 + 2400 = 4750 2450 + 2400 = 4850 (camí redundant) 2150 + 3000 = 5150 (camí redundant) 1750 + 4200 = 5950 2170 + 4200 = 6370 (camí redundant) Iteració 4: NY-ATL-DAL-PHO NY-ATL-DAL-DEN NY-MIA NY-ATL-DAL-CHI 3750 + 1050 = 4800 3400 + 1550 = 4950 1750 + 4200 = 5950 3650 + 3000 = 6650 (camí redundant) Iteració 5: NY-ATL-DAL-PHO-LAN NY-ATL-DAL-DEN NY-MIA NY-ATL-DAL-PHO-DEN 4350 + 550 = 4900 3400 + 1550 = 4950 1750 + 4200 = 5950 4700 + 1550 = 6250 (camí redundant) Iteració 6: NY-ATL-DAL-PHO-LAN-SFA NY-ATL-DAL-DEN NY-MIA 4350 + 550 = 4900 3400 + 1550 = 4950 1750 + 4200 = 5950 c) La trajectòria que trobi l’agent sempre serà la més curta possible perquè l’heurística que utilitza l’agent (la distància en línia recta) és admissible, i quan l’heurística és admissible, l’algorisme A* garanteix que trobarà la solució òptima (en aquest cas, la més curta).
Una heurística és admissible si ens assegura que mai sobre-estima el cost que falta per arribar a la solució.
En el problema, la distància en línia recta mai pot ser superior a la distància real que falta per arribar al destí. Per tant, l’heurística de la distància en línia recta és admissible.
...

Comprar Previsualizar