Как найти кратчайший путь в сетке X * Y

Question

У меня есть сетка N * M в Python.

, где

"X" представляет границу,

"1" представляет текущую позицию,

«2» обозначает конечное число sh, а

«3» обозначает запрещенное местоположение.

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

Пример 3x3 за исключением границ:

[X,X,X,X,X]
[X,2,1,0,X]
[X,0,3,0,X]
[X,0,0,0,X]
[X,X,X,X,X]

Другой пример:

[X,X,X,X,X]
[X,2,0,0,X]
[X,3,3,1,X]
[X,X,X,X,X]

Или другой:

[X,X,X,X,X,X,X]
[X,0,2,0,0,0,X]
[X,0,3,0,3,0,X]
[X,0,0,0,0,0,X]
[X,0,3,0,3,0,X]
[X,0,3,1,3,0,X]
[X,X,X,X,X,X,X]

Есть ли у вас какие-либо предложения по конкретному сценарию, который найдет самый быстрый путь?

А если его нет, напечатайте («Нет решения»)?

Большое спасибо!

Чтобы помочь вам понять эти ситуации:

изображения примеров 1 и 2

Answer 1

Вы можете использовать этот код, который основан на теории Grap:

grid = [
['X','X','X','X','X','X','X'],
['X',2,0,0,0,0,'X'],
['X',0,3,0,3,0,'X'],
['X',0,0,0,0,0,'X'],
['X',0,3,0,3,0,'X'],
['X',0,3,1,3,0,'X'],
['X','X','X','X','X','X','X']
]


INF=1000000

def is_valid(grid:list):
    ends = 0
    starts = 0
    for line in grid:
        for el in line:
            if el==2:
                ends+=1
            if el==1:
                starts+=1
    return False if ends!=1 or starts!=1 else True

def redef_grid(grid:list):
    ''' Deleting from grid all 'X' '''
    g=grid.copy()
    if 'X' in g[0]: del g[0]
    if 'X' in g[-1]: del g[-1]
    for line in g:
        while 'X' in line:
            line.remove('X')
    return g

def uni_index(grid:list, pos:tuple):
    return len(grid[0])*pos[0]+pos[1]

def real_index(grid:list, index:int):
    row =index//len(grid[0])
    col=index-row*len(grid[0])
    return (row, col)

def get_neibs(grid:list, index:int):
    def get_vertical(grid:list, index:int):
        return [index+k for k in [len(grid[0]), -len(grid[0])] if index+k>=0 and index+k<uni_index(grid, (len(grid)-1, len(grid[0])-1))]
    def get_horizontal(grid:list, index:int):
        return [index+k for k in [1, -1] if index+k>=(index//len(grid[0]))*(len(grid[0])) and index+k<=uni_index(grid, (index//len(grid[0]), len(grid[0])-1))]
    return get_vertical(grid, index)+get_horizontal(grid, index)

def get_matrix(grid:list):
    last_el = uni_index(grid, (len(grid)-1, len(grid[0])-1))
    elements=len(grid[0])*len(grid)
    matrix=[[INF for _ in range(elements)] for _ in range(elements)]
    for index in range(last_el):
        neibs=get_neibs(grid, index)
        neibs=[neib for neib in neibs if grid[real_index(grid, neib)[0]][real_index(grid, neib)[1]]!=3]
        for neib in neibs:
            matrix[index][neib]=1
    return matrix

def get_start(grid:list):
    for i in range(len(grid)):
        try:
            return (i, grid[i].index(1))
        except ValueError:
            pass

def get_end(grid:list):
    for i in range(len(grid)):
        try:
            return (i, grid[i].index(2))
        except ValueError:
            pass

def Dijkstra(N, S, matrix):
    valid = [True]*N
    weight = [1000000]*N
    weight[S] = 0
    for i in range(N):
        min_weight = 1000001
        ID_min_weight = -1
        for i in range(N):
            if valid[i] and weight[i] < min_weight:
                min_weight = weight[i]
                ID_min_weight = i
        for i in range(N):
            if weight[ID_min_weight] + matrix[ID_min_weight][i] < weight[i]:
                weight[i] = weight[ID_min_weight] + matrix[ID_min_weight][i]
        valid[ID_min_weight] = False
    return weight

grid=redef_grid(grid)
if is_valid(grid):
    matrix=get_matrix(grid)
    paths = Dijkstra(len(grid)*len(grid[0]), uni_index(grid, get_start(grid)), matrix)
    shortest_path = paths[uni_index(grid, get_end(grid))]
    if shortest_path==INF: shortest_path='No solution'
    print(shortest_path)
else: print('Invalid grid')

Answer 2

Это было весело. Подход методом грубой силы вычисляет все возможные пути в системе и, наконец, находит минимальную длину пути из тех, которые заканчиваются на 2. Обратите внимание, что init просто возвращает допустимую матрицу для работы. Если решение для матрицы не найдено, None возвращает функцию решения.

BLOCK=3
FINAL=2
TERMINATE=None
INITIAL=1
PATH=0

def init(n,m):
  # returns array with essential components, but not necessarily with solution
  import numpy
  import random
  while True:
    try:
      a=numpy.zeros((n,m),dtype=int)
      for i in range(n):
        for j in range(m):
          t=INITIAL
          # initialize to anything but INITIAL
          while t==INITIAL: t=numpy.random.randint(PATH,BLOCK)
          a[i,j]=t
      c=random.choice(list(zip(*(a==PATH).nonzero())))
      a[c]=INITIAL
      finals=list(zip(*(a==FINAL).nonzero()))
      c=random.choice(finals)
      for i in finals:
        if i!=c: a[i]=BLOCK
      break
    except:
      continue
  return a

def possible_moves(a,pos):
  n,m=a.shape
  test_moves=[(0,1),(1,0),(-1,0),(0,-1)]
  #print('from pos={}'.format(pos))
  x,y=pos[0:2]
  valid_moves=[]
  for t in test_moves:
    new=(t[0]+x,t[1]+y)
    if t[0]+x>-1 and \
       t[0]+x<n and \
       t[1]+y>-1 and \
       t[1]+y<m:
      if a[new] not in [BLOCK]:
        valid_moves.append((t[0]+x,t[1]+y))
  return valid_moves

def allpaths(a,paths):
  for path in paths:
    if path[-1] in [TERMINATE,FINAL]: continue
    pos=path[-1]
    moves=possible_moves(a,pos)
    if not moves:
      path.append(TERMINATE) # if no moves left, path is terminated
      continue
    base=path.copy()
    for im,move in enumerate(moves):
      b=a.copy()
      # set previous position to BLOCK so can't move into previous positions
      b[pos]=BLOCK
      if im==0:
        if a[move]==FINAL: path.append(FINAL) # if position to move to is FINAL, indicate
        else: path.append(move)
      else:
        if a[move]==FINAL: paths.append(base+[FINAL])
        else: paths.append(base+[move])
    paths=allpaths(b,paths)
  return paths

def solve(a):
  ipos=list(zip(*(a==INITIAL).nonzero()))
  paths=[ipos]
  paths=allpaths(a,paths)
  M=a.shape[0]*a.shape[1]
  minlen=M
  for path in paths:
    if path[-1] in [FINAL]:
      minlen=min(minlen,len(path)-1)
  if minlen==M: return None
  else: return minlen

n,m=5,6
a=init(n,m)
print(n,m)
print(a)

minlen=solve(a)
print(minlen)

Чтобы зафиксировать «право», вы можете просто отследить предыдущую позицию до функции возможные_перемещения и убедиться, что вы только возвращаетесь » прямые "и" правильные "направления (" назад "уже защищено, поскольку они закодированы).