Как легко узнать, есть ли у лабиринта путь от начала до цели?

Question

Я реализовал лабиринт, используя массив 0,1. Вход и цель фиксируется в лабиринте. Вход всегда будет 0,0 точки лабиринта. Целью всегда будет м-1, н-1, точка лабиринта. Сейчас я использую алгоритм поиска в ширину, но скорость не достаточно хорошая. Особенно для большого лабиринта (100 * 100 или около того). Может ли кто-нибудь помочь мне с этим алгоритмом?

Вот мое решение:

queue = []
position = start_node
mark_tried(position)
queue << position
while(!queue.empty?)
  p = queue.shift  #pop the first element
  return true if maze.goal?(p)
  left = p.left
  visit(queue,left) if can_visit?(maze,left)
  right = p.right
  visit(queue,right) if can_visit?(maze,right)
  up = p.up
  visit(queue,up) if can_visit?(maze,up)
  down = p.down
  visit(queue,down) if can_visit?(maze,down)
end
return false

можно_свить? Метод проверки, находится ли узел внутри лабиринта, посещен ли узел, заблокирован ли узел.

Answer 1

худший ответ возможен.

1) идите вперед, пока не сможете двигаться

2) повернуть налево

3) промыть и повторить.

если ты это сделаешь, конец есть.

Лучшее решение.

Пройдите через ваш лабиринт, сохраняя 2 списка для открытых и закрытых узлов. Используйте известный алгоритм A-Star выбрать оценку следующего узла и сбросить узлы, которые являются тупиком. Если у вас закончились узлы в вашем открытом списке, выхода нет.

Answer 2

Вот простой алгоритм, который должен быть намного быстрее:

• От начала / цели перейти к первому перекрестку. Вы можете игнорировать что-либо между этим соединением и началом / целью.

• Найдите все места в лабиринте, которые являются тупиками (у них три стены). Вернитесь к следующему перекрестку и уберите этот путь из дерева поиска.

После того, как вы удалите все тупики таким образом, должен остаться один путь (или несколько, если есть несколько способов достичь цели).

Answer 3

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

# maze is a m x n array
def canBeTraversed(maze):
  m = len(maze)
  n = len(maze[0])

  colored = [ [ False for i in range(0,n) ] for j in range(0,m) ]

  open = [(0,0),]

  while len(open) != 0:
    (x,y) = open.pop()
    if x == m-1 and y == n-1:
      return True
    elif x < m and y < n and maze[x][y] != 0 not colored[x][y]:
      colored[x][y] = True
      open.extend([(x-1,y), (x,y-1), (x+1,y), (x,y+1)])

  return False

Да, это глупо, да, это первый хлеб и все такое.

Вот реализация A *

def dist(x,y):
  return (abs(x[0]-y[0]) + abs(x[1]-y[1]))^2

def heuristic(x,y):
  return (x[0]-y[0])^2 + (x[1]-y[1])^2

def find(open,f):
  result = None
  min = None
  for x in open:
    tmp = f[x[0]][x[1]]
    if min == None or tmp < min:
      min = tmp
      result = x
  return result

def neighbors(x,m,n):
  def add(result,y,m,n):
    if x < m and y < n: result.append(y)
  result = []
  add(result, (x[0]-1,x[1]), m, n)
  add(result, (x[0],x[1]-1), m, n)
  add(result, (x[0]+1,x[1]), m, n)
  add(result, (x[0],x[1]+1), m, n)
  return result

def canBeTraversedAStar(maze):
  m = len(maze)
  n = len(maze[0])

  goal = (m-1,n-1)

  closed = set([])
  open = set([(0,0),])

  g = [ [ 0 for y in range(0,n) ] for x in range(0,m) ]
  h = [ [ heuristic((x,y),goal) for y in range(0,n) ] for x in range(0,m) ]
  f = [ [ h[x][y] for y in range(0,n) ] for x in range(0,m) ]

  while len(open) != 0:
    x = find(open,f)
    if x == (m-1,n-1):
      return True
    open.remove(x)
    closed.add(x)

    for y in neighbors(x,m,n):
      if y in closed: continue

      if y not in open:
        open.add(y)

        g[y[0]][y[1]] = g[x[0]][x[1]] + dist(x,y)
        h[y[0]][y[1]] = heuristic(y,goal)
        f[y[0]][y[1]] = g[y[0]][y[1]] + h[y[0]][y[1]]

  return True

Вот мой (простой) код теста:

def tryIt(func,size, runs):
  maze = [ [ 1 for i in range(0,size) ] for j in range(0,size) ]
  begin = datetime.datetime.now()
  for i in range(0,runs): func(maze)
  end = datetime.datetime.now()

  print size, 'x', size, ':', (end - begin) / runs, 'average on', runs, 'runs'

tryIt(canBeTraversed,100,100)
tryIt(canBeTraversed,1000,100)

tryIt(canBeTraversedAStar,100,100)
tryIt(canBeTraversedAStar,1000,100)

Какие выходы:

# For canBeTraversed
100 x 100 : 0:00:00.002650 average on 100 runs
1000 x 1000 : 0:00:00.198440 average on 100 runs

# For canBeTraversedAStar
100 x 100 : 0:00:00.016100 average on 100 runs
1000 x 1000 : 0:00:01.679220 average on 100 runs

Здесь очевидно: чтобы A * работал бесперебойно, требуется много оптимизаций, за которыми я не потрудился ...

Я бы сказал:

1. Не оптимизировать
2. (только эксперт) Пока не оптимизировать

Сколько времени вы говорите, когда говорите слишком много? Действительно, сетка 100x100 так легко разбирается в грубой силе, что это шутка: /

Answer 4

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

• создайте целое число [] [] с одним значением на лабиринт "комната"
• создать очередь, добавить [начальную точку, количество = 1, дельта = 1] и [цель, количество = -1, дельта = -1]
• начать раскрашивать маршрут по:
  • выскакивая объект из головы очереди, ставьте счет в точку лабиринта.
  • проверьте все доступные комнаты на предмет подсчета со знаком, противоположным знаку дельты комнат, если вы найдете одну, лабиринт решен: пройдите в обе стороны и соедините маршруты с самыми большими шагами вверх и вниз по количеству комнат.
  • в противном случае добавьте все доступные номера, у которых нет отсчета, в конец очереди, с добавлением дельты к количеству комнат.
  • если очередь пуста, путь через лабиринт невозможен.

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

Вам не нужно возвращаться, поэтому его O (количество комнат в лабиринте)

Answer 5

Я бы решил это с помощью AStar . Если вы хотите еще большей скорости, вы можете оптимизировать, чтобы генерировать только узлы из соединений, а не из каждой плитки / квадрата / шага.