-
Notifications
You must be signed in to change notification settings - Fork 1
/
TP3_comentarios.txt
192 lines (115 loc) · 6.28 KB
/
TP3_comentarios.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
TP3
Caminos:
más rápido
más barato
menor cantidad de escalas
Centralidad:
Betweennes: cuáles es más frecuente terminar haciendo escalas para poder
ir entre cualquier parte del mundo a otra.
bAIRros Airlines:
Conectar con todos, usando las rutas más baratas posibles.
Viaje alrededor del mundo:
Todo el mundo, con:
menor costo posible
menor tiempo posible
Necesidades de las aerolineas: MEJOR solución y BUENA solución.
Ciudad de origen:
Se da el origen, recorre N cantidad de ciudades del mundo, vuelve al origen.
Viaje cultural:
Indicar las ciudades a conocer.
Si se desea visitar una antes que otra.
Mapa:
Exportar un mapa que permita visualizar las rutas de vuelo.
** DATOS DISPONIBLES **
1. Datos de los aeropuertos de Estados Unidos, así como de más de medio millón de vuelos durante el año 2015.
2. Parseado de datos, se genera:
El archivo aeropuertos.csv con el formato:
ciudad,codigo_aeropuerto,latitud,longitud
El archivo vuelos.csv con el formato:
aeropuerto_i,aeropuerto_j,tiempo_promedio,precio,cant_vuelos_entre_aeropuertos
3. Pruebas rápidas: set de aeropuertos y vuelos inventados.
** ACLARACIONES **
Una ciudad puede tener uno o más aeropuertos.
** IMPLEMENTACIÓN **
3 partes:
1. TDA GRAFO con sus primitivas
2. Biblioteca de funciones de grafos
3. FlyCombi (Interfaz con el usuario)
FlyCombi:
1. El programa debe recibir por parámetro y cargar en memoria
el set de datos ($ ./flycombi aeropuertos.csv vuelos.csv).
2. Solicitar el ingreso de comandos por entrada estándar,
del estilo <comando> 'parametro'.
3. Notar que esto permite tener un archivo de instrucciones
a ser ejecutadas (i.e. $ ./flycombi aeropuertos.csv vuelos.csv < entrada.txt).
** COMANDOS OBLIGATORIOS **
1. listar_operaciones.
Debe imprimirse una línea por cada comando que esté implementado.
Complejidad: O(1).
// Tener un txt y leer del mismo las operaciones disponibles, imprimiendo en pantalla.
2. Camino_mas (★) OK
Parámetros: barato ó rapido + origen y destino (ciudades, no aeropuertos)
Complejidad: Este comando debe ejecutar en O(F*log(A)), siendo A la cantidad de aeropuertos,
y F la cantidad de vuelos entre aeropuertos (sin contar frecuencia).
3. camino_escalas (*) OK
Camino con menor cantidad de escalas.
Parámetros: origen y destino.
Este comando debe ejecutar en O(F+A), siendo A la cantidad de aeropuertos,
y F la cantidad de vuelos entre aeropuertos (sin contar frecuencia).
4. Aeropuertos más importantes
* A tener en cuenta no sólo centralidad sino FRECUENCIA de vuelos *
Betweeness Centrality (***) OK
Parámetros: N cantidad de aerop más importantes a mostrar.
Complejidad: O(A * F*Log(A)).
Betweeness Centrality Aproximada (*) OK
Parámetros: N cantidad de aerop más importantes a mostrar.
Complejidad: O(A + F).
Pagerank (**) OK
Parámetros: N cantidad de aerop más importantes a mostrar.
Complejidad: O(K*(A+F)), K cantidad de iteraciones.
5. Optimización de rutas para nueva aerolínea (**) OK
Comando: nueva_aerolinea.
Parámetros: ruta, ruta del archivo de salida.
exportar un archivo con las rutas que permitan implementar
una nueva aerolínea tal que se pueda comunicar a todos los aeropuertos
(en esta primera iteración, sólo de Estados Unidos) con dicha aerolínea,
pero que el costo total de la licitación de las rutas aéreas sea mínima.
Se considera que el costo de las rutas es proporcional al costo de los pasajes,
por lo que se puede trabajar directamente con dicho costo.
Se busca que la nueva aerolínea pueda llegar a todos los aeropuertos de alguna forma.
La salida de este comando debe ser un archivo con el mismo formato del archivo vuelos.csv,
pero únicamente con las rutas de vuelo a utilizar por ésta aerolínea.
6. Recorrer el mundo, de forma óptima (***)
Comando: recorrer_mundo.
Parámetros: origen, ciudad desde la que se parte para comenzar el recorrido.
nos devuelve una lista en orden de cómo debemos movernos por el mundo para visitar
todas las ciudades del mundo, demorando lo menos posible. Podemos volver a usar un
aeropuerto ya usado, u otro de alguna ciudad ya visitada, si eso mejora la duración de
nuestro viaje.
7. Recorrer el mundo, de forma aproximada (*)
Comando: recorrer_mundo_aprox
Parámetros: origen, ciudad desde la que se parte para comenzar el recorrido.
Nos devuelve una lista en orden de cómo debemos movernos por el mundo para
visitar todas las ciudades del mundo, demorando aproximadamente lo menos posible.
Podemos volver a usar un aeropuerto ya usado, u otro de alguna ciudad ya visitada,
si eso mejora la duración de nuestro viaje.
8. Viaje de N lugares (***) OK
Comando: vacaciones
Parámetros: origen, y n.
Utilidad: Obtener algún recorrido que comience en origen y que termine en
origen también, de largo n (sin contar la última vuelta al origen).
No debe pasarse por un aeropuerto más de una vez (salvo el origen,
cuando volvemos a éste). En caso de no encontrar un recorrido de dicho largo
que vuelva luego al origen, imprimir "No se encontro recorrido".
// backtracking ?
9. Itinerario cultural (**) OK
Comando: itinerario
Parámetros: ruta, la ruta el archivo del itinerario.
Utilidad: El archivo de ruta tiene el formato:
ciudad_1,ciudad_2,ciudad_3, ...,ciudad_N
ciudad_i,ciudad_j
Imprimir el orden en el que deben visitarse dichas ciudades.
Imprimir el camino mínimo en tiempo o escalas (según lo que se haya implementado en ese caso) a realizar.
10. Exportar a archivo KML (*) OK
Comando: exportar_kml.
Parámetros: archivo.