6

我最近在今年早些时候 Spotify 的黑客挑战中遇到了这个（编辑：问题 A）有趣的问题，其中涉及确定火车卡车交叉点的切换以将火车路由回其起点。火车必须朝着它离开的方向到达，并且火车永远不能在轨道上倒车。

据我了解，该问题可以建模为无向（？）图，我们必须从某个顶点找到最短的循环，或者检测不存在这样的循环。然而，有趣的是，对于顶点 v，与 v 相邻的顶点依赖于到 v 的路径，因此从某种意义上说，该图可以被认为是有向的，尽管这个方向是依赖于路径的。

我的第一个想法是将每个节点建模为 3 个单独的顶点 A、B 和 C，其中 A <-> B 和 A <-> C，然后使用广度优先搜索构建搜索树，直到找到原始顶点，但这因上面的警告而变得复杂，即给定顶点的邻接取决于我们访问的前一个顶点。这意味着在我们的 BFS 树中，节点可以有多个父节点。

显然，一个简单的 BFS 搜索不足以解决这个问题。我知道存在一些算法来检测图中的循环。一种方法可能是检测所有循环，然后对于每个循环，检测路径是否有效。（即不反转方向）

还有其他人对解决此问题的方法有任何见解吗？

更新： 我遵循@Karussell 在评论中建议的方法。

这是我在 github 上的解决方案。

诀窍是使用基于边缘的图而不是传统的基于顶点的图来模拟情况。比赛中提供的输入文件已经根据边方便地指定了，因此该文件可以很容易地用于构建基于边的图。

该程序使用两个重要的类：Road 和 Solver。Road 有两个整数字段，j1 和 j2。j1 代表源交汇点，j2 代表目标交汇点。每条道路都是单向的，这意味着您只能从 j1 行驶到 j2。每条道路还包括相邻道路的链接列表和父道路。Road 类还包括静态方法，用于在输入文件中使用的字符串和表示每个交叉点处的 A、B 和 C 点的整数索引之间进行转换。

对于输入文件中的每个条目，我们将两条 Roads 添加到 HashMap 中，两个路口之间的每个方向对应一个 Road。我们现在有一个在交叉点之间运行的所有道路的列表。我们只需要通过 A、B 和 C 开关将路口的道路连接在一起。如果一条道路在 Junction.A 结束，我们查找从 Junction.B 和 Junction.C 开始的道路并将这些道路添加为邻接。buildGraph() 函数返回目标交汇点 (j2) 为“1A”== 索引 0 的道路。

至此，我们的图就构建好了。为了找到最短路径，我只是使用 BFS 来遍历图形。我们不标记根，并从排队根的邻接开始。如果我们找到一条目标路口为“1A”（索引 0）的道路，那么我们就找到了通过起点的最短循环。一旦我们使用每个 Road 的 parent 属性重建路径，就可以根据问题的需要适当地设置开关。

感谢 Karussell 提出这种方法。如果您想以简短解释的形式将您的评论放在答案中，我会接受。也感谢@Origin。我必须承认我没有完全按照你的回答逻辑，但这当然不是说它不正确。如果有人使用您的解决方案解决了这个问题，我会非常有兴趣看到它。

4

2 回答 2

1

一种可能的方法：首先构建某种图来建模所有连接（图 G）。然后构造另一个图，我们将在其中找到循环（图 H）。对于 G 中的每个节点 A，我们将向图 H 添加一个节点。每个 A 节点也有 2 条出边（到图 G 中的 B 和 C 节点）。在 H 中，这些边将到达 G 中将遇到的下一个 A 节点。例如，与 ID 为 3 的交换机的 A 节点相对应的 H 中的 A 节点将具有到节点 9 和节点 6 的出边。 H. 每条边的权重是该路线上经过的开关数量（包括起始开关）。

这将产生一个图，我们可以在其中生长一个前向最短路径树。如果我们再次到达起点，那么循环就完成了。

关键是一个switch只有在A->方向遍历时才是一个决策点。没有必要对向后方向建模，因为这只会使搜索复杂化。

编辑：更多说明

问题包括确定从 A 到 A 的最短路径（再次）。最短的定义在这里是通过的开关数量。这将用于基于 Dijkstra 的搜索算法。我们基本上将在图 H 上进行 Dijkstra，其中边的成本等于该边中开关的数量。

在 H 图中，每个开关都有一个节点。每个节点将有 2 条出边，对应于可以采用的 2 条路径（B 和 C 方向）。H 中的边将对应于原始图中 2 个 A 节点之间的完整路径。对于问题描述中的示例，我们得到以下信息：

开关1对应的节点：

  • 1 到节点 2 的出链路，权重 2，对应离开交换机 1 时走 C 方向。权重为 2，因为我们通过交换机 1，如果从 A1->C1->C3->A3->A2 走，则通过交换机 3
  • 1出链路到节点3，权重2，对应走B方向

开关2对应的节点：

  • 1出链路到节点6，权重2，对应走B方向
  • 没有第二个链接，因为 C 方向是死胡同

开关3对应的节点：

  • 1出链路到节点6，权重2，对应走C方向
  • 1 到节点 9 的出链路，权重 3，对应取 B 方向并经过开关 3、7 和 8

等等每个开关。这会产生一个包含 10 个节点的图，每个节点最多有 2 个有向边。

现在我们可以开始构建我们的 Dijkstra 树了。我们从节点 1 开始，有 2 个可能的方向，B 和 C。我们将它们放在优先队列中。然后队列包含[节点2，权重2]和[节点3，权重2]，因为我们可以在经过2个交换机后到达交换机2的A入口，在经过2个交换机后到达交换机3的A入口。然后我们通过从队列中获取最低权重的条目来继续搜索：

  • [节点2，权重2]：只取B方向，所以把[节点6，权重4]放到队列中
  • [节点 3，权重 2]：要走 2 个方向，因此将 [节点 6，权重 4] 和 [节点 9，权重 5] 添加到队列中。
  • [节点 6，权重 4]：可能有 2 个方向，将 [节点 4，权重 5] 和 [节点 8，权重 8] 添加到队列中]
  • [节点9，权重5]：只有C方向，添加[节点10，权重6]
  • [节点4，权重5]：添加[节点5，权重7]为C方向和[节点1，权重9]为B方向]
  • [节点10，权重6]：C方向添加[节点1，权重8]，B方向添加[节点1，权重10]
  • [节点5，权重7]：添加[节点1，权重11]和[节点8，权重10]
  • [节点 8，权重 8]：添加 [节点 7，权重 9]
  • [节点 1，权重 8]：我们找到了回去的路，所以我们可以停下来

（错误是可能的，我只是手工做的）

然后该算法在一个周期的最终长度为 8 处停止。确定遵循的路径只是在解决节点并解包路径时维护节点的父指针的问题。

我们可以使用 Dijkstra，因为 H 中的每个节点对应于沿正确方向遍历原始节点（G 中）。然后可以以 Dijkstra 方式解决 H 中的每个节点，因此算法的复杂性仅限于 Dijkstra（它可以处理 100k 开关数量的上限）。

于 2012-11-02T22:38:35.283 回答
1

正如我的评论所建议的那样：我认为您可以通过基于边缘的图或通过或多或少是基于“增强”节点的图的改进来解决这个问题。

细节：

  • 您的情况类似于道路网络中的转弯限制。如果您为每条（定向！）街道创建一个节点并根据允许的转弯连接这些节点，则可以对这些进行建模。
  • So, do not only store the position of your current position but also the direction and possible further 'situations'. To make it possible that even the same position with a 180° turn is different to your current state.

Instead of modeling your 'state' (which is directed!) into the graph you could also assign possible outcomes to every junction - now the algorithm needs to be more clever and needs to decide per junction what to do depending on your earlier state (including direction). I think, this is the main idea of the 'enhanced' node based graph which should be less memory intensive (not that important in your case).

于 2012-11-03T11:28:29.860 回答