número possível de combinações de rotas de viagem de retorno

Question

A minha matemática é ruim, muito ruim. Tão ruim que eu estou lutando para a frase mesmo esta pergunta, mas aqui vai.

A situação é a viagem de trem e você tem quatro matrizes para trabalhar.

Leaving_Stations Arriving_Stations

Leaving_Dates Returning_Dates

Então, digamos que você está interessado apenas em um rotas caminho e você precisa descobrir quantas combinações de rota existem. Isso seria (eu acho)

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

Mas como eu iria sobre descobrir quantas combinações existem, se eu quiser uma viagem de volta?

Atualização ::

ou seria este trabalho?

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

Answer 1

Bem, a resposta é que não é totalmente claro de seus nomes da matriz.

Supondo que temos os 4 matrizes:

• Deixando Datas
• datas de retorno
• Deixando Estações
• Chegando Estações

Então nós podemos fazer um pouco de explicar aqui. Vamos usar a notação | x | para representar a cardinalidade (número de elementos) de matriz [x], de modo que | Partindo Datas | é o número total de datas que você poderia deixar por diante.

Então | Deixando Datas | * | Deixando Estações | * | Chegando Estações | se traduziria em, escolher uma data para sair em, em seguida, escolher uma estação para deixar de, em seguida, escolher uma estação para chegar a, e fazer isso de todas as maneiras possíveis. Portanto, este parece ser o que você está pedindo para viagens one-way.

Agora, praticamente, eu vou assumir que este é um problema do mundo real, de modo que nos deixa dizem que nós escolhemos para sair de Southampton a Yorkshire em 20 de junho, na viagem de volta tudo o que está autorizado a escolher neste momento deve ser a data de retorno (ou seja, eu estou supondo que você quer voltar para casa).

Assim, o número total de maneiras que podemos planejar uma viagem de volta seria o primeiro plano de uma viagem só de ida como acima, e, em seguida, escolher uma data de retorno, o que seria | Deixando Datas | * | Deixando Estações | * | Chegando Estações | * | Data de retorno |. Os 3 primeiros termos escolher a viagem só de ida como acima, e o último termo escolhe uma data de retorno de todas as possíveis datas. Claro que, se tivéssemos a opção de voltar para outra estação diferente daquele que deixamos de, em seguida, a equação seria (| Deixando Datas | * | Deixando Estações | * | Chegando Estações |) * (| data de retorno | * | Deixando Estações |), ou se poderia mesmo deixar a partir de uma diferente Chegada Estação do que a que se chegou no que se tornaria (| Deixando Datas | * | Deixando Estações | * | Chegando Estações |) * (| data de retorno | * | Chegando Estações | * | Deixando Estações |.)

Answer 2

Eu não tenho certeza se eu entendi corretamente, mas este parece ser um gráfico de encaminhamento normal problema teoria . Você pode olhar para mínima Path ou A * algoritmos.

Answer 3

Em primeiro lugar, A-Um rotas são as coisas erradas, por isso:

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

operação de intersecção é elementos que pertencem a ambas as matrizes

Em segundo lugar, quando você quer 2 rotas maneira, as combinações são:

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 depois de deixar datas + tempo de percurso)' são coisa estranha, por isso pode ser mais fácil de cumpute alta estima - número, que não menos de possible_2way_routes em qualquer caso. a maior contagem será quando todos returning_dates mais tarde do que leaving_dates, assim:

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

oh, eu me lembrei como calcular 'return_dates que depois de deixar datas + tempo de percurso'. é:

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

ainda há problema de 'tempo de rota', embora ...