我正在开展一个项目，我需要执行寻路以找到成本最低的路线 . 我不是最短的路线 . 到目前为止似乎A *是不可能的，老实说，我不理解Prim的算法 .
让我解释一下我需要找到路线的那种 Map . 这是一个示例 Map ：
+------|-*----
+------|----|-
+--|--------|-
+@-|----------
“*”是起始位置，“@”是目的地 . 一行中的“”符号表示直接路线，a）成本与单步相同，b）整个路线的成本减半 .
这意味着通过“”路线从起始位置到目的地有10个“步骤”，最终成本为5.有15个步骤使用最左边的“|” route（“|”的成本低于“ - ”，但差于“”），最终成本为15.显然，成本为5的路径是使用路径 .
现在我在C＃中实现它时遇到了麻烦 . 我目前有一个“步骤”功能，如果方式被阻止或者步骤的成本和新位置，它会移动并返回 . 这很好用，但目前它非常天真，因为它会下降到“|”如果它在“”之前找到一个（这意味着整个行程的成本要高得多，因为它没有找到更快的路线） .
我想将每个位置标记为“已访问”，但最低成本的路径将自行循环，这是完全可信的 . 还有许多不同的路径，每个路径都是唯一的，并且每个路径可以使用不同的路径段（可能已经被先前的运行访问过） . 显然，每条路径都需要遍历才能找到最便宜的路径，但我无法弄清楚如何做到这一点，而不会一遍又一遍地搜索相同的路径 .
如果它变得更简单，我可以限制任何移动仅移动到目的地（即，在下降后不能再次返回） .
如果有人能提供一些见解，那就太好了！
1 回答
据我所知， 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
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/A*_search_algorithm