Zadanie 82 polega na znalezieniu drogi z lewej kolumny do prawej kolumny, która będzie przechodzić po polach dających najmniejszą możliwą sumę. Zadanie można sprowadzić do poszukiwania najkrótszej ścieżki w grafie, dla odpowiednio skonstruowanego grafu (takie zadanie można już np. rozwiązać algorytmem Dijkstry).
Zastosowałem małą modyfikację tego algorytmu, ponieważ oryginalny algorytm służy do szukania najkrótszej ścieżki w grafie, w którym wagi przejść mają krawędzie. W tym zadaniu wagi mają wierzchołki, ale pomysł pozostał ten sam.
Rozwiązanie:
Pomyślałem, że można nieco rozwinąć to rozwiązanie i spróbować je namalować. Z biblioteką turtle jest to w miarę możliwe. Oto efekty:
Dla ciekawych, kod:
Zastosowałem małą modyfikację tego algorytmu, ponieważ oryginalny algorytm służy do szukania najkrótszej ścieżki w grafie, w którym wagi przejść mają krawędzie. W tym zadaniu wagi mają wierzchołki, ale pomysł pozostał ten sam.
Rozwiązanie:
from heapq import heappop, heappush, heapify f = open("p082_matrix.txt") lines = f.readlines() matrix = [map(int, line.strip().split(",")) for line in lines] N = len(matrix) # matrix is square, [0..N-1] x [0..N-1] queue = [(matrix[row][0] + matrix[row][1], row, 1) for row in range(N)] dist = {(row, 0): matrix[row][0] for row in range(N)} heapify(queue) while queue: cost, row, col = heappop(queue) if col == N - 1: print cost, row, col break if (row, col) in dist: continue dist[(row, col)] = cost heappush(queue, (cost + matrix[row][col + 1], row, col + 1)) if row > 0: heappush(queue, (cost + matrix[row - 1][col], row - 1, col)) if row < N - 1: heappush(queue, (cost + matrix[row + 1][col], row + 1, col))
Pomyślałem, że można nieco rozwinąć to rozwiązanie i spróbować je namalować. Z biblioteką turtle jest to w miarę możliwe. Oto efekty:
Dla ciekawych, kod:
# encoding=utf-8 from heapq import heappop, heappush, heapify import turtle import time f = open("p082_matrix.txt") lines = f.readlines() matrix = [map(int, line.strip().split(",")) for line in lines] N = len(matrix) # matrix is square, [0..N-1] x [0..N-1] queue = [(matrix[row][0] + matrix[row][1], row, 1, None) for row in range(N)] heapify(queue) dist = {(row, 0): matrix[row][0] for row in range(N)} # Ustawienia malowania turtle.hideturtle() turtle.penup() turtle.tracer(0, 0) turtle.colormode(255) def nice_colors(): step = 7 x = y = z = 0 while True: yield x, y, z if x >= 170 and y >= 255 and z >= 255: x = y = z = 0 elif y == 255 and z == 255: y = z = 0 x = min(x + 3 * step, 255) elif z == 255: z = 0 y = min(y + 7 * step, 255) else: z = min(z + step, 255) color_generator = nice_colors() def draw(wait, (row, col), color=None): if not color: color = next(color_generator) time.sleep(wait) turtle.setpos((col * 5 - 200, row * 5 - 200)) turtle.dot(None, *color) turtle.update() # Wyliczanie odległości i malowanie grafu przeszukiwania. parent = {} while queue: cost, row, col, prev = heappop(queue) curr = row, col if col == N - 1: parent[curr] = prev break if curr in dist: continue parent[curr] = prev dist[curr] = cost heappush(queue, (cost + matrix[row][col + 1], row, col + 1, curr)) if row > 0: heappush(queue, (cost + matrix[row - 1][col], row - 1, col, curr)) if row < N - 1: heappush(queue, (cost + matrix[row + 1][col], row + 1, col, curr)) draw(0.001, curr) # Malowanie najlepszej ścieżki. while curr: draw(0.2, curr, (255, 0, 0)) curr = parent[curr] turtle.exitonclick()
[…] 83 jest uogólnieniem zadania 82. Rozwiązanie z zadania 82 było na tyle ogólne, że jego mała modyfikacja pozwoliła rozwiązać […]
OdpowiedzUsuń