我最近在今年早些时候Spotify的黑客挑战中遇到了这个(编辑:问题A)有趣的问题,涉及确定在火车卡车路口的切换,以便将火车送回到它的起点.火车必须朝着它离开的方向朝向,火车永远不会在轨道上倒转.
据我了解,问题可以建模为无向(？)图,我们必须从某个顶点找到最短的周期,或者检测不存在这样的周期.然而,有趣的部分是对于顶点v,与v相邻的顶点取决于采用v的路径,因此在某种意义上,该图可以被认为是有向的,尽管该方向是路径依赖的.
我的第一个想法是将每个节点建模为3个独立的顶点,A,B和C,其中A < - > B和A < - > C,然后使用广度优先搜索来构建搜索树,直到我们找到原始顶点,但上面的警告使这很复杂,即给定顶点的邻接依赖于我们访问的前一个顶点.这意味着在我们的BFS树中,节点可以有多个父节点.
显然,简单的BFS搜索不足以解决这个问题.我知道存在用于检测图中的循环的算法.一种方法可能是检测所有周期,然后对于每个周期,检测路径是否有效.(即,不反转方向)
有没有其他人对解决这个问题的方法有任何见解？
更新: 我在评论中遵循@Karussell建议的方法.
诀窍是使用基于边缘的图形来模拟情况,而不是传统的基于顶点的图形.比赛中提供的输入文件已经根据边缘方便地指定,因此该文件可以很容易地用于构建基于边缘的图形.
该程序使用两个重要的类:Road和Solver.道路有两个整数字段,j1和j2.j1表示源结,j2表示目标结.每条道路都是单向的,这意味着你只能从j1到j2旅行.每条道路还包括相邻道路的链表和父道.Road类还包括静态方法,用于在输入文件中使用的字符串和表示每个连接处的A,B和C点的整数索引之间进行转换.
对于输入文件中的每个条目,我们向HashMap添加两个Road,两个结点之间的每个方向都有一个Road.我们现在列出了在路口之间运行的所有道路.我们只需要通过A,B和C开关将道路连接在一起.如果道路在Junction.A结束,我们会查看从Junction.B和Junction.C开始的道路,并将这些道路添加为邻接道路.buildGraph()函数返回其目标连接点(j2)为"1A"==索引0的Road.
此时,构建了我们的图形.为了找到最短的路径,我只使用BFS来遍历图形.我们保留根没有标记,并开始排队根的邻接.如果我们找到一条目标路口为"1A"(索引0)的道路,那么我们找到了通过起点的最短周期.一旦我们使用每个Road的父属性重建路径,根据问题的要求适当设置开关是一件小事.
感谢Karussell建议采用这种方法.如果你想把你的评论放在答案表中,并附上简短的解释,我会接受.还要感谢@Origin.我必须承认,我没有完全遵循你答案的逻辑,但这肯定不是说它不正确.如果有人使用您的解决方案解决了这个问题,我会非常有兴趣看到它.