我正在做一个项目，我需要执行寻路以找到成本最低的路线。我真的不在乎它是否是最短路线。到目前为止，似乎 A* 是不可能的，老实说，我不理解 Prim 的算法。
让我解释一下我需要在哪些 map 上查找路线。这是一个示例 map :
+------|-*----
+------|----|-
+--|--------|-
+@-|----------
“*”是起始位置，“@”是目的地。一行中的“+”号表示一条直接路线，a) 成本与一步相同，b) 整条路线的成本减半。
这意味着通过“+”路线从起始位置到目的地有 10 个“步骤”，最终成本为 5。使用最左边的“|”有 15 个步骤route(“|”比“-”成本低，但比“+”差)，最终成本为15。显然，成本为5的路由是要使用的路由。
现在我无法在 C# 中实现它。我目前有一个“步骤”功能，如果路径被阻塞或步骤成本以及新位置，它会移动并返回。这很好用，但目前它非常天真，因为它会下降一个“|”如果它在“+”之前找到一个(这意味着整个行程的成本要高得多，因为它没有找到更快的路线)。
我正在考虑将每个位置标记为“已访问”，但成本最低的路线将自行环回是完全合理的。还有许多不同的路径，每条路径都是唯一的，并且每条路径可能使用不同的路径段(可能已经被之前的运行访问过)。显然，需要遍历每条路径才能找到最便宜的路径，但如果不一遍又一遍地搜索相同的路线，我不知道该怎么做。
如果它更简单，我可以将任何移动限制为只向目的地移动(即，在下降后不能再次返回)。
如果有人能提供一些见解，那就太好了!
最佳答案
据我了解， map 中的“-”字段是图形节点。每个“-”节点到相邻的“-”字段最多有 8 个边。 8 如果允许对角线移动，否则只有 4 个相邻的“-”节点有效。 “-”节点和“|”之间没有边节点。
这足以实现一个简单的深度优先搜索/广度优先搜索，其中您保留一个未访问节点队列(深度优先为 LIFO，广度优先为 FIFO)和一个已访问节点列表(到避免骑自行车)。这两种算法的效率都相对较低，但可以很容易地加以改进。
我不确定您的“+”节点是什么意思。从一个“+”模式移动到下一个“+”模式是自由移动吗？如果是这样，您可以使用边成本对其进行建模。从“-”节点移动或移动到“-”节点的成本为 1，从“+”节点移动到“+”节点的成本为 0。
广度优先搜索算法可以扩展为 Dijkstra 算法，该算法计算源和目标之间的最短路径，只要所有图形边都是非负的:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Dijkstra 算法可以通过添加一个简单的启发式算法得到进一步改进，使其成为 A* algorithm .如果您在 2D 坐标中有目标坐标，则可以使用节点与目标之间的欧几里德距离作为粗略估计最好遵循哪个节点。如果“+”字段是通过 map 的隧道，移动成本为零，则 A* 算法可能无济于事，因为如果您应该朝隧道移动，则试探性地朝目的地移动通常是错误的。如果有多个隧道或隧道不通向您的目的地，可能没有比朴素的 Dijkstra 算法更好的启发式算法了。
请注意，成本最低的路线不可能包含环路:如果成本最低的路线包含环路，剥离环路仍会以较低的成本产生通往目标的有效路线，这与我们的假设相矛盾从成本最低的路线开始。
看看Cormen's Introduction to Algorithms ，或相关的维基百科页面:
http://en.wikipedia.org/wiki/Shortest_path
http://en.wikipedia.org/wiki/Breadth-first_search
关于c# - 使用加权路线寻路，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1795375/