8

我需要一种算法，它会给我一条从开始节点到结束节点的路径，但路径必须有确切数量的节点，否则寻路应该失败。

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

我查看了 Dijkstra/A* 并搜索了寻路算法，但据我所知，所有这些算法都集中在最短路径上，这对我没有多大好处。我不在乎它是哪条路径，只要它遵循上述规则即可。

我是否遗漏了一些东西，这样的算法是否已经存在，或者是否有一种简单的方法可以修改 Dijkstra/A* 以给出这个结果？由于我不是以英语为母语的人，我可能使用了错误的术语，因此我欢迎针对此类算法提出关键字建议。


当我说它必须是准确的距离并且不能两次使用同一个瓷砖时，这是我的意思的一个例子。

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

XXXXXXX
潇潇
呜呜呜

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

XXXXXXX
潇潇
XXOOOXO

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

至于最大距离，这里是距离的范围。玩家将掷骰子并得到数字 1-6。如果玩家得到一个 6，他再次掷骰子，如果他得到另一个 6，一次又一次，直到他没有得到一个 6。距离是得到的数字加上玩家捡起的物品数量，理论上可以上升到 8，但通常是 0-3，maaaybe 4。

另一方面，我刚刚收到新订单，游戏规则已更改为允许在同一路径上两次踩同一位置，我相信这大大简化了过程，但我将把这个问题保留为我认为它有很好的答案可以帮助处于这种情况的人。

4

4 回答 4

3

由于您遇到每个步骤的成本为 1 的问题，因此称为深度限制搜索的深度优先搜索的简单变体应该能够找到您想要的路径类型。Python中的朴素版本：

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是这类算法的权威教科书。

于 2012-09-20T10:01:03.407 回答
3

由于它是 NP 完全的，正如 Haile 所指出的，如果您的问题足够小，这里有一个启发式方法：

  • 找到不包含Snor的半岛（即仅通过一个节点连接到其余部分的图的部分）E并删除它们。
  • 找到P从S到的最短路径E。如果n小于len(P)，则无解。
  • S现在，从到进行深度优先搜索E，使用以下启发式方法选择首先挖掘的节点。设为A深度优先搜索中的当前图块。在欧几里得几何中，将 的位置投影A在线上(SE)并称之为点A'。尽量保持比例len(current path) / n接近len([SA']) / len([SE])。或者更好的是，以某种方式“投射”在获得并保持比率接近A的路径上。PA''len(current path) / nlen([SA''] along P) / len(P)

我们对您将要处理的具体情况知之甚少，肯定有更多启发式方法可以添加以丢弃深度优先搜索树的部分内容。

于 2012-09-20T09:56:04.347 回答
2

如果有一个快速的算法，你可以插入，number of nodes = n算法会很快告诉你是否有哈密顿路径。由于该问题是NP完全的，因此您的问题也是如此。

于 2012-09-20T09:41:46.293 回答
0

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

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

另外，请注意，反复掷骰子直到得到 6 以外的数字，就相当于在 1 和 5 之间抽取一个随机数。在电脑游戏中微不足道，并且有物理的这种骰子（谷歌搜索“5 面骰子”图像）。使用十面骰子也很常见。

于 2012-09-20T14:51:32.763 回答