Блог

Я пытаюсь решить это упражнение:

Как часть планировщика маршрутов, метод route_exists используется в качестве быстрого фильтра, если пункт назначения достижим, прежде чем использовать более трудоемкие процедуры для поиска оптимального маршрута. Дороги на карте растрируются и создают матрицу логических значений — True, если дорога присутствует, или False, если ее нет. Дороги в матрице соединяются только в том случае, если дорога сразу слева, справа, ниже или выше нее. Завершите метод route_exists, чтобы он возвращал True, если пункт назначения достижим, или False, если это не так. Параметры from_row и from_column являются начальной строкой и столбцом в map_matrix. to_row и to_column являются строкой и столбцом назначения в map_matrix. Параметр map_matrix — это вышеупомянутая матрица, созданная на основе карты. Например, следующий код должен возвращать True, поскольку пункт назначения достижим:

 map_matrix = [
    [True, False, False],
    [True, True, False],
    [False, True, True]
];

route_exists(0, 0, 2, 2, map_matrix)
  

Мое решение с рекурсией:

 def route_exists(from_row, from_column, to_row, to_column, map_matrix):
    if route_exists2(from_row, from_column, to_row, to_column, map_matrix):
        return True
    else:
        return False
def route_exists2(from_row, from_column, to_row, to_column, map_matrix):
    if (from_row<0 or from_row>=len(map_matrix) or from_column<0 or from_column>=len(map_matrix[0])):
        return False
    if map_matrix[from_row][from_column]:
        map_matrix[from_row][from_column]=False #traversed
        if (from_row == to_row and from_column ==to_column):
            return True
        return (route_exists2(from_row-1, from_column, to_row, to_column, map_matrix) or
                route_exists2(from_row, from_column-1, to_row, to_column, map_matrix) or
                route_exists2(from_row, from_column 1, to_row, to_column, map_matrix) or
                route_exists2(from_row 1, from_column, to_row, to_column, map_matrix))
        
if __name__ == '__main__':
    map_matrix = [
        [True, False, False],
        [True, True, False],
        [False, True, True]
    ];

    print(route_exists(0, 0, 2, 2, map_matrix))
  

Я получаю только 50% в 4 тестовых примерах этого упражнения с логическими ошибками, и я не могу воссоздать ошибку из тестовых примеров.

Окончательное решение, о котором упоминал @Frank Yellin.

 def route_exists(from_row, from_column, to_row, to_column, map_matrix):
    visited = [[False for i in range(len(map_matrix[0]))] for j in range(len(map_matrix))]
    
    def route_exists2(from_row, from_column, to_row, to_column, map_matrix):
        if (from_row<0 or from_row>=len(map_matrix) or from_column<0 or from_column>=len(map_matrix[0]) or visited[from_row][from_column]==True):
            return False
        if map_matrix[from_row][from_column]:
            visited[from_row][from_column]=True
            #map_matrix[from_row][from_column]=False #traversed
            if (from_row == to_row and from_column ==to_column):
                return True
            return (route_exists2(from_row-1, from_column, to_row, to_column, map_matrix) or
                    route_exists2(from_row, from_column-1, to_row, to_column, map_matrix) or
                    route_exists2(from_row, from_column 1, to_row, to_column, map_matrix) or
                    route_exists2(from_row 1, from_column, to_row, to_column, map_matrix))

    
    if route_exists2(from_row, from_column, to_row, to_column, map_matrix):
        return True
    else:
        return False
    
    
if __name__ == '__main__':
    map_matrix = [
        [True, False, False],
        [True, True, False],
        [False, True, True]
    ];
    

    print(route_exists(0, 0, 2, 2, map_matrix))
  

Результат 4/4!

Вам нужно изменить конец на:

 result = (rout_exists2..........)
map_matrix[from_row][from_column] = True
return result
  

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

===== Расширяю свой ответ ======

Представьте внешний вызов route_exists2() . Он хочет выполнить четыре рекурсивных вызова route_exists2() , и матрица, которую он хочет передать каждому из этих четырех рекурсивных вызовов, является полученной матрицей с изменением одной ячейки. Но каждый из этих четырех рекурсивных вызовов может дополнительно модифицировать матрицу, и эти изменения никогда не отменяются.

Один из возможных подходов — сопоставить все возможные допустимые пункты назначения с учетом начальной точки, а затем проверить, предусмотрен ли желаемый пункт назначения. Я предполагаю, что это то, чего вы пытаетесь достичь в своем рекурсивном вызове, пытаясь разделить конец вашего route_exists() в нескольких вызовах route_exists() . Но проблема, как указал Фрэнк Йеллин, заключается в том, что, когда первый рекурсивный вызов полностью разрешен, вы устанавливаете для всех дорог этого пути значение False, тем самым избегая других возможных путей использования этих дорог. Я бы предпочел попытаться сохранить последние новые маршруты и взаимодействовать с ними.

 def route_exists(start_x, start_y, end_x, end_y, map_matrix):
    possible_routes = [[[start_x, start_y]]]
        # each route is a list of [x, y] points indicating all the route roads  
    added_routes = 0
    
    while True:
        routes_count = len(possible_routes)
        for route in possible_routes[-added_routes:]:
            # check only the active new rotes and their possible roads
            for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                road_x = route[-1][0]   x
                road_y = route[-1][1]   y
                    # the possible road at the route end
                try:
                    if map_matrix[road_x][road_y]: # the road exists
                        if [road_x, road_y] not in route: # not going backwards
                            new_route = route   [[road_x, road_y]]
                            if new_route not in possible_routes:
                                possible_routes.append(new_route)
                except:
                    pass

        added_routes = len(possible_routes) - routes_count
        if added_routes == 0:
            break

    destinations = [r[-1] for r in possible_routes]
    if [end_x, end_y] in destinations:
        return True
    else:
        return False
  

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