代码之家 › 专栏 › 技术社区 › Matthew Iselin

加权路径寻路

path-finding c#

Matthew Iselin · 技术社区 · 15 年前

我正在做一个项目,在那里我需要执行寻路以找到路线 花费最少 . 我真的不在乎这是不是可能的最短路线。到目前为止,这似乎是一个*是不可能的问题,我真的不理解普里姆的算法。

我来解释一下我需要在哪种地图上找到路线。这是一个示例图:

+------|-*----
+------|----|-
+--|--------|-
+@-|----------

“*”是起始位置,“@”是目的地。一行中的“+”符号表示一条直接路线,a)成本与一步相同,b)将整个路线的成本减半。

这意味着从起始位置到目的地有10个“步骤”,通过“+”路线,最终成本为5。使用最左边的“”路线有15个步骤(“”比“-”低,但比“+”差),最终花费15。显然,成本为5的路线是要使用的路线。

现在我在C中实现这一点时遇到了困难。我现在有一个“步骤”功能,如果路径被阻塞或步骤的成本,以及新的位置,它将移动并返回。这很有效,但目前它非常幼稚,因为如果它在“+”之前找到一个“”(这意味着整个旅程的成本要高很多,因为它没有找到更快的路线)。

我在考虑把每个地点都标为“已参观”,但最便宜的路线可能会自行返回。还有许多不同的路径,每个路径都是唯一的,并且每个路径都可以使用不同的路径段(以前的运行可能已经访问过这些路径段)。显然,为了找到最便宜的路径,每个路径都需要被遍历,但是如果不反复搜索相同的路径,我就不知道该怎么做。

如果这样做更简单,我可以限制任何移动,只向目的地移动(即,下降后不能再返回)。

如果有人能提供一些见解,那就太好了!

1 回复 | 直到 15 年前

Sebastian 15 年前

据我所知,地图中的“-”字段是图形节点。每个“-”节点与相邻的“-”字段最多有8个边。8如果允许对角线移动,否则只有4个相邻的“-”节点有效。“-”节点和“”节点之间没有边缘。

这足以实现一个简单的深度优先搜索/广度优先搜索,其中保留一个未访问的节点队列(深度优先的LIFO,广度优先的FIFO)和一个访问的节点列表(以避免循环)。这两种算法都将相对低效,但可以很容易地加以改进。

我不知道“+”节点的含义是什么。从一个“+”模式移动到下一个“+”模式是自由移动吗?如果是这样,您可以使用边缘成本对此进行建模。从“-”节点移动或移动到“+”节点的成本为1,从“+”节点移动到“+”节点的成本为0。

宽度优先搜索算法可以扩展到Dijkstra的算法,该算法计算源和目标之间的最短路径,只要所有图边都为非负:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Dijkstra算法可以通过添加一个简单的启发式算法来进一步改进,使其成为 A* algorithm .如果目标的坐标是二维坐标,则可以使用节点和目标之间的欧几里得距离粗略估计哪个节点最适合跟踪。如果“+”字段是通过地图的隧道,移动成本为零,则A*算法可能没有多大帮助,因为如果您应该向隧道移动,则启发式向目标移动通常是错误的。如果有多个隧道或隧道没有通向您的目的地,那么可能没有比naive 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