넓은 우선 Matlab에서 미로 찾기

Question

나는 미로를 해결하는 폭 넓은 첫 번째 알고리즘을 구현하려고합니다. 입력으로 나는 n * m 2 진 행렬을 가지고 있는데, 여기서 '1'은 장애물/벽을 의미하고 '0'은 경로/자유 세포를 의미합니다.

나는 알고리즘이 일반적으로 어떻게 작동하는지 알지만, matlab에 정보를 저장하고 진행하는 방법에 어려움을 겪고있다. 기본적으로 시작 셀부터 시작하여 모든 이웃에게 장애물이 있는지 확인하십시오. 그들이 자유 롭다면, 나는 그것들을 잠재적 인 경로로 표시하고, 그런 다음 다시 모든 셀들에 대해 동일한 반복적 인 작업을 수행합니다.

그러나 정보를 저장하는 방법을 알아낼 수 없으므로 결국에는 하나의 경로 만 갖게됩니다. 아이디어가 있습니까?

Answer 1

스타 경로 찾기 알고리즘과 마찬가지로 열기 및 닫기 목록을 사용할 수 있습니다. 모든 이웃을 확인하고 이웃이 장애물이 아닌 경우 공개 목록을 작성하십시오. 모든 이웃과 최소 비용을 가진 이웃을 검사하여 닫힌 목록에 넣습니다. 결국 닫힌 목록에 최적의 경로가 있습니다. 기본적으로 그와 같은 것입니다.

Answer 2

연결되지 않은 그래프의 연결된 구성 요소를 우선 검색으로 검색하는 기능입니다. BFS는 코딩하기가 더 쉬워야합니다.

function comp = findNodeComponentDFS(G, node) 
%Find a connected component of the given node in the unoriented graph. Use 
%Deep first search (Cormen, Rivest, Leiserson) 
%G - connectivity matrix 
%node - given node 
%comp - contain the numbers of all nodes in the found connected component 
%except the node itself 
N = length(G); 
white = ones(1,N);%unexamined vertices 
grey = zeros(1,N);%vertices that are currently examining but with not all edges have been examined yet 
black = zeros(1,N);%vertices with all the edges have been examined 
prev = zeros(1,N); 
current = node; 
stop=false; 
while (~stop) 
    grey(current) = 1; 
    white(current) = 0; 
    next = find(G(current,:) & white,1); 
    if (isempty(next)) 
     black(current) = 1; 
     if (prev(current)==0) 
      stop = true; 
     else 
      current = prev(current);%back to previous vertice 
     end 
    else 
     prev(next) = current; 
     current = next; 
    end 
end 
comp = find(black);