图搜索算法

Question

我正在寻找具有一些不寻常属性的图算法。

图中的每条边要么是“上”边，要么是“下”边。

有效路径可以经过无限数量的“向上”，然后是无限数量的“向下”，反之亦然。然而，它不能多次改变方向。

例如，有效的路径可能是“ up” b“ up” up“ c” d down“ e” e“ down” f无效的路径可能是“ up” up'b“ down” c“ up” d d

寻找两个节点之间最短有效路径的好算法是什么？找到所有等长的最短路径怎么样？

Answer 1

假设你没有任何启发式的方法， 迪杰斯特拉算法 应该足够了。每次您考虑新边缘时，请存储有关其“祖先”的信息。然后，检查不变量（仅一个方向变化），如果违反则回溯。

这里的祖先是沿着最短路径到达当前节点所遍历的所有边。存储祖先信息的一个好方法是作为一对数字。如果 U 向上，D 向下，则特定边的祖先可能是 UUUDDDD, ，这将是一对 3, 4. 。由于不变量，您不需要第三个数字。

由于我们使用了迪杰斯特拉算法，因此已经解决了寻找多条最短路径的问题。

Answer 2

也许您可以将图转换为正常的有向图，然后使用现有算法。

一种方法是将图分成两个图，一个具有所有向上边缘，另一个具有所有向下边缘，并且具有图一上的所有节点与图二上的相应节点之间的有向边。

首先解决从图一开始到图二结束的问题，然后反过来，然后检查最短的解决方案。

Answer 3

人们会认为你的标准 广度FS 应该在这里工作。每当您将节点添加到打开列表时，您都可以将其包装到一个结构体中，该结构体保存它正在使用的方向（向上或向下）以及指示它是否已切换方向的布尔标志。这些可用于确定该节点的哪些传出边是有效的。

要查找所有长度相等的最短路径，请在结构中包含到目前为止遍历的边数。当找到第一条最短路径时，记下路径长度并停止向打开列表添加节点。继续遍历列表中的剩余节点，直到检查完当前长度的所有路径，然后停止。

Answer 4

A* 使用特制的成本（G 分数）和启发式（H 分数）函数可以处理它。

对于成本，您可以跟踪路径中方向变化的次数，并在第二次变化时添加无限成本（即切断对这些分支的搜索）。

启发式方法需要更多的思考，特别是当您想要保持启发式方法可接受（永远不要高估到目标的最小距离）和单调性时。（保证 A* 找到最优解的唯一方法。）

也许有更多关于可用于创建启发式的域的信息？（IE。图中节点的 x,y 坐标？）

当然，根据您想要求解的图的大小，您可以首先尝试更简单的算法，例如广度优先搜索或 Dijkstra 算法：基本上每一种搜索算法都可以，而且对于每一种算法，你都需要一个成本函数（或类似的）。

Answer 5

如果您有标准的图形搜索功能，比如说 Graph.shortest(from, to) 在库中，您可以在 C#/伪代码中循环和最小化：

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

如果您需要记住最小路径，并且您的标准函数恰好返回数据，您也可以发音

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

在哪里 myMin 应该比较两个 [fst, nxt, C, AC, BD] 元组并保留距离较小的那个，或两者都保留并假设 reduce 是一个智能功能。

如果我们的图形很大并且根本不使用内存（如果它们是动态生成的，则这是可能的），这会产生一些内存开销，但实际上并没有任何速度开销，恕我直言。