我最近碰到这个（编辑：问题一）从Spotify的黑客挑战的今年早些时候包括确定开关的火车车路口路线火车回它的出发点有趣的问题。火车要到面对它留下相同的方向和列车不能扭转在铁轨上。

I recently came across this ( Problem A) interesting problem from Spotify's hacker challenge earlier this year which involves determining the switching at train truck junctions to route a train back to it's starting point. The train must arrive facing the same direction it left and the train can never reverse on the tracks.

据我了解，这个问题可以建模为一个无向（？）图中，我们必须找到从某个顶点最短的周期，或者检测到没有这样的周期存在。然而，有趣的是，对于一个顶点，V，毗邻诉顶点取决于采取诉路径上，因此在一定意义上图可以考虑执导，但这个方向是路径依赖的。

As I understand it, the problem can be modeled as an undirected(?) graph where we must find the shortest cycle from a certain vertex, or detect that no such cycle exists. However, the interesting part is that for a vertex, v, the vertices adjacent to v are dependent on the path taken to v, so in a sense the graph could be considered directed, though this direction is path-dependent.

我的第一个念头是模型中的每个节点为3个独立的顶点，A，B和C，其中A＆LT; - > B和A＆LT; - > C，然后使用广度优先搜索来建立一个搜索树直到我们找到原始顶点，但是这是由警告并发以上，即邻接对于给定的顶点取决于我们访问previous顶点。这意味着，在我们的BFS树中，节点可以具有多个父母。

My first thought was to model each node as 3 separate vertices, A, B and C, where A <-> B and A <-> C, and then use a breadth-first search to build a search tree until we find the original vertex, but this is complicated by the caveat above, namely that the adjacencies for a given vertex depend on the previous vertex we visited. This means that in our BFS tree, nodes can have multiple parents.

显然，一个简单的BFS搜索将不足以解决这个问题。我知道有存在检测周期的图形算法。一种办法是，检​​测到所有的循环，然后为每个周期，检测路径是否有效。 （即，不反转方向）

Obviously a simple BFS search won't be sufficient to solve this problem. I know there are algorithms that exist to detect cycles in a graph. One approach might be to detect all the cycles, then for each cycle, detect whether the path is valid. (i.e., does not reverse direction)

没有任何人有任何的方法的见解，解决这个问题呢？

Does anyone else have any insights on approaches to solving this problem?

更新： 我接着@Karussell在评论中提出的办法。

UPDATE: I followed the approach suggested by @Karussell in the comments.

这是我在github的解决方案。

诀窍是使用基于边缘的图形，而不是传统的基于顶点的图形的情况进行建模。在大赛提供的输入文件在边缘已经而言方便地指定，因此这个文件可以方便地用于构建基于边缘的曲线图。

The trick was to model the situation using an edge-based graph, not a traditional vertex-based graph. The input file supplied in the contest is conveniently specified in terms of edges already, so this file can be easily used to build an edge-based graph.

该计划使用两个重要的类：道路和求解。一道道有两个整数字段，J1和J2。 J1重新presents源结和J2重新presents目标交界处。每路是单向的，即只能从J1前往J2。每道还包括邻近道路和父道的链表。该道班还包括静态方法来输入使用的文件和整数索引重新presenting了A，B和C点，每个结点字符串之间进行转换。

The program uses two important classes: Road and Solver. A Road has two integer fields, j1 and j2. j1 represents the source junction and j2 represents the target junction. Each road is one-way, meaning that you can only travel from j1 to j2. Each Road also includes a LinkedList of adjacent Roads and a parent Road. The Road class also includes static methods to convert between the Strings used in the input file and integer indexes representing the A, B, and C points at each junction.

有关在输入文件中的每个条目中，我们添加两条路一个HashMap，一条路两个路口之间的每个方向。现在，我们有所有的连接点之间运行道路的列表。我们只需要连接道路一起通过A，B和C交换机的连接处。如果道路在Junction.A结束后，我们仰望那开始在Junction.B和Junction.C，并添加这些道路为邻接道路。该buildGraph（）函数返回，其目标结（J2）道是1A==指数0。

For each entry in the input file, we add two Roads to a HashMap, one Road for each direction between the two junctions. We now have a list of all of the Roads that run between junctions. We just need to connect the roads together at the junctions through the A, B and C switches. If a Road ends at Junction.A, we look up the roads that begin at Junction.B and Junction.C and add these roads as adjacencies. The buildGraph() function returns the Road whose target junction (j2) is "1A" == index 0.

目前这一点上，我们的图形构成。为了找到最短路径，我只​​是用一个BFS遍历图。我们离开根无标记和排队根的邻接开始。如果我们发现一个道路，其目标交界处，是1A（索引0），那么，我们发现通过起点的最短周期。一旦我们重建使用每个道的父属性的路径，这是因为需要在该问题的小事来设置适当的开关。

At this point, our graph is constructed. To find the shortest path I simply used a BFS to traverse the graph. We leave the root unmarked and begin by queueing the root's adjacencies. If we find a road whose target junction is "1A" (index 0) then we have found the shortest cycle through the starting point. Once we reconstruct the path using each Road's parent property, it's a trivial matter to set the switches appropriately as required in the problem.

感谢Karussell的建议这种方法。如果你想要把回答的形式您的评论有一个简短的说明，我会接受的。多亏@Origin，以及。我必须承认，我没有完全按照你的答案的逻辑，但是这肯定不是说这是不正确的。如果有人使用您的解决方案解决了这个问题，我会非常有兴趣看看吧。

Thanks to Karussell for suggesting this approach. If you want to put your comment in answer form with a short explanation, I will accept it. Thanks to @Origin, as well. I must admit that I did not fully follow the logic of your answer, but that is certainly not to say that it is not correct. If anyone solves this problem using your solution, I would be very interested to see it.

推荐答案

由于我的意见建议：我认为，你可以通过的基于边缘图表或通过改善< /一>这是或多或少的增强的节点基于曲线图。

As my comment suggested: I think that you can solve this via edge based graph or via an improvement which is more or less an 'enhanced' node based graph.

详细信息：

您也可以分配可能的结果每一个路口 - 现在的算法需要更加聪明，需要每个结点来决定如何根据你刚才做的国家（含方向）。我想，这就是增强型节点基于图的主要思想应该是较少的内存密集型的（不是你的情况是很重要）。

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).