Crowdly
Add to Chrome
Una companyia alemanya vol incloure un cercador de vols a la seva pàgina web per...
✅ The verified answer to this question is available below. Our community-reviewed solutions help you understand the material better.
Una companyia alemanya vol incloure un cercador de vols a la seva pàgina web per permetre que els seus clients puguin trobar la combinació de vols més barata entre les ciutats on opera. És molt important que el cercador sempre retorni la solució òptima (la més barata) i que el temps que trigui a trobar la solució sigui raonable.
Per a trobar la solució, es disposa dels preus dels vols que fa la companyia i s'ha definit una heurística que permet estimar el cost aproximat del viatge entre dues ciutats qualsevols a partir de la distància en línia recta entre les ciutats multiplicada per un preu per kilòmetre fix (heurística= (distància en línia recta) x (preu per km)).
A continuació teniu la matriu que mostra els preus dels vols que opera la companyia:
| 1 Münster FMO | 2 Hamburg HAM | 3 Colonia CGN | 4 Sttutgart STR | 5 Frankfurt FRA | 6 Munich MUC | 7 Erfurt ERF | 8 Berlin SXF | 9 Dresde DRS | 10Rostock RLG |
1-Münster FMO | ---- | 360 |
|
|
|
|
|
|
|
|
2-Hamburg HAM | 360 | ---- | 340 | 375 | 120 | 250 |
|
|
|
|
3-Colonia CGN |
| 340 | ---- |
| 150 |
|
|
|
|
|
4-Stuttgart STR |
| 375 |
| ---- | 150 | 190 |
|
|
|
|
5-Frankfurt FRA |
| 120 | 150 | 150 | ---- | 170 | 80 | 200 |
|
|
6-Munich MUC |
| 250 |
| 190 | 170 | ---- |
|
|
|
|
7-Erfurt ERF |
|
|
|
| 80 |
| ---- |
|
|
|
8-Berlin SXF |
|
|
|
| 200 |
|
| ---- | 120 | 95 |
9-Dresde DRS |
|
|
|
|
|
|
| 120 | ---- |
|
10-Rostock RLG |
|
|
|
|
|
|
| 95 |
| ---- |
L’equip que està desenvolupant el cercador està considerant implementar l’algorisme GBFS (Greedy Best First Search). Per ajudar a l’equip desenvolupador, s’us demana que feu una simulació de la primera iteració de l’algorisme GBFS Stuttgart i Rostock.
· Suposeu que l’aplicació elimina els cicles i, per tant, no els poseu a les llistes. · Per a cada camí, doneu el valor de la funció que utilitza l’algorisme per seleccionar els camins a expandir. Indiqueu els passos de càlcul per arribar al valor que doneu. · Si l'algorisme genera camins redundants, indiqueu clarament quins són i elimineu-los. Si necessiteu una heurística, podeu utilitzar l'heurística de la distància en línia recta fins el destí multiplicada per un preu de 0,25 €/km. Aquesta heurística proporciona una aproximació del preu del viatge i ja la teniu calculada a la columna 'heurística' de la taula pel trajecte demanat. |
|
Quin és el resultat de la primera iteració?