nombre de combinaisons possibles pour les itinéraires de voyage de retour

Question

Mon calcul est mauvais, mauvais réel. Si mal que je me bats pour égaliser cette question phrase, mais voilà.

La situation est Voyage en train et vous avez quatre tableaux pour travailler avec.

Leaving_Stations Arriving_Stations

Leaving_Dates Returning_Dates

Alors disons que vous êtes seulement intéressé par un parcours à sens unique et vous avez besoin de savoir combien de combinaisons de la route il y a. Ce serait (je pense)

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

Mais comment pourrais-je aller tenter de comprendre combien de combinaisons il y a si je veux un voyage de retour?

Mise à jour ::

ou serait ce travail?

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

Answer 1

Eh bien, la réponse est qu'il est pas tout à fait claire de vos noms de tableau.

En supposant que nous avons les 4 tableaux:

• Dates Leaving
• Dates de retour
• Stations Leaving
• Stations Arrivée

Ensuite, nous pouvons faire un peu d'expliquer ici. Utilisons la notation | x | pour représenter la cardinalité (nombre d'éléments) de la matrice [x], de sorte que | Fin Dates | est le nombre total de dates que vous pouvez laisser sur.

Alors | En quittant Dates | * | Stations | Leaving * | Stations | Arrivée se traduirait, choisir une date à partir de, puis choisissez une station de partir de, puis choisissez une station pour arriver à et faire de toutes les manières possibles. cela semble ainsi être ce que vous demandez pour les voyages à sens unique.

Maintenant, pratiquement, je vais supposer que c'est un problème du monde réel, de sorte que, disons que nous avons choisi de partir de Southampton à Yorkshire le 20 Juin, le voyage de retour tout ce que nous sommes autorisés à choisir à ce stade devrait être la date de retour (ce qui signifie que je suppose que vous voulez rentrer chez eux).

Le nombre total de façons que nous pouvons planifier un voyage aller-retour serait le premier plan d'un voyage à sens unique comme ci-dessus, puis choisir une date de retour, ce qui serait | Leaving Dates | * | Stations | Leaving * | Stations | Arrivée * | Date de retour |. Les 3 premiers termes choisir le voyage à sens unique comme ci-dessus, et le dernier terme choisit une date de retour de toutes les dates possibles. Bien sûr, si nous avions la possibilité de revenir à une autre station autre que celui que nous avons quitté à partir, l'équation serait (| Leaving dates | * | Stations Leaving | * | Stations Arrivée |) * (| Date de retour | * | en quittant les stations |), ou si l'on pouvait même laisser partir d'un autre gare d'arrivée que celle que nous sommes arrivés à elle deviendrait (| Leaving dates | * | Stations Leaving | * | Stations Arrivée |) * (| Retour | * | Stations Arrivée | * | Stations Leaving |.)

Answer 2

Je ne sais pas si je comprends bien, mais cela semble être un href="http://en.wikipedia.org/wiki/List_of_algorithms#Routing" typique graphique-routage problème de la théorie . Vous pouvez regarder Chemin minimum ou A noreferrer * algorithmes.

Answer 3

Tout d'abord, les routes A-A sont des choses mauvaises, donc:

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

opération d'intersection est des éléments qui appartient aux deux rangées

En second lieu, quand vous voulez 2 voies à sens unique, les combinaisons sont:

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 plus tard que de laisser les dates + durée du trajet) » sont chose étrange, il peut être plus facile à cumpute haute estimation - nombre, que pas moins de possible_2way_routes dans tous les cas. le nombre le plus élevé sera quand tous returning_dates plus tard leaving_dates, donc:

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

oh, je suis rappelé comment calculer «return_dates plus tard que de laisser les dates + durée du trajet. il est:

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

il y a encore problème du 'temps de parcours', mais ...