graph-theory - 图搜索算法

Question

这就是问题所在：
我必须找到从起点到目的地的路径，并考虑以下因素。

在给定的图中，一个点可以是：

• (1) A Checkpoint-->这个点必须在计算的最终路径中

• (2) A Mine-->这个点
  在计算的最终路径中不应该存在

• (3) 中性点--> 该点
  可能/可能不在
  计算的最终路径中

我需要一个算法。

Answer 1

首先清除地雷并列出检查点。

然后，您几乎可以肯定必须进行深度优先或广度优先搜索。哪一个取决于图表。我建议尝试广度优先搜索，并采用适当的修剪启发式方法。搜索者从起点开始，然后只要有选择，它就会复制自己并双向进行。它保留两个列表：它访问过的检查点，以及自上次检查点以来访问过的中性节点。当它访问一个中性节点时，它会将其检查点列表写在墙上，并删除任何属于它自己子集的列表。如果遇到以下情况之一，它将自行终止：

• 它访问已经在其列表之一上的节点。
• 它在墙上看到一个检查点列表，它是它自己的超集。
• 它在没有访问所有检查站的情况下到达目的地。

这应该足以让你开始。根据图表，还有其他可能值得的优化（例如消除死角）。

（编辑：当我看到最后一个条件会使某些图表变得不可能时，就抓到了。）

Answer 2

如果您的检查点需要按特定顺序访问，Dijkstra 算法是一个简单的解决方案。您可以针对图形的子集使用该算法。子集将是图，其中开始和结束节点是检查点（或图的打开或关闭节点）。您可以使用边权重来表示不应访问的节点。

但是，我建议A Pathfinding * 因为它可能更适合您尝试做的事情。那里有很多示例代码。

这是一个很好的教程，可以帮助您入门：

A* 初学者寻路

您可以将您的地雷和检查点表示为图表中的权重，或使用启发式方法。这很可能取决于检查点是否已排序。

Gamedev.net 是你的朋友。祝你好运！

Answer 3

我个人会为此使用深度优先搜索（DFS）。Dijkstras 算法用于计算最短路径，基于一些边缘距离函数（你没有提到节点之间的任何距离，所以我假设没有）。

因此可以修改 DFS（假设 s 是您的源，t 是目标）：

• 首先删除所有“我的”节点及其相邻边缘。如果一个矿节点不能被访问，那么它也可能被移除，因为路径中不能使用来自它的传入或传出边。
• 从节点 s 执行 DFS。
• 执行 DFS 后，您将拥有一组节点序列，例如 [s, a, b, d, e, t], [s, b, d, t, e] 等。
• 如果这些序列中的任何一个包含节点 t 之前的所有检查点节点，那么这是一条合适的路径。
• 如果 DFS 结果中没有这样的序列，则没有满足条件的路径。您要么错过检查站，要么参观矿井才能到达目的地。

这可能不是最有效的算法，但应该适用于寻找路径。也没有保证您从 DFS 结果中选择的路径是最佳路径。

（这假设可以按任何顺序访问检查点）

Answer 4

好吧，我认为您可以使用Dijkstra 的算法（或类似的算法，我建议使用 Dijkstra 的算法，因为它详尽且通用，并且您没有提供有关数据的太多信息）来找到最短路径...通过以下修改：

1. 检查点的值等于中性点数量的负数。
2. 地雷的值等于中性点的数量。
3. 中性点的值为 1。

Dijkstra 会找到最短的路径（权重最小的路径），保证穿过所有检查站并避开所有地雷。

不过，这不是一个快速算法，因此如果您的地图太大，它可能无法工作。