3

我在一家贸易公司面试时被问到这个问题，

您乘坐公共汽车穿越州，公共汽车可以在任何可能的 C 城市停靠，您需要找到从城市 a 到城市 b 的方法。共有B 辆公交车，每辆公交车往返于两个城市之间。所有公共汽车都以每日为基地行驶，例如，每辆公共汽车 x 在 d1 天离开某个城市 c1，并在另一天 d2 到达另一个城市 b1 (d2>d1)。假设如果您在 d 天到达一个城市，您可以搭乘任何在 d 天或之后离开该城市的公共汽车。

B 总线为您提供 a1、b1、d1 和 d2。描述一种算法，判断是否存在不超过 D 天从城市 a 到城市 b 的路线，并分析运行时间。

我最初试图将问题建模为最短路径算法，但当时我无法弄清楚，我搞砸了面试。

4

4 回答 4

1

我想如果给你一天的时间（似乎不是这样），应用Dijkstra 的算法应该很容易。

为问题创建图表很简单。每个节点都是一个城市，每条总线都是从一个节点到另一个节点的有向边。边缘的权重通常并没有真正定义（我们不能只考虑行程时间），并且将在我们处理它时确定。

因此，将问题简化为您知道 start day 的多个子问题，如下所示：

从a有k辆公共汽车到其他城市。所以巴士 b i从 a 到 b i从第i天开始到第i天结束。对于这些总线中的每一个，在第i天结束时从 b i开始创建一个子问题（并记住 start i）。

在给定起始日期和城市的情况下进行 Dijkstra：

在探索图表时，我们需要跟踪当天。

当从第 d1 天开始在城市 c1 生成邻居时，对于每个有从 c1 到 c2 的公共汽车的城市 c2，我们生成从 c1 到 c2 的最早公共汽车（在 c1 >= 当天出发）（如果公共汽车可以乘坐从 c1 到 c2 的天数不同，考虑最早到达 c2)。c2 的值就是从最初的出发日（从上面开始i）到巴士到达 c2 的天数。

优化：

您不需要对每个子问题执行一次完整的 Dijkstra 运行，如果您在某一天到达一个城市，那么在同一天到达该城市的任何下一个子问题都将从那里开始具有相同的路径。同时完成它们应该不会太难，并且应该比一次完成它们产生更好的性能。

人们可能会想出一个启发式函数来应用A*。

如果我错过了什么，请随时指出。

于 2013-04-11T08:22:02.670 回答
0

有趣的问题。这是我的尝试。如果我忽略了一些重要的事情，或者我的解决方案中的某些内容不清楚，请告诉我。

提示 1：如果问题看起来很难，请将其简化为更简单的问题。解决更简单的问题，看看你是否可以将你的解决方案推广到更难的情况。

让我们在这里应用这个技巧。我们知道公共汽车在两个城市之间穿梭。为了简化假设，如果一辆公共汽车从一个城市到另一个城市，我们总是可以在这两个节点之间穿行。因此，构建一个以城市为顶点的无向图。现在在顶点 i 和 j 之间有一条边，如果有从 i 到 j 的公共汽车（与从 j 到 i 相同）。现在在这种情况下，问题很简单，如果我们对从 a 开始并以长度 < n 的 b 结束感兴趣，最短路径的长度是否小于 n。伟大的！

现在让我们回到更难的问题。我们构建了两个图 G_1 和 G_2，G_1 表示在奇数天（如第 1 天）时我们可以到达的地方，而 G_2 表示在偶数天（如第 2 天）时我们可以到达的地方。现在这两个图都是有向的，不像以前。现在我们将这两个图结合起来形成图G。G的顶点只是G_1并集G_2。现在对于 G_1 中的每个有向边，表示开始顶点 s 和结束顶点 t。将 G_1 中的顶点 s（作为 G 的子图）连接到 G_2 中的顶点 t（作为 G 的子图）。对于 G_2 中的每个有向边，表示开始顶点 s 和结束顶点 t。将 G_2 中的顶点 s（作为 G 的子图）连接到 G_1 中的顶点 t（作为 G 的子图）。G 中的所有有向边的权重为 1。现在的问题是 G 中是否存在长度 < n 的最短路径。

这个想法是将两个图 G_1 覆盖在 G_2 之上，以便我们考虑路线在偶数日和奇数日发生变化。

于 2013-04-11T01:19:00.813 回答
0

这是 Haskell 中的一个示例，其中包含真正的慢速巴士，构建从目的地到起点的路线：

import Data.List (elemIndex)
import Data.Maybe (fromJust)

cities = ["New York", "Philadelphia", "Washington", "Buffalo"]
buses = [([0,1],2), ([0,2],1), ([1,2],1), ([2,3],4)] --buses (cities a1 b1 as indexes, num days of travel)

solve origin destination maxDays = do
  lastBus <- filter ((== fromJust (elemIndex destination cities)) . last . fst) buses
  solve' [lastBus] where
    solve' result 
      | sum (map snd result) > maxDays                   = []
      | cities !! (head . fst . head $ result) == origin = 
          [(map (map (cities !!) . fst) result, show (sum . map snd $ result) ++ " Days Travel")]
      | otherwise = 
          let potentialBuses = filter ((== (head . fst . head $ result)) . last . fst) buses
          in if null potentialBuses 
                then []
                else do
                  bus <- potentialBuses
                  solve' (bus:result)


OUTPUT:
*Main> solve "New York" "Buffalo" 6
[([["New York","Washington"],["Washington","Buffalo"]],"5 Days Travel")]

*Main> solve "New York" "Buffalo" 3
[] --trip longer than D

*Main> solve "New York" "Washington" 3
[([["New York","Washington"]],"1 Days Travel"),
 ([["New York","Philadelphia"],["Philadelphia","Washington"]],"3 Days Travel")]
于 2013-04-11T06:04:45.067 回答
0

您会不时发现另一种方法。它基于定义城市之间可能的过渡的矩阵。假设矩阵是 M，如果有从城市 j 到城市 i 的道路，则 M[i,j] 为 1，否则为 0。通过从起始城市的单位向量开始并将该向量与转移矩阵相乘，您可以将在一步内到达的所有城市中获得一个值大于零的向量。您在请求的天数内重复此步骤。

在为您的案例建模时，一个问题是您有一个加权图，即并非每个转换都需要相同的时间。但是，该成本是一个整数，因此您可以在需要超过一天时间的路线中引入人工停靠点（即顶点）来对此进行建模。然后你会得到一个未加权的图表。此外，您可以从问题中假设权重很低，因此它可能不会造成太多开销。

由于矩阵乘法是关联的，因此您可以将矩阵与自身相乘多次，然后再将其输入初始向量。由于实际值不感兴趣，只有它们是 0 还是 1，您可能能够进一步减少它并有效地对矩阵进行位打包。此外，您可以将 MxMxMxM 计算为 (MxM)x(MxM) 以减少开销。然后，还可以对矩阵乘法（Strassen 算法，IIRC）进行一些优化。

注意：我知道这个描述有点粗略，请给我留言，我会尽力澄清它。

于 2013-04-12T17:20:39.253 回答