图搜索算法

我正在寻找一种具有一些异常特性的图算法。

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

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

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

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

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

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

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

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

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

首先求解从图一开始并在图二结束，然后以另一种方式求解，然后检查最短解。

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

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

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

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

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

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

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

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

如果您需要记住最小路径，并且碰巧您的标准函数返回了数据，您还可以发音

其中，myMin应该比较两个[fst, nxt, C, AC, BD]元组，并保留一个距离较小的元组，或者同时保留两者，并假定reduce是一个灵巧函数。

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