在网格中搜索。成本相同时如何选择BFS路径
Searching in grid. How to choose BFS paths when cost are the same
所以我有一个类似网格的图表。假设我想从 (1,1) 到 (3,3)。假设所有边的权重相等，BFS 显然会 return 多条路径（总成本相同）。有没有办法选择最大化转弯的路径（在最短路径中）？
所以在这个例子中
(1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3) 和
(1,1) -> (1,2) -> (2,2) -> (2,3) -> (3,3)
具有相同的长度，但第二个将是更理想的路径。
我知道我可以生成所有路径然后过滤结果。但我想知道是否有办法在搜索中做到这一点。我在考虑改变邻居节点被推入队列的顺序。但是我无法证明它会起作用。
感谢任何帮助、提示或指导！
我认为 BFS 不是用于寻路的正确算法。 doesn't care about weights. You should adjust your edge weights to account for turns, and then use something like Dijkstra's algorithm to find the shortest path, or Floyd–Warshall 找到多条最短路径。
所以我有一个类似网格的图表。假设我想从 (1,1) 到 (3,3)。假设所有边的权重相等，BFS 显然会 return 多条路径（总成本相同）。有没有办法选择最大化转弯的路径（在最短路径中）？
所以在这个例子中 (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3) 和 (1,1) -> (1,2) -> (2,2) -> (2,3) -> (3,3) 具有相同的长度，但第二个将是更理想的路径。
我知道我可以生成所有路径然后过滤结果。但我想知道是否有办法在搜索中做到这一点。我在考虑改变邻居节点被推入队列的顺序。但是我无法证明它会起作用。
感谢任何帮助、提示或指导！
我认为 BFS 不是用于寻路的正确算法。