标签: path-finding

我正在做一项任务,我必须使用一颗星来解决一个15谜题(在C中).

启发函数是曼哈顿距离(又名出租车距离).

我们给出了一个示例输入/输出,其中电路板在22次移动中和扩展395个节点(电路板状态)后解决(即我们必须查看395个节点的子节点)

通过'正确'启发式,我的意思是我的功能与用于产生样本输出的功能相同并产生正确的距离.

问题是我的解决方案扩展了超过400个节点以找到解决方案(它是最佳的22个移动而不是另一个).

我注意到数字的变化取决于我生成子节点的顺序(向上,向左,向下,向右或其他方向移动空间区域).

有24种方法可以向上,向下,向左和向右移动空间磁贴以生成子项,我尝试了所有这些,但它们都没有扩展395个节点.

为什么会这样？

术语:

• node:每个节点都是15-puzzle board的配置
• children:通过从当前节点向上,向下,向左或向右移动空间磁贴可以实现的配置

PS:如果重要的话,我正在使用二进制堆作为开放列表

谢谢

我遇到过Jump Point Search,对我来说似乎很甜蜜.但是,我不确定他们的修剪规则是如何实际工作的.更具体地说,在图1中,它表明了这一点

我们可以立即修剪所有灰色邻居,因为这些邻居可以从x的父节点最佳地到达,而无需通过节点x

然而,这似乎有些不一致.在第二个图像中,可以通过首先通过节点7并x完全跳过对称路径(即,6 -> x -> 5似乎是对称的)来到达节点5 6 -> 7 -> 5.这与如何在不经过x第一图像的情况下到达节点3的情况相同.因此,我不明白这两个图像是如何完全等效的,而不仅仅是彼此的旋转版本.

其次,我想了解这个算法如何推广到三维搜索量.

我有一个由节点组成的图,我需要一个快速算法,在两个节点之间生成一个随机路径.我从头开始设计了几种算法,但似乎无法做到这一点.

要么算法陷入循环,要么当我保留受访节点的记录时,它有时会卡在被访问节点之间.我遇到的另一个问题是我的算法性能太不稳定了.

所以我的问题是; 有没有人知道一个快速稳定的算法,用于无向图中两个可达节点之间的随机路径？

http://msl.cs.uiuc.edu/rrt/

任何人都可以解释rrt如何使用易于理解的简单措辞？我在网站和维基百科中阅读了这些描述.

我想看到的是对rrt的简短实现或对以下内容的彻底解释:

为什么rrt向外生长而不是仅仅围绕中心生长非常密集？它与天真的随机树有什么不同？

我们试图接下来的下一个新顶点如何被选中？

我知道有一个我可以下载的运动策略库,但在深入研究代码之前我宁愿理解这个想法,而不是相反.

假设我们在A点有一个物体.它想知道它是否可以移动到B点.它的速度有限,所以它只能一步一步地移动.它向正在移动的方向投射光线.Ray与一个对象碰撞,我们检测到它.如何安全地传递我们的光线(避免碰撞)？

顺便说一句,有没有办法让这种东西在对象投射的情况下工作,它会像简单的光线投射一样快/近吗？

有没有办法在某些vay路径中找到最优？

我有一个包含以下格式的30,000条记录的数据框:

ID | Name | Latitude | Longitude | Country |
1  | Hull | 53.744   | -0.3456   | GB      |

我想选择一条记录作为起始位置,将一条记录作为目标,并返回最短路径的路径(列表).

我使用Geopy来找到以km为单位的点之间的距离

import geopy.distance

coords_1 = (52.2296756, 21.0122287)
coords_2 = (52.406374, 16.9251681)

print (geopy.distance.vincenty(coords_1, coords_2).km)

我已经从以下教程中了解了如何在python中执行A*:https: //www.redblobgames.com/pathfinding/a-star/implementation.html

然而,他们创建了一个网格系统来浏览.

这是数据框中记录的直观表示:

这是我到目前为止的代码,但它找不到路径:

def calcH(start, end):
    coords_1 = (df['latitude'][start], df['longitude'][start])
    coords_2 = (df['latitude'][end], df['longitude'][end])
    distance = (geopy.distance.vincenty(coords_1, coords_2)).km
    return distance

^计算点之间的距离

def getneighbors(startlocation):
    neighborDF = pd.DataFrame(columns=['ID', 'Distance'])
    coords_1 = (df['latitude'][startlocation], df['longitude'][startlocation])
    for index, row in df.iterrows():
        coords_2 = (df['latitude'][index], df['longitude'][index]) …

我需要优化带有由贝塞尔线构造的填充形状的矢量图像。输入图像以及形状分离后的外观：

我想通过删除不必要的线条并依靠形状堆叠来保留外观来优化图像，但顶点要少得多。结果形状应如下所示：

这个问题可能可以分解为单独的步骤：

1. 检测堆叠线。这或多或少是简单的：计算沿线的点，沿它们找到顶点。如果顶点堆叠起来，它就变得微不足道了。

2. 寻找穿过其他形状的填充区域的贝塞尔路径。可能已经存在这样的算法，但我不知道。（我在这里真的需要帮助。）而且还不清楚要采用什么形状。也许我应该解决所有的可能性并进行比较。一旦我了解了它，它可能会变得更清楚。（欢迎提供提示/建议。）

3. 找到最佳的堆叠顺序以使顶点数量最少。对于像我这样不太热衷于算法的人来说，这听起来很痛苦，但这似乎是通过不同“路径”的顶点数量的某种最小化，所以可以做到。（如我错了请纠正我。）

4. 如果一个形状中有一个洞，这可能意味着里面的所有东西都会堆叠在它的上面，所以这是一个单独的简单情况，不需要额外的计算。

总的来说，第二点似乎是最有（唯一？）问题的，所以我需要在正确的方向上推动。

就示例图像而言，如何找到绿色形状的潜在遮挡部分穿过蓝色形状（以及可选的黄色形状）的贝塞尔路径，反之亦然，让蓝色形状穿过绿色形状？我不需要路径是最短的，我需要它的顶点最少。

本质上，我需要找到这些具有最少顶点数的路径。请随意忽略其余内容，将其视为不相关的上下文。

据我所知:

将当前节点添加到关闭列表.

查找当前节点的相邻节点,如果它们不是不可移动的节点而不是关闭的列表,则将该节点添加到打开列表中,父节点是当前节点,并计算F,G和H值.如果节点已经存在于打开列表中,请检查通过当前节点转到该节点是否会导致较低的G值 - 如果是,则使该节点的父节点成为当前节点.

在具有最高F值的打开列表中查找节点,并使当前节点成为该节点.

重复直到最终到达目的地,然后浏览目标节点的父节点,然后您将返回到起始节点.这将是最好的途径.

所以,这对我的大脑来说是有意义的,但是当我在图表上实际尝试时,我想我并没有正确地理解它.

(从下面的图片)从起始绿色瓷砖下来,F值为60的那个.这是在打开的列表上,并且具有比右下角74更低的F值.为什么选择74一个而不是60？

我正在建立一个在立方体表面上玩的蛇游戏.目前它使用Dijkstra的算法进行寻路.尽管使用set和priority队列数据结构进行了优化,但它仍然有点太慢.当蛇吃食物并开始寻找新食物时,你会注意到延迟.

我试图让它使用A*而不是我找不到一个好的启发式.在有4个运动方向的平面网格上,我会使用曼哈顿距离.我已经尝试过使用3D曼哈顿距离了abs(dx) + abs(dy) + abs(dz),这个距离并不合理:对于蛇来说,游戏世界实际上是6个网格(对应于立方体的面),具有不寻常的环绕特性.

在代码中,每个方块存储在grid[15][15]2D数组中.每个面都有6个这样的数组.因此每个方块都有一个(arrayX, arrayY, d)三元组来描述2D数组中的偏移并指定哪个数组.此外,每个方块都有一个(x, y, z)描述空间位置的三元组.

这是寻路发生的游戏代码区域:

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

这是A*的库代码:

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60

什么是这个游戏世界的合适,简洁的启发式？

所以我的问题是我有一个非负边长的有向图G,我希望找到两个节点u和v之间的最短路径,这样它们只能通过图中的一个标记节点.

如果我们没有涉及标记节点的条件,则可以使用Dijkstra算法轻松解决该问题.

procedure dijkstra(G, l, s)
Input: Graph G = (V, E), directed or undirected;
positive edge lengths {le : e ? E}; vertex s ? V
Output: For all vertices u reachable from s, dist(u) is set to the distance from s to u.

for all u ? V :
    dist(u) = ?
    prev(u) = nil
dist(s) = 0
H = makequeue(V ) (using dist-values as keys)
while H is not empty:
    u = deletemin(H)
    for all …