问题标签 [path-finding]

我正在使用具有两种状态“开”和“关”的正方形网格。我有一个相当简单的Connected Component Labeling算法，它可以找到所有“ON”组件。通常，但不总是，只有一个“ON”组件。

我希望构建一个算法，该算法将开/关单元格矩阵、组件标记（可能格式化为单元格的哈希集列表）以及自标记形成以来已更改的单元格列表作为输入，并输出一个新的标签。显而易见的解决方案是从头开始重新计算，尽管这效率不高。通常，已更改的单元格列表会很小。

在更改列表只是已打开的单元格的情况下，这很容易做到：

但是，如果更改包含任何已关闭的单元格，我不知道该怎么做。请记住，所有 ON 单元格必须恰好是一个组的成员。因此，一种解决方案是获取与新关闭的单元格相邻的每个单元格，并查看它们是否相互连接（例如，使用 * 寻路）。这将产生 1-4 个连续的组（除非该单元是其组中唯一的单元，因此有 0 个相邻单元要检查，在这种情况下它会产生 0 个组）。然而，这仅比从头开始好一点，因为通常（但不总是）将这些相邻的方格连接在一起就像找到一个连续的组一样困难（除非有人建议用一种聪明的方法来做到这一点）。此外，如果有很多更改的单元格，这有点可怕……尽管我承认通常没有。

上下文，对于那些坚持知道我为什么这样做的人：Nurikabe谜题中的一个规则是你可能只有一组连续的墙。上面是我试图解决以提高速度（并玩寻路）的问题的简化。基本上，我希望检查连续的墙壁，而不会浪费从以前的此类测试中获得的信息。我想看看我的求解器中有多少地方可以利用以前的信息来提高速度，因为当 O(f(Δ)) 时使用 O(f(N)) 算法似乎有点痛苦算法就足够了（N 是拼图的大小，Δ 是自上次运行算法以来所做的更改）。

剖析确实表明改进此算法会影响执行时间，但这是一个有趣的项目，而不是为了利润，所以它并不重要，除了能够衡量更改是否有任何影响。

注意：我省略了解释我当前的算法，但它基本上通过在它找到的第一个 ON 方格上执行基于堆栈的Flood Fill算法来工作，然后检查是否还有更多 ON 方格（这意味着有多个组，它不会费心检查）。

编辑：增强想法：Yairchu 和 John Kugelman 的建议在我的脑海中形成了这种改进，这实际上并不是这个问题的解决方案，但可能会使这部分代码和其他几段代码运行得更快：

电流回路：

改进思路：

这将需要维护几个 m.NeighborsXX 实例（一个用于需要增强的每种匹配类型）并在正方形发生变化时全部更新它们。我需要对此进行基准测试，看看它是否真的有帮助，但它看起来像是用一些内存换取一些速度的标准案例。

前段时间我问了一个关于java 2d pathfinding的问题... Pathfinding 2D Java game？

我正在开发的游戏是基于主题医院的想法。从我的问题中选择的答案，A* 寻路，链接很棒，非常有帮助。我最终将把它应用到我的游戏中，但是我还有一些关于它的问题/问题。

在我的游戏中，地图会改变。本教程假设地图是静态的（我认为）。我一直在看代码，据我所知，我只需要创建一个方法来调用来更新寻路代码中的游戏地图。

其次，我看到了 GameMap 类。我有自己的班级，叫做 Board，里面有所有的瓷砖。我相信我可以将 GameMap 上的方法集成到我的 Board 类中。正确的？

第三，我一直在研究任何房间都将被视为阻塞的推理。我的意思是，房间覆盖的任何方格都被算作阻塞。我在想人们会从哪里进入房间。然后，他们将不得不在这些房间周围移动才能到达不同的地方。我在想我会为每个正方形反转 Blocked 布尔值，但这有两个原因是行不通的。1，房间可能有相邻的墙壁，并且可能会破坏寻路。2、如果阻塞状态只是简单的倒置，那么房间内的任何实心物品倒置后都会被视为不实心，这可能会在它们与墙壁接触时出现问题。

想一想，如果您可以将正方形的边制作成块状而不是实际的整个正方形会更好。这一定是可能的，但我只是通过使用上一个问题中的教程获得，并且不确定我是否应该尝试更改 A* 来执行此操作，或者解决房间物品问题的解决方法。

对这些问题有什么想法或建议吗？我今天正在实施简单的路径查找，但只是提前思考。

我正在开发一个简单的基于 2d 网格的 sim 游戏，并且具有功能齐全的寻路功能。

我使用在上一个问题中找到的答案作为实现 A* 路径查找的基础。（寻路 2D Java 游戏？）。

为了真正向您展示我的要求，我需要向您展示我制作的视频屏幕截图。我只是在测试这个人将如何移动到一个位置并再次返回，这就是结果......

http://www.screenjelly.com/watch/Bd7d7pObyFo

根据方向选择不同的路径，结果出人意料。有任何想法吗？

我需要在 google appengine 中存储一个大型动态无向图，最好的方法是什么？图表示必须能够支持快速拉出一组顶点（用于在页面上呈现）和来自特定顶点的所有链接，以及跨图的寻路（尽管实际上并不需要最佳路径，只是一个相当好一个）

我对这个主题的想法：最明显的方法是拥有一个顶点模型和一个引用两个顶点的边模型，但是听起来它最终会为每个操作使用大量查询，我想知道是否有更好的方法（也许以某种方式将链接信息构建到每个顶点中）

好的，这是一个家庭作业问题，我只是不知道我应该如何开始。一些帮助和提示将不胜感激。

我需要使用启发式函数来解决迷宫类型问题。

假设我有一个 5x5 的网格，一个机器人在位置 (1,5)，我的目标是将机器人移动到 (5,1)。一路上几乎没有障碍，比如说(X,1,3)，，，，(X,2,3)(X,5,3)(X,4,2)

打印出机器人经过的路线。

我正在考虑使用贪婪的最佳优先搜索算法来找到机器人到达目标的路径

我的问题是，我是新来的计划不知道我应该如何开始解决这个问题。

我是不是该 ？

解决问题？

如何创建网格？我应该如何解决这个问题？如何打印出机器人行走的步数？

非常感谢您的帮助:)

我正在做一个项目，我需要执行寻路以找到成本最低的路线。我真的不在乎这是否是最短的路线。到目前为止，似乎 A* 是不可能的，老实说，我不了解 Prim 的算法。

让我解释一下我需要在哪些地图上查找路线。这是一个示例地图：

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

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

现在我无法在 C# 中实现它。我目前有一个“步进”函数，如果路径被阻塞或步进成本以及新位置，它会移动并返回。这很好用，但目前它非常幼稚，因为它会下降一个“|” 如果它在“+”之前找到一个（这意味着整个行程的成本要高得多，因为它没有找到更快的路线）。

我正在考虑将每个位置标记为“已访问”，但完全有可能最低成本的路线会自行循环。还有许多不同的路径，每一个都是唯一的，并且每一个都可能使用不同的路径段（可能已经被之前的运行访问过）。显然，需要遍历每条路径才能找到最便宜的路径，但如果不一遍又一遍地搜索相同的路径，我无法弄清楚如何做到这一点。

如果它使它更简单，我可以将任何运动限制为仅向目的地移动（即，下降后不能再次返回）。

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

我有一个这样存储的数组：

我正在尝试找到一种更简单的方法来查找到某个 ID 的路线。现在我正在使用 foreach 遍历所有可能的数组并找到路径。

例子：

如果我的问题没有意义，我将其归咎于试图找到一个好的解决方案所花费的时间......

我正在尝试编写路由功能，但似乎无法获得所需的结果。这是到目前为止的代码。Predecessor 找到链接到 N 的节点并将其作为 P 返回。

当我运行traceroute(placeA, Y).它时，它会返回此数据.. Y = [ (_G575, _G575)|_G579] .

基本上对于 traceroute 的第一行，如果任何成员是其自身的前身，我将尝试终止递归。第二部分应该遍历所有节点并将它们添加到列表（L）中。

节点存储为 [(placeA,placeB),(placeB,placeC)]，列表应存储为 [placeA,placeB,placeC]

我不明白为什么我会得到这些结果。

我发现 AIMA（人工智能：现代方法）中的算法描述根本不正确。“必要”是什么意思？内存限制是多少？队列大小或处理的节点？如果当前节点根本没有子节点怎么办？

我想知道这个算法本身是否正确。因为我搜索了互联网，还没有人实现它。

谢谢。

（这不完全是我遇到的问题，但它是同构的，我认为这种解释对其他人来说最容易理解。）

假设我在n维空间中有一组点。以 3 个维度为例：

我还有一组向量来描述这个空间中可能的运动：

现在，给定一个点dest，我需要找到一个起点p和一组矢量移动，它们将以最有效的方式将我带到dest 。效率被定义为“最少的移动次数”，不一定是“最小的线性距离”：如果移动集可以让您以更少的移动到达那里，则允许选择比其他候选者更远离dest的p 。move 中的向量必须是可用向量的严格子集；您不能多次使用同一个向量，除非它在输入集中出现多次。

我的输入包含约 100 个起点和约 10 个向量，我的维数为约 20。起点和可用向量将在应用程序的生命周期内固定，但我会为许多不同的终点寻找路径。我想优化速度，而不是内存。算法失败是可以接受的（找不到到dest的可能路径）。

使用已接受的解决方案进行更新

我采用了一种与下面标记为“已接受”的解决方案非常相似的解决方案。我遍历所有点和向量，并构建所有可到达点的列表以及到达它们的路线。我将此列表转换为 < dest , p+vectors > 的散列，为每个目标点选择最短的向量集。（还有一点对哈希大小的优化，这里不相关。）随后的dest查找在恒定时间内发生。