Número posible de combinaciones para las rutas de viaje de regreso

Question

Mi matemáticas es malo, muy malo. Tan mal estoy luchando para igualar esta pregunta frase, pero aquí va.

La situación es un viaje en tren y tiene cuatro matrices para trabajar.

Leaving_Stations Arriving_Stations

Leaving_Dates Returning_Dates

Así que digamos que sólo está interesado en una forma en rutas y tiene que averiguar cuántas combinaciones de ruta existen. Eso sería (creo)

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

Pero, ¿cómo hago para encontrar la manera muchas combinaciones que hay si quiero un viaje de regreso?

ACTUALIZACIÓN ::

o funcionaría esto?

possible_routes = ((leaving_stations x arriving_stations) x leaving_dates) x (leaving_dates x returning_dates)

Answer 1

Bueno, la respuesta es que no es totalmente claro, desde su nombre de matriz.

Suponiendo que tenemos las matrices de 4:

• Fechas Dejando
• Fechas de retorno
• Estaciones Dejando
• Estaciones Destino

A continuación, podemos hacer un poco de explicar aquí. Vamos a usar la notación | x | para representar la cardinalidad (número de elementos) de array [x], de manera que | Dejando fechas | es el número total de las fechas que usted podría dejar actuar.

A continuación | Dejando fechas | * | Estaciones Dejando | * | Estaciones Destino | se traduciría en, elegir una fecha para dejar actuar, a continuación, elegir una estación para salir de, a continuación, elegir una estación para llegar a, y hacer que en todas las formas posibles. Así que esto parece ser lo que está pidiendo para viajes de ida.

Ahora, prácticamente, voy a asumir que este es un problema del mundo real, por lo que vamos a decir que elegimos para salir de Southampton a Yorkshire el 20 de junio, en el viaje de vuelta todo lo que se les permite elegir en este momento debe ser la fecha de vuelta (lo que significa que estoy asumiendo que usted quiere volver a casa).

Así que el número total de maneras que podemos planificar un viaje redondo sería el primer plan de un viaje de una manera que el anterior, y luego elegir una fecha de retorno, lo que sería | Dejando fechas | * | Estaciones Dejando | * | Estaciones Destino | * | Fecha de regreso. | Los 3 primeros términos elegir el viaje de ida como antes, y el último término recoge una fecha de regreso de todas las posibles fechas. Por supuesto, si tuviéramos la opción de volver a otra estación distinta de la que partimos de, entonces la ecuación sería (| Dejando fechas | * | Dejando estaciones | * | Estaciones Destino |) * (| fecha de regreso | * | Dejando estaciones |), o si se podría incluso dejar de una diferente estación de llegada a la que llegamos por primera vez en que se convertiría en (| Dejando fechas | * | Estaciones Dejando | * | Estaciones Destino |) * (| regreso | * | Estaciones Destino | * | Estaciones Dejando |.)

Answer 2

No estoy seguro de si he entendido bien, pero esto parece como un típico href="http://en.wikipedia.org/wiki/List_of_algorithms#Routing" gráfico de ruta problema de la teoría . Usted puede mirar en trayectoria mínima o noreferrer A * algoritmos.

Answer 3

En primer lugar, rutas A-A son las cosas mal, por lo que:

possible_routes = 
(
  leaving_stations x arriving_stations - 
  (leaving_stations [intersection] arrivig_stations) 
) x leaving_dates

operación de intersección es elementos que pertenecen a ambas matrices

En segundo lugar, cuando se quiere 2 rutas manera, las combinaciones son:

possible_2way_routes = 
(
    leaving_stations x arriving_stations - 
    (leaving_stations [intersection] arrivig_stations) 
) x 
leaving_dates x 
(return_dates that later than leaving dates+route time)

'leaving_dates x (return_dates que luego de dejar las fechas + tiempo de recorrido)' son algo extraño, por lo que puede ser más fácil de cumpute alta estima - número, que no menos del possible_2way_routes en cualquier caso. los más altos niveles será cuando todos returning_dates más tardar leaving_dates, así:

possible_2way_routes <= 
(
    leaving_stations x arriving_stations - 
    (leaving_stations [intersection] arrivig_stations) 
) x leaving_dates x return_dates

Oh, he recordado cómo calcular 'return_dates que luego de dejar las fechas + tiempo de ruta'. es:

for each element of leaving_dates {
sum=sum+return_dates that later than ith leaving date+route time}

todavía hay un problema de 'tiempo de ruta', aunque ...