图搜索算法

假设你没有任何启发式方法, dijkstra's algorithm 应该足够了。每次考虑新的边缘时,都要存储有关其“祖先”的信息。然后,检查不变量(只有一个方向更改),如果违反了,则进行回溯。

这里的祖先是沿着最短路径遍历以到达当前节点的所有边。存储祖先信息的一个好方法是使用一对数字。如果u是上的,d是下的,那么一个特定边缘的祖先可能是 UUUDDDD 哪一对呢 3, 4 . 由于不变量的存在,您将不需要第三个数字。

由于我们已经使用了Dijkstra的算法,因此找到多条最短路径已经得到了考虑。

也许你可以将你的图转换成一个普通的有向图,然后使用现有的算法。

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

首先求出从图1开始到图2结束的解,然后求出最短解。

有人会认为你的标准 BFS 应该在这里工作。无论何时向打开的列表中添加节点,都可以将其包装成一个结构,该结构保持其使用的方向(向上或向下),以及一个布尔标志,指示其是否已切换方向。这些可用于确定该节点的哪些传出边缘有效。

要查找所有长度相等的最短路径,请包括结构中迄今遍历的边数。找到第一条最短路径后,记下路径长度并停止向打开列表中添加节点。继续浏览列表上的其余节点,直到选中当前长度的所有路径,然后停止。

A* 有了一个专门设计的成本(G分数)和启发式(H分数)函数可以处理它。

对于成本,您可以跟踪路径中方向更改的数量,并在第二个更改上添加无限的成本(即切断对这些分支的搜索)。

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

也许有更多关于创建启发式域的信息?(即图中节点的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 是一个智能功能。

如果我们的图很大,并且根本不使用内存(如果动态生成的话,这是可能的),那么这会有一些内存开销,但实际上不会有任何速度开销,imho。