图搜索算法
问题是这样的：
我必须考虑以下因素找到一条从起点到目的地的路径。
在给定的图中，一个点可以是：
(1) A Checkpoint-->这一点必须 出现在最终计算的路径中
(2) A Mine-->这一点不应该
出现在计算出的最终路径中(3)中性点-->这点
可能/可能不会出现在决赛中
路径计算
我需要一个算法。
Here is the problem:
I have to find a path from the starting point to the destination with following considerations.
In the given graph a point could be either:
(1) A Checkpoint--> this point must
be there in the final path calculated(2) A Mine--> this point should not
be there in the final path calculated(3) A neutral point--> this point
may/may not be there in the final
path calculated
I need an algorithm for this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
首先清除地雷并列出检查点清单。
那么你几乎肯定必须进行深度优先或广度优先搜索。哪一个取决于图表。我建议尝试广度优先搜索，并采用适当的修剪启发式方法。探索者从起点开始，然后每当它有选择时，它就会复制自己并双向前进。它保留两个列表：它访问过的检查点，以及自上次检查点以来它访问过的中立节点。当它访问中立节点时，它会将其检查点列表写在墙上，并删除属于其自己的子集的任何列表。如果遇到以下条件之一，它将自行终止：
它没有经过所有检查站就到达了目的地。这应该足以让您开始。根据图表的不同，还有其他可能值得的优化（例如消除死胡同）。
（编辑：当我看到它会使某些图表变得不可能时，就划掉了最后一个条件。）
First remove the mines and make a list of the checkpoints.
Then you'll almost certainly have to do a depth-first or breadth-first search. Which one depends on the graph. I'd suggest trying a breadth-first search, with a decent pruning heuristic. A seeker starts at the starting point, then whenever it has a choice to make it copies itself and goes both ways. It keeps two lists: the checkpoints it's visited, and the neutral nodes it's visited since its last checkpoint. When it visits a neutral node it writes its checkpoint list on the wall, and erases any lists that are subsets of its own. It will terminate itself if it encounters one of the following conditions:
It arrives at the destination without having visited all the checkpoints.That should be enough to get you started. There are other optimisations (such as removing dead ends) that may be worthwhile, depending on the graph.
(EDIT: scratched that last condition when I saw that it would make some graphs impossible.)
如果您需要按特定顺序访问检查点，Dijkstra 算法是一个简单的解决方案。您可以针对图的子集使用该算法。子集将是图，其中起始节点和结束节点是检查点（或图的开始或结束节点）。您可以使用边权重来表示不应访问的节点。
不过，我建议A寻路*，因为它可能更适合您想要做的事情。那里有很多示例代码。
这是一个很好的入门教程：
A* 初学者寻路
您可以将您的地雷和检查点表示为图表中的权重，或使用启发式方法。这很可能取决于检查点是否已排序。
Gamedev.net 是你的朋友。祝你好运！
If your checkpoints need to be visited in a specific order, Dijkstra's algorithm is an easy solution. You can use the algorithm against subsets of the graph. The subsets will be graphs where the starting and ending nodes are checkpoints (or the opening or closing nodes of the graph). You can use edge weights to represent nodes that shouldn't be visited.
However, I would suggest A Pathfinding* as it is probably more suited to what you are trying to do. There is a lot of sample code out there.
Here is a good tutorial to get you started:
A* Pathfinding for Beginners
You can represent your mines and checkpoints as weights in the graph, or by using heuristics. This will most likely depend on whether checkpoints are ordered or not.
Gamedev.net is your friend. Good luck!
好吧，我认为你可以使用 Dijkstra 算法 （或者类似的东西，我建议Dijkstra 的原因是它详尽且通用，并且您没有提供太多有关数据的信息）来找到最短路径...通过这些修改：
会找到最短路径（权重最低的路径），保证穿过所有检查站并避开所有地雷。
但这不是一个快速的算法，因此如果您的地图太大，它可能无法工作。
Well, I think you can use Dijkstra's algorithm (Or something similar, I'm suggesting Dijkstra's because it is exhaustive and general and you did not provide that much info about your data) to find the shortest path... with these modifications:
Dijkstra's will find the shortest path (path with the lowest weight), which is guaranteed to cross all the checkpoints and avoid all the mines.
It's not a fast algorithm though, so it might not work if your map is too large.
就我个人而言，我会为此使用深度优先搜索（DFS）。 Dijkstras 算法用于基于某些边缘距离函数计算最短路径（您没有提到节点之间的任何距离，所以我假设没有）。
DFS 可以这样修改（假设 s 是源，t 是目的地）：
这可能不是最有效的算法，但应该适用于寻找路径。也不保证您从 DFS 结果中选择的路径是最佳路径。
（这假设可以按任何顺序访问检查点）
Personally I would use a depth first search (DFS) for this. Dijkstras algorithm is for computing a shortest path, based on some edge distance function (you haven't mentioned any distances between nodes so I assumed there are none).
The DFS can be modified thus (assuming s is your source and t is the destination):
This may not be the most efficient algorithm, but should work for finding a path. There are also no promises that a path you pick from the DFS result is the optimal path.
(This assumes checkpoints can be visited in any order)