具有指定距离/节点数的寻路算法-Java 学习之路

我需要一个算法，它会给我一条从起始节点到结束节点的路径，但路径必须有一个确切数量的节点，否则路径查找应该失败 .

为了扩展，我有一个瓷砖网格 . 移动只能是紧邻的上，下，左或右平铺（意思是没有对角线移动） . 瓦片在路径中可以使用和不可以使用的规则有很多，但大多数情况下可以归结为简单的布尔来判断瓦片是否可以使用（这可以在开始算法之前计算出来）但是，给我带来麻烦的是，我有一条路径必须具有的距离，这意味着，从一个瓷砖到相邻瓷砖的每一次移动都是一个距离，整个路径应该有一个指定的距离，不多也不少 . 此外，一旦瓷砖被踩到（但算法开始时所有瓷砖都可用），它不能再次踩到，有点像玩老蛇游戏你我要注意不要吃自己 .

我看过Dijkstra / A *并且我用google搜索算法进行寻路，但据我所知，所有这些算法都集中在最短的路径上，这对我没什么好处 . 只要遵循上述规则，我不关心它是哪条路径 .

我错过了什么，这样的算法和算法是否已经存在，或者是否有一种简单的方法来修改Dijkstra / A *来给出这个结果？由于我不是母语为英语的人，我可能使用了错误的术语，所以我欢迎这种算法的关键字建议 .

这里是我的意思，当我说它必须是和确切的距离，并不能使用相同的瓷砖两次 .

假设距离必须为7.现在让我们用O标记可以在路径中使用的图块，不能使用的图块和X，S的起点和E的目标 .

X X X X X X X
X O O E S O O
X O O O O O O

如果没有距离限制，可以向左走，问题就解决了 . 如果有距离限制，但没有“不能踩到相同的瓷砖”限制，可以下降一次，然后向左，然后向右，然后向左，然后向右，然后向左，然后向上并到达目标 . 由于存在这两种限制，因此需要向右，向下，向左，向左，向上，向右然后才能到达目标 . 但是，如果情况是这样的话，就没有有效的路径 .

X X X X X X X
X O O E S O O
X X O O O X O

如果它是相关的，我正在用C＃开发这个棋盘游戏 .

至于最大距离，这是距离所在的范围 . 玩家将掷骰子并获得数字1-6 . 如果玩家获得6，他会再次投掷骰子，如果他再次获得6，则一次又一次直到他没有得到6.距离是结果数加上玩家拾取的物品数量，理论上可以最多8，但通常是0-3，maaaybe 4 .

另一方面，我刚收到新订单，游戏规则改为允许在相同的路径上两次踩到同一个位置，我相信这个过程很简单，但是我会把这个问题保留为我认为它有很好的答案，可以帮助那些情况下的人 .

4 回答

2

现在问题已经用通常的距离值更新了......

因此，在每个时间步，您最多有4个选项，最多有5 4 = 9个步骤 . 这使得少于49 = 262 144个潜在路径 . 首先尝试蛮力，看看能走多远 .

此外，请注意，反复掷骰子直到你得到6以外的东西相当于在1到5之间绘制一个随机数 . 在一个comupter游戏中琐碎，并且有物理这样的骰子（谷歌为“5面骰子”图像） . 使用十面骰子也很常见 .

回复于 2024-05-04T03:52:17+08:00
3
正如Haile所指出的，它是NP完全的，如果您的问题足够小，这里是一个启发式：
- 查找不包含 S 和 E 的半岛（即仅由一个节点连接到其余部分的图形部分）并删除它们 .
- 从 S 到 E 找到最短路径 P . 如果 n 小于 len(P) ，则没有解决方案 .
- 现在，执行从 S 到 E 的深度优先搜索，使用以下启发式选择首先挖掘哪个节点 . 设 A 为深度优先搜索中的当前切片 . 在欧几里德几何中，将 A 的位置投影到 (SE) 行并调用此点 A' . 尽量保持比率 len(current path) / n 接近 len([SA']) / len([SE]) . 或者更好，不知何故"project" A 在路径 P 上得到 A'' 并保持比率 len(current path) / n 接近 len([SA''] along P) / len(P) .
我们对您将要处理的确切案例知之甚少，当然还有更多的启发式方法可以丢弃深度优先搜索树的部分内容 .
回复于 2024-05-04T03:52:17+08:00

由于您遇到的问题是每个步骤的成本为1，因此深度优先搜索的简单变体depth-limited search应该能够找到所需的路径类型 . 天真的版本蟒蛇：

def dls(path, goal, depth):
    last = path[-1]
    if len(path) == depth:
        if last == goal:
            return path
    else:
        for n in neighbors(last):
            if allowed(n) and n not in path:
                path.append(n)
                solution = dls(path, depth)
                if solution:
                    return solution
                path.pop()

# call as:
dls([start], goal, depth)

正如其他人所指出的那样，问题是NP完全的，所以不要指望奇迹会有更长的路径长度 .

Russell & Norvig是这种算法的权威教科书 .

回复于 2024-05-04T03:52:17+08:00

3

如果有一个快速算法，你可以插入 number of nodes = n ，算法会很快告诉你是否有一个Hamiltonian Path . 由于这个问题是NP完全的，你的问题也是如此 .

回复于 2024-05-04T03:52:17+08:00

具有指定距离/节点数的寻路算法

4 回答

相关问题