使用加权路线进行寻路
我正在开发一个项目，需要执行寻路来找到成本最低的路线。我真的不在乎这是否是最短路线。到目前为止，A* 似乎是不可能的，老实说我不明白 Prim 的算法。
让我解释一下我需要在哪些地图上查找路线。这是一个示例地图：
+------|-*----
+------|----|-
+--|--------|-
+@-|----------
“*”是起始位置，“@”是目的地。一行中的“+”号表示直接路线，a）与单步成本相同，b）整个路线的成本减半。
这意味着从起始位置通过“+”路线到目的地有 10 个“步骤”，最终成本为 5。使用最左边的“|”有 15 个步骤。路线（“|”的成本比“-”低，但比“+”差），最终成本为15。显然，成本为5的路线是要使用的路线。
现在我在 C# 中实现这个方法时遇到了麻烦。我目前有一个“步骤”函数，如果路径被阻塞或步骤的成本以及新位置，它会移动并返回。这很有效，但目前它非常天真，因为它会下降“|”如果它在“+”之前找到一个（这意味着整个行程的成本要高得多，因为它没有找到更快的路线）。
我正在考虑将每个位置标记为“已访问”，但成本最低的路线完全有可能会自行循环。还有许多不同的路径，每条路径都是唯一的，并且每条路径都可能使用不同的路径段（可能已经被先前的运行访问过）。显然，需要遍历每条路径才能找到最便宜的路径，但我不知道如何做到这一点，而不最终一遍又一遍地搜索相同的路线。
如果它使它更简单，我可以限制任何移动仅向目的地移动（即，在下降后不能再次返回）。
如果有人可以提供一些见解，那就太好了！
I'm working on a project where I need to perform pathfinding to find the route which costs the least. I don't really care if it's the shortest route possible. So far it seems A* is out of the question and I honestly do not understand Prim's algorithm.
Let me explain the kind of maps that I need to find routes on. This is an example map:
+------|-*----
+------|----|-
+--|--------|-
+@-|----------
The "*" is the start location, the "@" is the destination. The "+" signs in a line indicate a direct route which a) costs the same as a single step, and b) halves the cost of the entire route.
This means there are 10 "steps" from the start position to the destination via the "+" route, which ends up with a cost of 5. There are 15 steps to use the left-most "|" route ("|" is a lower cost than "-", but worse than "+"), which ends up with a cost of 15. Obviously, the route with a cost of 5 is the route to use.
Now I'm having trouble implementing this in C#. I currently have a "step" function which moves and returns if the way was blocked or the cost of the step, and the new position. This works well, but at the moment it is extremely naive in that it'll go down a "|" if it finds one before a "+" (which means the entire trip costs significantly more, as it hasn't found the faster route).
I was thinking of marking each location as "visited", but it's completely plausible that the lowest-cost route will loop back on itself. There are also many different paths, each of which is unique, and each of which may use different path segments (that may have already been visited by a previous run). Obviously each path needs to be traversed in order to find the cheapest path, but I can't figure out how to do that without ending up searching the same routes over and over again.
If it makes it simpler, I can limit any movement to only move towards the destination (ie, can't go back up again after going down).
If anyone could provide some insight, that'd be great!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
据我了解，地图中的“-”字段是图形节点。每个“-”节点至多有 8 个到相邻“-”字段的边。如果允许对角线移动，则为 8，否则只有 4 个相邻的“-”节点有效。 “-”节点和“|”之间没有边节点。
这足以实现简单的深度优先搜索/广度优先搜索，其中保留未访问节点的队列（深度优先为 LIFO，广度优先为 FIFO）和已访问节点列表（以避免循环） 。这两种算法的效率都相对较低，但可以很容易地进行改进。
我不确定你的“+”节点的含义是什么。从一个“+”模式移动到下一个“+”模式是自由移动吗？如果是这样，您可以使用边缘成本对此进行建模。从“-”节点移动或移动到“-”节点的成本为 1，从“+”节点移动到“+”节点的成本为 0。
广度优先搜索算法可以扩展到 Dijkstra 算法，该算法计算源之间的最短路径和目的地，只要所有图边都是非负的：
http://en.wikipedia.org /wiki/Dijkstra%27s_algorithm
通过添加简单的启发式算法，可以进一步改进 Dijkstra 算法，使其成为 A* 算法。如果您的目标坐标为 2D 坐标，则可以使用节点与目标之间的欧几里得距离作为最好遵循哪个节点的粗略估计。如果“+”字段是穿过地图的隧道，移动成本为零，则 A* 算法可能没有多大帮助，因为如果您应该朝隧道移动，则试探性地朝目的地移动通常会是错误的。如果有多个隧道或没有通向目的地的隧道，可能没有比朴素的 Dijkstra 算法更好的启发式算法了。
请注意，成本最低的路线不可能包含环路：如果成本最低的路线包含环路，则剥离环路仍然会产生一条到达目标的有效路线，成本较低，这与我们从成本最低的路线。
查看 Cormen 的算法简介，或相关的维基百科页面：
< a href="http://en.wikipedia.org/wiki/Shortest_path" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Shortest_path
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/A*_search_algorithm
From what I understand, the '-' fields in your map are graph nodes. Each '-' node has at most 8 edges to neighboring '-' fields. 8 if you allow diagonal movement, otherwise only 4 neighboring '-' nodes are valid. There is no edge between a '-' node and a '|' node.
This is enough to implement a simple depth-first search / breadth-first-search in which you keep a queue of unvisted nodes (LIFO for depth-first, FIFO for breadth-first) and a list of visited nodes (to avoid cycling). Both algorithms will be relatively inefficient, but can be easily improved upon.
I'm not sure what the meaning of your '+' nodes is. Is moving from one '+' to the next '+' mode a free move? If so, you can model this using edge costs. A move from or to a '-' node has cost 1, a move from '+' to '+' node has cost 0.
The breadth-first-search algorithm can be extended to Dijkstra's algorithm that calculates the shortest path between your source and destination as long as all graph edges are non-negative:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
The Dijkstra algorithm can be further improved with the addition of a simple heuristic, making it the A* algorithm. If you have the coordinates of your goal in 2D coordinates, you could use the euclidian distance between a node and the goal as a rough estimate of which node is best to follow. If the '+' fields are something of a tunnel through your map with zero cost to move, the A* algorithm may not help that much because heuristically moving towards your destination will often be wrong if you should have moved towards the tunnel. If there are multiple tunnels or tunnels not leading to your destination, there may not be an heuristic better than the naive Dijkstra algorithm.
Please note that it is impossible for the lowest-cost route to contain a loop: If the lowest-cost route contained a loop, stripping the loop would still yield a valid route to the goal with lower cost contradicting the assumption that we started from a route with lowest-cost.
Have a look at Cormen's Introduction to Algorithms, or the relevant Wikipedia pages:
http://en.wikipedia.org/wiki/Shortest_path
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/A*_search_algorithm