DFS в любом порядке для уборки каждой комнаты по сетке? - PullRequest
Новая
       40

DFS в любом порядке для уборки каждой комнаты по сетке?

0 голосов
/ 05 мая 2020

Рассмотрим задачу, в которой «робот-уборщик» помещен в комнату, смоделированную в виде сетки. Каждая ячейка в сетке может быть пустой или заблокированной, и все доступные ячейки соединены, то есть все пустые ячейки будут доступны роботу независимо от его начальной позиции.

Нам говорят, что робот-уборщик может выполнить только одно из четырех действий:

  • robot.move() для движения вперед (возвращает true, если следующая ячейка открыта, а робот перемещает в ячейку, возвращает false, если следующая ячейка является препятствием, и робот остается в текущей ячейке.)
  • robot.turn_left() для поворота влево (90 градусов, без движения)
  • robot.turn_right() для поворота вправо (90 градусов, без движения)
  • robot.clean(), чтобы очистить текущую ячейку в сетке

Нам предлагается разработать алгоритм для робота, чтобы очистить всю room .

Каждое решение, которое я нашел для этой проблемы, рассматривает исследование соседних ячеек (до ячейки, которую в настоящее время посещают) либо в по часовой стрелке , либо в против по часовой стрелке направление (т.е. так принцип следования за стеной светодиода) относительно текущего направления робота в ячейке (например, пример ниже в Python). Почему?

Например, почему бы не использовать обычную DFS (и, таким образом, выбор соседних ячеек в любом порядке (например, пробовать все 4 направления, например, вверх / вниз / вправо / влево независимо от текущая позиция ) здесь не работает? 

def clean_room(robot):

    def go_back():
        robot.turn_right()
        robot.turn_right()
        robot.move()
        robot.turn_right()
        robot.turn_right()

    def backtrack(cell = (0, 0), d = 0):
        visited.add(cell)
        robot.clean()

        # Always going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
        for i in range(4):
            new_d = (d + i) % 4
            new_cell = (cell[0] + directions[new_d][0], \
                        cell[1] + directions[new_d][1])

            if not new_cell in visited and robot.move():
                backtrack(new_cell, new_d)
                go_back()
            # turn the robot following chosen direction : clockwise
            robot.turn_right()

    # Going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = set()
    backtrack()

1 Ответ

1 голос
/ 06 мая 2020

DFS будет работать независимо от того, в каком порядке вы пробуете соседние ячейки. Однако он не особенно эффективен, поскольку может тратить много времени на поиск ячеек, которые уже исследованы. В DFS после каждой «дочерней» ячейки вы должны повторно вводить родительскую ячейку, которая уже была посещена.

Использование другой стратегии может быть в два раза быстрее, требуя вдвое меньше ходов. Однако эти другие стратегии, как правило, более сложны. кратчайший путь, чтобы добраться туда.

...