标签: path-finding

我发现很多人都提到了吃豆子鬼的人工智能,但他们都没有提到在吃掉鬼人吃鬼之后眼睛如何回到中央鬼洞.

在我的实现中,我实现了一个简单但可怕的解决方案.我只是在每个角落都硬编码应该采取哪个方向.

有没有更好/或最好的解决方案？也许是一个适用于不同级别设计的通用产品？

在塔防游戏中,你有一个NxM网格,有一个开始,一个完成和一些墙.

敌人从头到尾穿过最短路径而不穿过任何墙壁(它们通常不会被限制在网格上,但为了简单起见,我们可以说它们是.在任何一种情况下,它们都不能穿过对角线"洞")

问题(对于这个问题,至少)是将多达 K个追加墙壁最大化的敌人必须采取的路径.例如,对于K = 14

我的直觉告诉我这个问题是NP难的,如果(正如我希望的那样)我们将其概括为包括在移动到终点之前必须访问的路点,也可能没有路点.

但是,对于接近最优的解决方案,是否有任何体面的启发式方法？

[编辑]我在这里发布了一个相关的问题.

我读到这个:http: //en.wikipedia.org/wiki/A*_search_algorithm

它说A*比使用dijkstra更快,并使用最佳优先搜索来加快速度.

如果我需要算法在毫秒内运行,A*何时成为最突出的选择.

据我所知,它不一定能带来最好的结果.

如果我需要快速结果,预先计算路径是否更好？它可能需要几兆字节的空间来存储它们.

我需要一些帮助找到一个良好的启发式解决以下问题:

您将得到一个R-by- C网格和六面的骰子.设start和 end是在这个网格两种截然不同的细胞.找到一条路径start,end使得当模具沿路径转动时,模具面朝上的总和是最小的.

模具的起始方向如下("2"朝南):

我模拟这个问题的方法是将模具的面值视为图形中边缘的成本.图形的顶点具有形式(row, col, die)(即,网格中的位置和模具的当前状态/方向).顶点不是简单的原因(row, col)是因为你可以使用骰子的多个配置/方向结束相同的单元格.

我用A*来找到问题的解决方案; 给出的答案是正确的,但效率不高.我已经确定问题是我正在使用的启发式问题.目前我正在使用曼哈顿距离,这显然是可以接受的.如果我将启发式乘以常量,则不再允许:它运行得更快,但并不总能找到正确的答案.

我需要一些帮助才能找到比曼哈顿距离更好的启发式方法.

所以,这是我正在尝试的功能的一部分.

我不希望代码太复杂.

我有一个单词列表,例如

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

单词链序列的概念是下一个单词以最后一个单词结尾的字母开头.

(编辑:每个单词不能多次使用.除此之外没有其他限制.)

我希望输出给出最长的单词链序列,在这种情况下是:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

我不确定该怎么做,我尝试过不同的尝试.其中一个......

如果我们从列表中的特定单词开始,此代码正确地找到单词链,例如单词[0](所以'giraffe'):

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []

word_chain.append(words[0])

for word in words:
    for char in word[0]:

       if char == word_chain[-1][-1]:
            word_chain.append(word)

print(word_chain)

输出:

['giraffe', 'elephant', 'tiger', 'racoon']

但是,我想找到最长的单词链(如上所述).

我的方法:所以,我尝试使用我编写和循环的上述工作代码,使用列表中的每个单词作为起点,找到每个单词[0],单词[1],单词[2]的单词链然后我尝试通过使用if语句找到最长的单词链,并将长度与前一个最长的链进行比较,但我无法正确完成它,我真的不知道这是怎么回事.

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []
max_length = 0
for starting_word_index in range(len(words) - …

有链接到d*一些文件在这里,但他们有点太数学对我来说.有没有关于D*/D*Lite的信息更适合初学者？

是否有将当前路径/文件复制到剪贴板的快捷方式？

对于太空游戏来说,这是一个非常困难的问题,即如何操纵可以在3D中平移和旋转的宇宙飞船.

宇宙飞船有n各种位置和方向的喷气式飞机.

i相对于宇宙飞船的CM ,-th jet的变换是常数= Ti.

• 变换是位置和方向的元组(四元数或矩阵3x3或更不优选的欧拉角).
• 转换也可以用单个矩阵4x4表示.

换句话说,所有喷射器都粘在船上并且不能旋转.

射流只能沿其轴线方向(绿色)向太空船施加力.
由于胶水,轴与飞船一起旋转.

所有喷射都可以Fi在一定幅度(标量)上施加力(矢量fi):
i- 喷射可以仅在范围内施加力(Fi= axisx fi)min_i<= fi <=max_i.
两个min_i和max_i与已知值恒定.

需要明确的是,单位min_i,fi,max_i是牛顿.
防爆.如果范围不包括0,则表示无法关闭喷嘴.

宇宙飞船的质量= m和惯性张量= I.
宇宙飞船的当前变换= Tran0,velocity = V0,angularVelocity = W0.

宇宙飞船物理学家遵循众所周知的物理规则: -
Torque=r x F
F=ma
angularAcceleration = I^-1 x Torque
linearAcceleration = m^-1 x F

I每个方向都有所不同,但为了简单起见,每个方向都有相同的值(球形).因此, …

我有一个50 x 50的2D网格.网格单元可以具有以下三种状态之一:

1: "inside"
2: "empty"
3: "wall"

我的初始配置是一个网格,其中一些单元格(可能是其中的10%,大部分是连续的)标记为"内部".随机也有一些"墙"细胞.其他单元格是"空的".

我试图找到我可以围绕"内部"单元构建的最短栅栏,以便所有"内部"单元被围起来(围栏是通过将"空"单元改为"墙"单元构建的).如果我们对解决方案进行评分,那么最佳解决方案将最小化需要更改为"墙"单元的"空"单元的数量.

更严格地说,在最终配置中,存在约束,即对于每个"内部"单元,没有到达不通过"墙"单元的网格边缘的路径.就我而言,允许对角线移动.

我猜我可以做一些巧妙的涉及距离变换,或计算网格的拓扑骨架,但这对我来说并不是很明显.如果这是一个经典的优化问题,我不知道谷歌的条款.

是否有O(n ^ 2)算法来寻找最短的栅栏？

编辑:它不像找到"内部"单元格的凸包那么容易,因为预先存在的"墙"单元是自由的.想象一个"C"形的预先存在的墙块,在C的内部有所有"内部"单元格.大多数时候,用"墙"单元格完成C将比在所有墙上绘制凸包更便宜"内部"细胞.这就是使这个问题变得困难的原因.

我正在寻找一种算法用于我正在制作的赛车游戏.地图/关卡/轨道是随机生成的,所以我需要找到两个位置,即开始和目标,它们利用了大部分地图.

• 该算法是在二维空间内工作
• 从每个点,只能遍历四个方向的下一个点; 上下左右
• 点数既可以是阻止的也可以是非阻塞的,只能遍历非阻塞点

关于距离的计算,它不应该是缺乏更好词的"鸟道".如果它们之间存在墙(或其他阻挡区域),则A和B之间的路径应该更长.

我不确定从哪里开始,非常欢迎评论,并且建议的解决方案在伪代码中是首选.

编辑:对.在查看了gs的代码后,我又给了它一个镜头.我这次用C++写的,而不是python.但是,即使在阅读了Dijkstras算法,洪水填充和Hosam Alys解决方案后,我也没有发现任何重要的区别.我的代码仍然有效,但没有你想要运行的那么快.完整的消息来源是牧场.唯一有趣的线(我猜)是第78-118行的Dijkstra变体.

但速度不是这里的主要问题.如果有人能够指出算法中的差异,我真的很感激帮助.

• 在Hosam Alys算法中,他是从边界而不是每个节点扫描的唯一区别吗？
• 在Dijkstras你跟踪和覆盖走的距离,但不是在洪水填充,但这就是它？