[python] 이미지가 주어진 미로를 표현하고 해결하기

이 문제에 대해 A-Star 검색을 구현하려고했습니다. 프레임 워크와 여기에 주어진 알고리즘 의사 코드에 대한 Joseph Kern 의 구현을 면밀히 따랐 습니다 .

def AStar(start, goal, neighbor_nodes, distance, cost_estimate):
    def reconstruct_path(came_from, current_node):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = came_from[current_node]
        return list(reversed(path))

    g_score = {start: 0}
    f_score = {start: g_score[start] + cost_estimate(start, goal)}
    openset = {start}
    closedset = set()
    came_from = {start: None}

    while openset:
        current = min(openset, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, goal)
        openset.remove(current)
        closedset.add(current)
        for neighbor in neighbor_nodes(current):
            if neighbor in closedset:
                continue
            if neighbor not in openset:
                openset.add(neighbor)
            tentative_g_score = g_score[current] + distance(current, neighbor)
            if tentative_g_score >= g_score.get(neighbor, float('inf')):
                continue
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal)
    return []

A-Star는 휴리스틱 검색 알고리즘이므로 목표에 도달 할 때까지 남은 비용 (여기 : 거리)을 추정하는 기능이 필요합니다. 차선책 솔루션에 익숙하지 않으면 비용을 과대 평가해서는 안됩니다. 보수적 인 선택은 여기서 맨하탄 (또는 택시) 거리 입니다. 이는 사용 된 폰 노이만 (Von Neumann) 이웃에 대한 그리드상의 두 점 사이의 직선 거리 를 나타냅니다. (이 경우 비용을 과대 평가하지는 않습니다.)

그러나 이것은 주어진 미로에 대한 실제 비용을 상당히 과소 평가합니다. 따라서 비교를 위해 두 개의 다른 거리 메트릭에 제곱 유클리드 거리와 맨해튼 거리에 4를 곱한 값을 추가했습니다. 그러나 이는 실제 비용을 과대 평가하여 차선책의 결과를 산출 할 수 있습니다.

코드는 다음과 같습니다.

import sys
from PIL import Image

def is_blocked(p):
    x,y = p
    pixel = path_pixels[x,y]
    if any(c < 225 for c in pixel):
        return True
def von_neumann_neighbors(p):
    x, y = p
    neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
    return [p for p in neighbors if not is_blocked(p)]
def manhattan(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def squared_euclidean(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2

start = (400, 984)
goal = (398, 25)

# invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]

path_img = Image.open(sys.argv[1])
path_pixels = path_img.load()

distance = manhattan
heuristic = manhattan

path = AStar(start, goal, von_neumann_neighbors, distance, heuristic)

for position in path:
    x,y = position
    path_pixels[x,y] = (255,0,0) # red

path_img.save(sys.argv[2])

다음은 결과를 시각화하기위한 일부 이미지입니다 ( Joseph Kern이 게시 한 이미지에서 영감을 얻음 ). 애니메이션은 기본 while 루프를 10000 회 반복 한 후 각각 새로운 프레임을 보여줍니다.

너비 우선 검색 :

스타 맨하탄 거리 :

별 제곱 유클리드 거리 :

A-Star Manhattan Distance에 4를 곱한 값 :

결과는 미로의 탐색 된 영역이 사용되는 휴리스틱에 대해 상당히 다르다는 것을 보여줍니다. 따라서, 제곱 유클리드 거리는 다른 메트릭과는 다른 (차선이 아닌) 경로를 생성합니다.

종료까지의 런타임 측면에서 A-Star 알고리즘의 성능과 관련하여, 거리 및 비용 함수에 대한 많은 평가는 BFS (Breadth-First Search)와 비교하여 “goaliness”만 평가하면됩니다. 각 후보자 위치. 이러한 추가 기능 평가 (A-Star)에 대한 비용이 많은 수의 노드 (BFS)에 대한 비용보다 큰지 여부, 특히 성능이 애플리케이션에 전혀 문제가되지 않는지는 개별 인식의 문제입니다. 물론 일반적으로 대답 할 수 없습니다.

정보 검색 알고리즘 (예 : A-Star)이 전체 검색 (예 : BFS)에 비해 더 나은 선택이 될 수 있는지에 대해 일반적으로 말할 수 있는 것은 다음과 같습니다. 미로의 차원의 수, 즉 검색 트리의 분기 인자에 따라, 철저한 검색 (완전히 검색)의 단점이 기하 급수적으로 증가한다. 복잡성 증가로 당신이 꽤 많이 행복과 그래서 어떤 시점에서 할 적게 가능하게 어떤 결과로, 그것은 (약) 최적의 여부를합니다.

답변

% read in and invert the image
im = 255 - imread('maze.jpg');

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count < 500
        result(result==i) = 0;
    end
end

% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
    k = zeros(1002,800);
    k(result==i) = 1; k = imclose(k,strel('square',8));
    closed(k==1) = i;
end

% do output
out = 255 - im;
for x = 1:1002
    for y = 1:800
        if closed(x,y) == 0
            out(x,y,:) = 0;
        end
    end
end
imshow(out);

from PIL import Image
img = Image.open("/tmp/in.jpg")
(w,h) = img.size
scan = [(394,23)]
while(len(scan) > 0):
    (i,j) = scan.pop()
    (r,g,b) = img.getpixel((i,j))
    if(r*g*b < 9000000):
        img.putpixel((i,j),(210,210,210))
        for x in [i-1,i,i+1]:
            for y in [j-1,j,j+1]:
                scan.append((x,y))
img.save("/tmp/out.png")