algorithm - 允许A-star算法绕过x个障碍物

Question

现在我有这个迷宫:

标有S和E的节点代表这个迷宫的起点和终点。

橙色节点表示目前无法绕过的障碍。

我的目标是让A*算法绕过x个障碍，以最快的速度到达终点。

我的 A* 算法目前是这样导航的:

.

但如果我允许绕过 1 个障碍，我希望它像这样导航:

如果我允许绕过 2 个障碍，就像这样:

如何修改 A* 算法来实现此目的？是否有替代算法可以帮助我解决这个问题？

Answer 1

您可以复制图中的节点，并为每个绕过次数生成实例。也就是说，您将创建多个图形层并从第 0 层开始(您已经绕过了 0 个障碍)。每当你到达一个障碍节点时，你就会切换到下一层(即，下一层的相邻障碍节点有边，同一层的相邻非障碍节点有边)。根据需要绕过障碍创建尽可能多的图层。如果您到达目标单元格的任何实例(在任何层上)，您就完成了。