notebook.community

Edit and run

3 Zaimplementuj algorytm znalezienia najkrótszej ścieżki w labiryncie na podstawie algorytmu Źródło: http://www.unit1.pl/349,txt (2018-02-12)

Wynik: najkrótsza ścieżka
Wynik: Droga w labiryncie, która prowadzi z pola s do wyjścia.
Krok 0: Przyjmij, ze na początku nie byłeś w żadnym polu labiryntu, a więc wszystkie pola są nieodwiedzone.
Krok 1: Umieść w kolejce Q pole s. W polu s umieść liczbę 0 (zero).
Krok 2: Dopóki kolejka Q nie jest pusta wykonuj kroki 3 – 5.

Krok 3: Usuń z kolejki Q jej pierwszy element - oznaczmy to pole przez v.
Krok 4: Dla każdego pola w sąsiedniego względem v i nieoddzielonego od niego ścianą wykonaj krok 5.
Krok 5: Jeśli nie byłeś jeszcze w polu w, to umieść w nim liczbę o jeden większą od liczby znajdującej się w polu v. Jeśli pole w zawiera wyjście to przejdź do kroku 6, a w przeciwnym razie dołącz w do końca kolejki Q.
Krok 6: (W tym kroku budujemy od końca listę pól tworzących najkrótszą drogę z pola s do pola w, na którym zakończył działanie krok 5). Dopóki w nie jest polem s, wykonuj: za kolejne (od końca) pole drogi przyjmij w i za nową wartość w przyjmij pole sąsiednie względem w, w którym znajduje się liczba o jeden mniejsza od liczby znajdującej się w obecnym polu w.



In [ ]:

    
from collections import namedtuple, deque

Point = namedtuple("Point", "x y")

_wall = object()

maze = [
    [-1, -1,    -1, -1],
    [-1, _wall, -1, -1],
    [-1, _wall, -1, -1],
    [-1, -1, _wall, -1]
]

expected_result = [
    Point(0, 0),
    Point(0, 1),
    Point(1, 2),
    Point(2, 3),
    Point(3, 3)
]

expected_result2 = [
    Point(0, 0),
    Point(0, 1),
    Point(1, 2),
    Point(2, 2),
    Point(3, 3)
]



In [ ]:

    
def shortest_path(maze, starting_point, exit_point):
    que = deque()
    maze[starting_point.x][starting_point.y] = 0
    que.append(starting_point)

    while len(que):
        point = que.popleft()
        neighbours = _find_neighbours(maze, point)
        not_visited = _filter_visited(maze, neighbours)
        if _increment_neighbors_value(maze, point, not_visited, exit_point):
            return _get_path(maze, exit_point, starting_point)
        que.extend(not_visited)


def _find_neighbours(maze, tested_point):
    maze_length = len(maze)
    point_x = tested_point.x
    point_y = tested_point.y
    points = (Point(x, y) for x in range(point_x - 1, point_x + 2) for y in range(point_y - 1, point_y + 2))

    result = []
    for point in points:
        if (point.x >= 0 and point.y >= 0
            and point.y < maze_length
            and point.x < maze_length
            and point != tested_point
            and _point_not_a_wall(maze, point)):
                result.append(point)
    return result


def _point_value(maze, point):
    return maze[point.x][point.y]


def _point_not_a_wall(maze, point):
    return _point_value(maze, point) != _wall


def _filter_visited(maze, points):
    return [point for point in points if _point_value(maze, point) == -1]


def _increment_neighbors_value(maze, point, neighbours, exit_point):
    value = _point_value(maze, point)

    for p in neighbours:
        maze[p.x][p.y] = value + 1
        if p == exit_point:
            return True
    return False


def _get_path(maze, exit_point, starting_point):
    result = [exit_point]
    que = deque([exit_point])

    while que:
        point = que.popleft()

        value = _point_value(maze, point)
        neighbours = _find_neighbours(maze, point)
        for neighbour in neighbours:
            if neighbour == starting_point:
                result.append(neighbour)
                break
            if _point_value(maze, neighbour) == value - 1:
                result.append(neighbour)
                que.append(neighbour)
                break
    return list(reversed(result))

result = shortest_path(maze, Point(0, 0), Point(3, 3))
assert result == expected_result or result == expected_result2