指定距离/节点数的路径规划算法

Question

我需要一个算法，能够给我一条从起始节点到结束节点的路径，但是这条路径必须有确切数量的节点，否则路径规划应该失败。

具体来说，我有一个方块网格。移动只能在紧邻的上、下、左或右方块中进行（即无对角线移动）。有许多规则可以确定哪些方块可以使用在路径中，哪些不行，但大多可以简化为一个简单的布尔值来告诉我们这个方块是否可以使用（这可以在开始算法之前计算出来）。让我头疼的问题是，我有一个规定好的路径距离，也就是说，从一个方块到相邻方块的每次移动距离都是一单位长度，整个路径应该有一个指定的距离，不多不少。此外，一旦踏上了一个方块（但所有方块都在算法开始时可用），就不能再踏上它了，有点像玩老的贪吃蛇游戏时要小心不要撞到自己。

我看过Dijkstra/A*算法，并搜索了寻路算法的相关信息，但据我所知，所有算法都集中于最短路径，这对我没有什么帮助。我并不关心它是哪条路径，只要它遵循上述规则即可。

我错过了什么，是否已经存在这样的算法，或者是否有一种简单的方法修改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或4。

另外，我刚刚收到新的规则，游戏规则改变为允许在同一路径上两次踏上相同的位置，我认为这极大地简化了流程，但我会保留这个问题，因为我认为它有很好的答案，可以帮助处于这种情况的人。

- Bikonja

---

请注意，通过将问题归约为哈密顿路径问题，该问题是NP完全的。此外，请阅读amit在此处的答案：http://stackoverflow.com/questions/10881014/how-to-find-path-of-exact-length-in-graph。 - Haile

@Haile：这个问题是NP完全的，但你需要更加小心一些，因为问题中的图形有点受限，你需要对每个合法缩减的汉密尔顿路径问题进行缩减。话虽如此，问题中的图形是网格图，寻找哈密顿路径在其中是NP完全问题。 - Nabb

@Nabb 你说得完全正确。 - Haile

Answer 1

由于您的问题每一步的代价都是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 是这种算法的权威教材。

- Fred Foo

---

你忘记检查路径是否真正到达目标点了：if path[-1]==goal: return path if len(path)==depth else None \ elif len(path) < depth: ... - tobias_k

Answer 2

由于像Haile所指出的那样，它是NP完全问题，因此如果您的问题足够小，则可以使用以下启发式方法：

• 查找半岛（即与其余部分仅通过一个节点连接的图的部分），这些部分不包含S或E并将其删除。
• 从S到E找到最短路径P。如果n小于len(P)，则没有解决方案。
• 现在，从S到E进行深度优先搜索，使用以下启发式方法选择要首先挖掘哪个节点。让A成为深度优先搜索中的当前节点。在欧几里得几何中，将A的位置投影到线(SE)上，并将此点称为A'。尝试使比率len(current path) / n接近len([SA']) / len([SE])。或者更好的是，以某种方式在路径P上“投影”A，以获取A''并将比率len(current path) / n保持接近len([SA''] along P) / len(P)。

我们不知道您将处理的确切情况，肯定有更多的启发式方法可以添加以丢弃深度优先搜索树的部分。

- jrouquie

---

感谢大家，你们的回答给了我一个解决问题的大致思路。 jrouquie，你的解决方案最吸引我，所以我会尝试实现它（现在不在家，所以不能立即实现），看看它是否可行。 我不确定什么距离算足够小，但我会编辑问题并说明距离是多少。 - Bikonja

不要忘记在深度 n 处停止搜索，就像 larsmans 所写的那样。 - jrouquie

Answer 3

如果存在一个快速算法，你可以输入“节点数量=n”，然后该算法将迅速告诉你是否存在哈密顿路径。由于该问题是NP完全问题，所以你的问题也是NP完全问题。

- BlueRaja - Danny Pflughoeft

Answer 4

现在问题已经更新为距离的常规值...

因此，在每个时间步骤中，您最多有4个选择，并且最多有5+4 = 9个步骤。这使得潜在路径少于4⁹ = 262 144条。首先尝试暴力破解，看看它能走多远。

另外，请注意，重复掷骰子直到获得不是6的数字等同于在1和5之间随机抽取一个数字。在计算机游戏中很简单，而且有物理骰子（搜索“5面骰子”图像）。使用十面骰子也很常见。

- jrouquie

---

首先，感谢您的回答。 问题在于移动必须一次性完成，而不是获取6，移动6，再投掷。虽然现在这个问题已经无关紧要了，因为根据更新后的规则，我不再需要满足不重复踏上同一位置的要求。 此外，游戏使用六面骰子，因为有时只有六种可能的结果，尽管通过获取6可以延长移动距离。但是不想扩大无关紧要的话题，该游戏实际上存在于物理棋盘游戏中，我只是制作了一个电脑版以配合它，所以我不能真正改变它的运行方式。 - Bikonja