图搜索算法
我正在寻找具有一些不寻常属性的图算法。
图中的每条边要么是“上”边，要么是“下”边。
有效路径可以经过无限数量的“向上”，然后是无限数量的“向下”，反之亦然。 然而，它不能多次改变方向。
例如，有效路径可能是 A“向上”B“向上”C“向下”E“向下”F 无效路径可能是 A“向上”B“向下”C“向上”D
查找两个节点之间最短有效路径的好算法是什么？ 找到所有等长的最短路径怎么样？
I'm looking for a graph algorithm with some unusual properties.
Each edge in the graph is either an "up" edge or a "down" edge.
A valid path can go an indefinite number of "up"'s followed by an indefinite number of "down"'s, or vice versa. However it cannot change direction more than once.
E.g., a valid path might be A "up" B "up" C "down" E "down" F
an invalid path might be A "up" B "down" C "up" D
What is a good algorithm for finding the shortest valid path between two nodes? What about finding all of the equal length shortest paths?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果您有标准的图形搜索功能，例如库中的 Graph.shortest(from, to)，您可以在 C#/伪代码中循环和最小化：
如果您需要记住最小路径如果您的标准函数返回数据，您也可以发音
where
myMin应该比较两个[fst, nxt, C, AC, BD]元组并离开距离较小的一个，或两者兼而有之，并假设reduce是一个智能函数。如果我们的图形很大并且根本不使用内存（如果它们是动态生成的，则这是可能的），这会产生一些内存开销，但实际上并没有任何速度开销，恕我直言。
If you have a standard graph search function, say
Graph.shortest(from, to)in a library, you can loop and minimize, in C#/pseudocode:If you need to remember the minimum path/paths and it so happens that your standard function returns you the data, you could also pronounce
where
myMinshould compare two[fst, nxt, C, AC, BD]tuples and leave the one that has lower distance, or both and assumingreduceis a smart function.This has some memory overhead if our graphs are large and don't use memory at all (which is possible if they are generated dynamically), but not really any speed overhead, imho.
假设您没有任何启发式方法，dijkstra 算法 的变体应该足够了。 每次您考虑新边缘时，请存储有关其“祖先”的信息。 然后，检查不变量（仅一个方向变化），如果违反则回溯。
这里的祖先是沿着最短路径到达当前节点所遍历的所有边。 存储祖先信息的一个好方法是作为一对数字。 如果 U 向上，D 向下，则特定边的祖先可能是
UUUDDDD，即3, 4对。 由于不变量，您不需要第三个数字。由于我们使用了迪杰斯特拉算法，因此已经解决了寻找多条最短路径的问题。
Assuming you don't have any heuristics, a variation of dijkstra's algorithm should suffice pretty well. Every time you consider a new edge, store information about its "ancestors". Then, check for the invariant (only one direction change), and backtrack if it is violated.
The ancestors here are all the edges that were traversed to get to the current node, along the shortest path. One good way to store the ancestor information would be as a pair of numbers. If U is up, and D is down, a particular edge's ancestors could be
UUUDDDD, which would be the pair3, 4. You will not need a third number, because of the invariant.Since we have used dijkstra's algorithm, finding multiple shortest paths is already taken care of.
也许您可以将图转换为正常的有向图，然后使用现有算法。
一种方法是将图分成两个图，一个具有所有向上边缘，一个具有所有向下边缘，并且具有图一上的所有节点与图二上的相应节点之间的有向边。
首先解决从图一开始到图二结束的问题，然后反过来，然后检查最短的解决方案。
Maybe you can transform your graph into a normal directed graph and then use existing algorithms.
One way would be to split the graph into two graphs, one with all the up edges and one with all the down edges and with directed edges between all the nodes on graph one and the corresponding node on graph two.
First solve for starting in graph one and ending in graph two and then the other way around, then check the shortest solution.
有人会认为你的标准 BFS 应该在这里工作。 每当您将节点添加到打开列表时，您都可以将其包装到一个结构体中，该结构体保存它正在使用的方向（向上或向下）以及指示它是否已切换方向的布尔标志。 这些可用于确定该节点的哪些传出边是有效的。
要查找所有长度相等的最短路径，请在结构中包含到目前为止遍历的边数。 当找到第一条最短路径时，记下路径长度并停止向打开列表添加节点。 继续遍历列表中的剩余节点，直到检查完当前长度的所有路径，然后停止。
One would think your standard BFS should work here. Whenever you add a node to the open list, you can wrap it into a struct that holds which direction it is using (up or down) and a boolean flag indicating whether it has switched directions yet. These can be used to determine which outgoing edges from that node are valid.
To find all shortest paths of equal length, include the number of edges traversed so far in your struct. When you find your first shortest path, make a note of the path length and stop adding nodes to the open list. Keep going through the remaining nodes on the list until you have checked all paths of the current length, then stop.
A* 具有特制的成本（G 分数）和启发式（H 分数）函数可以处理它。
对于成本，您可以跟踪路径中方向变化的次数，并在第二次变化时添加无限成本（即切断对这些分支的搜索）。
启发式方法需要更多的思考，特别是当您想要保持启发式方法可接受（永远不要高估到目标的最小距离）和单调性时。 （保证 A* 找到最佳解决方案的唯一方法。）
也许有更多关于可用于创建启发式的域的信息？ （即图中节点的 x,y 坐标？）
当然，根据您要解决的图的大小，您可以首先尝试更简单的算法，例如广度优先搜索或 Dijkstra 算法：基本上每个搜索算法都可以，并且对于每一个，你都需要一个成本函数（或类似的）。
A* with a specially crafted cost (G score) and heuristic (H score) function can handle it.
For the cost you could keep track of the number of direction changes in the path and add infinite cost on the second change (ie. cut off the search for those branches).
The heuristic takes some more thought, especially when you want to keep the heuristic admissible (never overestimates minimum distance to goal) and monotonic. (Only way to guarantee A* finds an optimal solution.)
Maybe there is more information about the domain available to create the heuristic? (ie. x,y coordinates of the nodes in the graph?)
Of course, depending on the size of the graph you want to solve, you could first try simpler algorithms like breadth first search or Dijkstra's algorithm: basically every search algorithm will do, and for every one you will need a cost function (or similar) anyway.