Mögliche Anzahl von Kombinationen für die Rückreiserouten

Question

Meine Mathe ist schlecht, wirklich schlecht. So schlecht, ich bin zu kämpfen Ausdruck, diese Frage zu glätten, aber hier geht.

Die Situation ist Zugfahrten und Sie haben vier Arrays mit zu arbeiten.

Leaving_Stations Arriving_Stations

Leaving_Dates Returning_Dates

Also lassen Sie uns sagen, dass Sie in einer Art und Weise Routen nur daran interessiert sind, und Sie müssen, wie viele Kombinationen Weg, um herauszufinden, gibt es. Das wäre (ich glaube)

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

Aber wie würde ich mich darum, herauszufinden, wie viele Kombinationen gibt es, wenn ich eine Hin- und Rückfahrt will?

UPDATE ::

oder würde diese Arbeit?

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

Answer 1

Nun, die Antwort ist es nicht ganz klar aus dem Array-Namen.

Angenommen, wir haben den 4-Arrays:

• Verlassen Daten
• Zurück Daten
• Verlassen Stations
• Ankunft Stationen

Dann können wir etwas tun, hier zu erklären. Lassen Sie uns die Notation | x | die Kardinalität (Anzahl der Elemente) des Arrays darzustellen [x], so dass | Daten Weggehen | ist die Gesamtzahl der Tage, dass Sie verlassen können.

Dann | Termine Weggehen | * | Verlassen Stationen | * | Ankunftsstationen | übersetzen würde, um ein Datum auszuwählen auf zu verlassen, dann eine Station wählt aus zu verlassen, dann eine Station abholen an ankommen, und zu tun, dass in allen möglichen Weisen. So würde das scheint zu sein, was sie für Einwegfahrten sind zu fragen.

Nun, praktisch, ich gehe davon aus, dass dies eine reale Welt Problem ist, so dass lasst uns sagen, dass wir von Southampton nach Yorkshire am 20. Juni auf der Rückfahrt sind wir alle verlassen dürfen gepflückt an dieser Stelle zu wählen sollte die Rückkehr aktuell sein (was bedeutet, ich nehme an, Sie nach Hause zurückkehren wollen).

So ist die Gesamtzahl der Möglichkeiten, dass wir eine Rundreise planen erster Plan eine Einwegfahrt wie oben wäre, und dann ein Rückgabedatum auswählen, das wäre | Termine Weggehen | * | Verlassen Stationen | * | Ankunftsstationen | * | Return Date |. Die ersten drei Begriffe wählen die Einwegfahrt wie oben, und der letzte Term nimmt von allen möglichen Daten ein Rückgabedatum. Natürlich, wenn wir die Möglichkeit haben an einem anderen Station andere als die Rückkehr, die wir von links, dann würde die Gleichung sein (| Termine Weggehen | * | Stationen Verlassen | * | Ankunftsstationen |) * (| Return Date | * | verlassen Stationen |), oder wenn wir auch aus einem anderen Ankunft Bahnhof als das verlassen können, dass wir zuerst auf mich angekommen würde (| Weggehen Termine | * | verlassen Stationen | * | Ankunftsstationen |) * (| Return Date | * | Ankunftsstationen | * | Verlassen Stationen |).

Answer 2

Ich bin mir nicht sicher, ob ich das richtig verstanden, aber dies scheint wie ein typischer Graph-Routing rel="nofollow Theorie Problem. Sie können unter Mindest Pfad oder A * Algorithmen.

Answer 3

erster, A-A Routen sind falsche Dinge, so:

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

Schnittoperation Elemente, die zu beiden Arrays gehört

zweitens, wenn Sie 2-Wege-Routen wollen, sind die Kombinationen sind:

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, die später als Termine + Fahrzeit verlassen)‘ sind seltsame Sache, so dass es leichter sein kann, hohe Wertschätzung cumpute - Zahl, dass nicht weniger als possible_2way_routes auf jedem Fall. die höchste Zählung sein wird, wenn alle returning_dates später als leaving_dates, so:

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

oh, habe ich daran dachte, wie ‚return_dates, die später als Termine + Fahrzeit verlassen‘ zu berechnen. es ist:

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

gibt es noch Problem der 'Fahrzeit', aber ...