回程路线的可能组合数

Question

我的数学很糟糕，非常糟糕。很糟糕，我什至都在努力表达这个问题，但就这样吧。

这种情况是火车旅行，您有四个阵列可以使用。

离开_Stations arriving_station

离开_dates returning_dates

假设您只对单向路线感兴趣，并且您需要弄清楚有多少种路线组合。那将是（我认为）

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

但如果我想要回程，我该如何计算有多少种组合呢？

更新：：

或者这会起作用吗？

可能的路线 = ((出发车站 x 到达车站) x 出发日期) x (出发日期 x 返回日期)

Answer 1

嗯，答案是从你的数组名称中并不完全清楚。

假设我们有 4 个数组：

• 离开日期
• 返回日期
• 出发车站
• 到达站

那么我们可以在这里做一些解释。让我们使用符号| x |代表数组[x]的基数（元素数），以便|离开日期|是您可以保留的日期总数。

然后|离开日期| * |离开电台| * |到达站|会翻译成，挑选一个日期，然后选择一个车站离开，然后选择一个车站到达，然后以各种可能的方式做到这一点。所以这似乎就是您对单程旅行的要求。

现在，实际上，我将假设这是一个现实世界的问题，所以假设我们选择 6 月 20 日从南安普敦出发前往约克郡，在回程中，我们此时可以选择的应该是返回日期（意味着我假设您想回家）。

因此，我们可以计划往返的总数将首先计划单程旅行，然后选择一个返回日期，这将是|离开日期| * |离开电台| * |到达站| * |返回日期|。前 3 个术语如上选择单程旅行，最后一个术语从所有可能的日期中选择返回日期。当然，如果我们可以选择返回我们离开的车站以外的另一个车站，那么等式将是 (|出发日期| * |出发车站| * |到达车站|) * (|返回日期| * |出发站|)，或者如果我们甚至可以从与我们第一次到达的站不同的到达站出发，那么它将变成 (|出发日期| * |出发站| * |到达站|) * (|返回日期| * |到达站| * |出发站|)。

Answer 2

我不知道如果我理解正确，但是这似乎是一个典型的图路由理论问题。你可以看一下最短路径或的 A * 算法。

Answer 3

第一，A-A航线错误的东西，所以：

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

交集操作是属于两个阵列元素

第二，当你想2点方式的路线中，所述组合是：

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晚于离开日期+路径时间）”是奇怪的，因此它可以更容易地cumpute高的估计 - 数，即不超过在任何情况下possible_2way_routes以下。最高计数将是当所有returning_dates迟于leaving_dates，所以：

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

哦，我记得如何计算“return_dates晚于离开日期+路线时间”。它是：

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

仍有的 '路径时间' 的问题，但...