← Volver a los ejercicios

Plantear un escenario como grafo de estado

Una ciudad con cruces y vías de doble sentido. Recorrer una vía de longitud ℓ toma ℓ minutos y gasta ℓ de batería. Un carro eléctrico sale con la batería llena, tiene capacidad C, y en algunos cruces hay estación de carga, donde dejar la batería llena toma t minutos. Se pide el menor tiempo hasta el cruce de destino. Las ocho preguntas de abajo son las que se responden de cualquier problema de este tipo, en su orden.

Resueltas: 0 de 8

La ciudad

Los cuadros ámbar son los cruces con estación de carga. En verde el cruce de salida, en azul el de destino. Las vías no tienen sentido: se recorren en los dos.

La respuesta

¿Cuál es el menor tiempo, en minutos, para llegar al destino?

Para llevarse

Sin solución aquí. Queda la quinta pregunta, que es dibujar: haga el pedazo del grafo de estados que sale del estado inicial, con dos niveles de transiciones y la acción escrita en cada arista. Después suba la capacidad de la batería a 12, diga cuánto tarda el carro, por qué la carga desaparece de la respuesta y por qué el cruce 2 deja de ser un callejón sin salida. Por último, escriba cuántos estados caben si el enunciado agregara un límite de K cargas.