Нахождение самого длинного пути с использованием рекурсии с набором правил - PullRequest
Новая
       38

Нахождение самого длинного пути с использованием рекурсии с набором правил

0 голосов
/ 13 мая 2019

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

   [0, 0, 0, 0, 0],
   [0, 1, 0, 0, 0],
   [1, 1, 1, 0, 0],
   [0, 0, 0, 0, 0],
   [1, 0, 0, 1, 0],

Правила таковы:

  1. Начните с заданной позиции «1», это действительные позиции.

  2. Каждый прыжок должен быть на другую действительную позицию в той же строке или столбце (можно перепрыгнуть через «0»).

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

  4. Никакая позиция не может быть использована дважды.

Допустимый путь в примере матрицы будет выглядеть так: 

(5,4),(5,1),(3,1),(3,3),(3,2),(2,2)

Неверный путь из-за правила # 3 будет выглядеть так: 

(3,1),(3,2),(3,3)

, тогда как следующие возможны : 

(3,1),(3,3),(3,2)

Хотя у меня есть небольшой опыт работы с python, я никогда не пробовал рекурсию (я почти уверен, что это то, что нужно для решения этой проблемы), и я не могу найти какую-либо помощь онлайн, которая находится на моем уровне.

Ответы [ 2 ]

1 голос
/ 13 мая 2019

Есть несколько решений для этого. Я бы предложил сначала преобразовать сетку в более объектно-ориентированную структуру, то есть ненаправленный граф с узлами, для которых на входе присутствуют единицы.

Тогда я бы выделил три вида ребер на этом графике:

  • Те, где одна из конечных точек находится по диагонали («специальные» ребра)
  • Те, где вышеприведенное неверно, но узлы находятся в одной строке
  • Те, где вышеприведенное неверно, но узлы находятся в одном столбце

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

Вот реализация: 

class Node:
    def __init__(self, y, x, size):
        self.x = x
        self.y = y
        self.coord = (y, x)
        self.diagonal = x == y or size - 1 - y
        # Separate lists of neighbors: vertical, horizontal. 
        # Third list is for when this node or neighbor is on diagonal
        self.neighbors = [[], [], []] 

    def addNeighbor(self, node, direction):
        self.neighbors[direction].append(node)

class Maze:
    def __init__(self, grid):
        def addedge(a, b):
            direction = 2 if a.diagonal or b.diagonal else int(a.x == b.x)
            a.addNeighbor(b, direction)
            b.addNeighbor(a, direction)

        # alternative grid having Node references:
        self.nodes = [[None] * len(grid) for _ in grid] 
        colNodes = [[] for _ in grid]
        for y, row in enumerate(grid):
            rowNodes = []
            for x, cell in enumerate(row):
                if cell: # only create nodes for when there is a 1 in the grid
                    node = Node(y, x, len(grid))
                    for neighbor in rowNodes + colNodes[x]:
                        addedge(node, neighbor)
                    rowNodes.append(node)
                    colNodes[x].append(node)
                    self.nodes[y][x] = node

    def findpath(self, y, x):
        def recur(node, neighbors):
            visited.add(node)
            longest = [node.coord]
            # always visit "special" neighbors 
            #   (i.e. those on diagonal or all vert/horiz when node is on diagonal)
            for neighbor in node.neighbors[2] + neighbors:
                if not neighbor in visited:
                    # toggle direction when going further
                    path = recur(neighbor, node.neighbors[1-int(node.x == neighbor.x)])
                    if len(path) >= len(longest):
                        longest = [node.coord] + path
            visited.remove(node)
            return longest

        node = self.nodes[y][x]
        if not node:
            raise "Cannot start from that position"
        visited = set()
        # look in both directions of starting node
        return recur(node, node.neighbors[0] + node.neighbors[1]) 


grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 1, 0]
]

maze = Maze(grid)
path = maze.findpath(2, 0)
print(path)  # output: [(2, 0), (2, 2), (2, 1), (1, 1)]

path = maze.findpath(4, 3)
print(path)  # output: [(4, 3), (4, 0), (2, 0), (2, 2), (2, 1), (1, 1)]

Обратите внимание, что координаты в этом решении начинаются с нуля, поэтому первая строка имеет номер 0 и т. Д.

Посмотреть, как он работает на repl.it

0 голосов
/ 13 мая 2019

Вы можете использовать рекурсию с генератором: 

d = [[0, 0, 0, 0, 0], [0, 1, 0, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 0, 0], [1, 0, 0, 1, 0]]
_d = {1:lambda a, b:'f' if b[-1] > a[-1] else 'b', 0:lambda a, b:'u' if b[0] > a[0] else 'd'}
def paths(start, _dir, c = []):
   yield c
   _options = [(a, b) for a in range(len(d)) for b in range(len(d[0])) if (a, b) not in c and d[a][b]]
   if _options:
      for a, b in _options:
         if a == start[0] or b == start[-1]:
            r = _d[a == start[0]](start, (a, b))
            if _dir is None or r != _dir:
               yield from paths((a, b), r, c+[(a, b)])


print(max(list(paths((4, 3), None, [(4, 3)])), key=len))

Выход: 

[(4, 3), (4, 0), (2, 0), (2, 2), (2, 1), (1, 1)]
...