带条件的最短路径图搜索

Question

问题是一个由一个附属建筑连接起来的迷宫。这个迷宫的布局完全为程序员所知。然而，每个附件都充满了四种有毒气体中的一种。可以提供防毒面具，只要它配备了一个针对每种气体的过滤器，就可以对每种类型的气体提供免疫力。四个过滤器（每种类型一个）分别位于迷宫中给定的建筑物中。在

a）第一个目标是编写一个方法maze_solver_single_explorer(maze, start, end)，它返回从start到达end所需的最小时间步数。在每一个时间步骤中，一个人可以拿起位于同一建筑物内的任何数量的过滤器，然后最多穿过一个附件（前提是拥有适当的过滤器）。可根据需要随时从面罩上取下或取下。在

b）第二个目标是编写一个方法maze_solver_multiple_explorers(maze, start, end, max_timesteps)，该方法返回在给定时间限制（小于20的小常数）内从{}到达{}所需的最小数量的探索者。探索者从源建筑开始，只有一个探索者需要到达目标建筑。除上述规则外，还可以放下过滤器，让其他玩家从同一栋建筑中取回。删除一个或多个过滤器可以在一个时间步骤的开始处完成，这样一个资源管理器可以删除一个过滤器并在同一个时间步骤中浏览附件。但是，另一个资源管理器可能无法提取在同一时间步中丢弃的筛选器。示例：资源管理器0向左移动以选择筛选器0，同时资源管理器1向右移动以选择筛选器1。然后两者都返回到源建筑，资源管理器0将选择资源管理器1丢弃的筛选器1，继续前往目标建筑。在

如何用Python建模/编码这个问题？在

编辑：我写了一些简单的测试用例：

def test_explore_single_basic(self):
        buildings = ['A', 'B', 'C', 'D']
        annexes = [('A', 'B', 0), ('B', 'D', 2), ('B', 'C', 0), ('C', 'D', 3)]
        filters = [('A', 0), ('C', 2), ('D', 3), ('D', 1)]
        start = 'A'
        goal = 'D'
        labyrinth = Maze(buildings, annexes, filters, start, goal)
        # There are two edges leading to the goal building, D. However the 
        # filter of type 3 cannot be obtained without reaching the goal 
        # building itself. So the explorer must first go to C to pick up the
        # filter of type 2. Thus the fastest sequence of actions is:
        # pick up filter 0, go from A to B, go from B to C, pick up filter 2, 
        # go from C to B, go from B to D.
        self.assertEqual(maze_solver_single_explorer(maze), 4)

def test_explore_single_unreachable(self):
        # Same as the previous test, except we require filter type 3 to go
        # from B to D.
        buildings = ['A', 'B', 'C', 'D']
        annexes = [('A', 'B', 0), ('B', 'D', 3), ('B', 'C', 0), ('C', 'D', 3)]
        filters = [('A', 0), ('C', 2), ('D', 3), ('D', 1)]
        start = 'A'
        goal = 'D'
        maze = Maze(buildings, annexes, filters, start, goal)
        self.assertEqual(maze_solver_single_explorer(maze), None)

def test_explore_multiple_basic(self):
        #   L  --  S  --  R
        #          |
        #          D
        #          |
        #          G
        buildings = ['S', 'L', 'R', 'D', 'G']
        annexes = [('S', 'L', 0), ('S', 'R', 1), ('S', 'D', 2), ('D', 'G', 3)]
        filters = [('S', 0), ('S', 1), ('R', 2), ('L', 3)]
        start = 'S'
        goal = 'G'
        maze = Maze(buildings, annexes, filters, start, goal)
        # A single explorer needs 6 timesteps to get to the goal.
        self.assertEqual(maze_solver_multiple_explorers(maze, 20), 1)
        self.assertEqual(maze_solver_multiple_explorers(maze, 6), 1)
        # Two explorers can make it in 5 timesteps. One explorer goes right, 
        # picks up filter 2, goes back and drops it at S.
        # Meanwhile, the other explorer goes left, picks up filter 3, goes 
        # back to S, picks up filter 2, and finally proceeds to D and G.
        self.assertEqual(maze_solver_multiple_explorers(maze, 5), 2)
        # No matter how many explorers you have, it's not possible to reach
        # the goal in 4 or fewer timesteps.
        self.assertEqual(maze_solver_multiple_explorers(maze, 4), None)

def test_explore_multiple_unreachable(self):
        # Same as the previous test, except filter type 2 is unreachable.
        buildings = ['S', 'L', 'R', 'D', 'G']
        annexes = [('S', 'L', 0), ('S', 'R', 1), ('S', 'D', 2), ('D', 'G', 3)]
        filters = [('S', 0), ('S', 1), ('D', 2), ('L', 3)]
        start = 'S'
        goal = 'G'
        maze = Maze(buildings, annexes, filters, start, goal)
        self.assertEqual(maze_solver_multiple_explorers(maze, 18), None)

Answer 1

问题1

Dijkstra算法是一种很好的方法。但是，您需要使您的状态表示更加完整。除了对资源管理器的位置进行建模外，还需要对资源管理器携带的过滤器进行建模。在

• 例如，从以下位置开始： {x: 0, y: 0, filters: []}

• 你可能采取的行动是： ['left', 'right', 'up', 'down']，（假设所有路径都存在，没有一条被气体阻塞）。

• 假设我们选择up，那里有一个过滤器。你的新州会是 {x: 0, y: 1, filters: ['S']}

• 现在我们知道我们可以通过气体S的路径，但不能通过其他路径。

问题2

第二个问题要复杂得多。为了达到最佳效果，您需要使用某种类型的多代理寻径，但这很难解决。如果你有一个好的启发式搜索，这可能是可行的贪婪的最佳优先搜索。在