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

图中的每个边缘都是"上"边缘或者"下"边缘。

有效路径可以不定数量的"向上"，后跟不定数量的"向下"，反之亦然。但是，它不能多次改变方向。

例如，有效路径可能是A"上" B"上" C"下" E"下" F
无效的路径可能是A"向上" B"向下" C"向上" D

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

解决方案

回答

假设我们没有任何启发式方法，那么dijkstra算法的一种变体就足够了。每当我们考虑新的优势时，请存储有关其"祖先"的信息。然后，检查不变性(仅一个方向变化)，如果违反则回溯。

这里的祖先是沿着最短路径经过的所有到达当前节点的边。存储祖先信息的一种好方法是使用一对数字。如果U向上，而D向下，则特定边的祖先可能是" UUUDDDD"，即" 3，4"对。由于不变，我们将不需要第三个数字。

由于我们使用了dijkstra的算法，因此已经解决了寻找多个最短路径的问题。

回答

也许我们可以将图转换为普通的有向图，然后使用现有算法。

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

首先解决从图一开始到图二结束，然后以另一种方式解决，然后检查最短的解决方案。

回答

有人会认为标准BFS应该在这里工作。每当我们将节点添加到打开列表时，都可以将其包装到一个结构中，该结构保存该节点正在使用的方向(向上或者向下)和一个布尔型标志，指示该节点是否已切换方向。这些可用于确定该节点的哪些传出边缘有效。

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

回答

带有特制成本(G得分)和启发式(H得分)功能的A *可以处理它。

对于成本，我们可以跟踪路径中方向变化的次数，并在第二个变化上增加无限的成本(即，切断对那些分支的搜索)。

启发式方法需要更多的思考，尤其是当我们想保持启发式方法可容许(永远不要高估到目标的最小距离)和单调性时。 (只有保证A *找到最佳解决方案的方法。)

也许有更多有关该域的信息可用于创建启发式方法？ (即，图中节点的x，y坐标？)

当然，根据要解决的图的大小，我们可以先尝试使用更简单的算法，例如广度优先搜索或者Dijkstra算法：基本上，每种搜索算法都可以使用，而每一种搜索算法都需要一个成本函数(或者类似函数)反正。

回答

如果我们具有标准的图形搜索功能，例如在库中说" 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"是一个智能函数。

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