7

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

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

一条有效的路径可以经过不定数量的“up”，然后是不定数量的“down”，反之亦然。但是，它不能多次改变方向。

例如，有效路径可能是 A “up” B “up” C “down” E “down” F 无效路径可能是 A “up” B “down” C “up” D

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

4

5 回答 5

11

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

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

由于我们使用了 dijkstra 算法，因此已经可以找到多个最短路径。

于 2008-09-09T21:14:27.100 回答
4

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

一种方法是将图拆分为两个图，一个具有所有上边，一个具有所有下边，并且在图 1 上的所有节点与图 2 上的相应节点之间具有有向边。

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

于 2008-09-09T21:15:55.630 回答
2

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

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

于 2008-09-09T21:16:26.720 回答
2

具有特制成本（G 分数）和启发式（H 分数）功能的A*可以处理它。

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

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

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

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

于 2008-09-09T21:22:44.753 回答
1

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

[ (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)

wheremyMin应该比较两个[fst, nxt, C, AC, BD]元组并留下距离较短的元组，或者两者兼而有之，并假设reduce是一个智能函数。

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

于 2009-06-12T09:32:59.187 回答