그리드에서 인접한 색상 영역을 결정하는 알고리즘이 있습니까?

StackOverflow https://stackoverflow.com/questions/452480

  •  19-08-2019
  •  | 
  •  

문제

각 셀이 N 색상 중 하나로 무작위로 채워진 기본 그리드 (그래프 용지와 같은)가 주어지면, 어떤 연속 영역 (동일한 셀 그룹의 셀 그룹)을 알려주는 시도 및 진정한 알고리즘이 있습니까? 옆에 결합 된 색상) 거기에 있습니까? N이 5와 같은 합리적인 것이라고 가정 해 봅시다.

나는 몇 가지 아이디어가 있지만 그들은 모두 끔찍하게 비효율적이라고 느낍니다.

도움이 되었습니까?

해결책

가능한 가장 좋은 알고리즘은 O (셀 수)이며 색상 수와 관련이 없습니다.

이것은 세포를 반복하여 달성 할 수 있으며, 방문한대로 표시되지 않은 것을 방문 할 때마다 그래프 트래버스를 수행하여 해당 영역의 모든 인접한 셀을 찾은 다음 계속 반복합니다.

편집하다:

다음은 깊이있는 첫 번째 검색의 간단한 의사 코드 예입니다.이 검색은 그래프 트래버스를 쉽게 구현할 수 있습니다.

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

다른 팁

재귀의 재귀 답변 외에도 재귀가 너무 느려지면 스택을 사용할 수 있습니다.

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

각 광장에서 홍수 채우기를 시도 할 수 있습니다. 홍수가 퍼지면서 그리드 사각형을 어레이 또는 무언가에 기록하고 사용하지 않은 색상으로 색칠하십시오.

홍수 채우기에 관한 Wikipedia 기사는 여기에 유용 할 수 있습니다. http://en.wikipedia.org/wiki/flood_fill

노조 찾기 여기서도 작동 할 것입니다. 실제로, 당신은 그래프에 대한 문제로 질문을 공식화 할 수 있습니다. 정점은 그리드 셀이며, 그리드 셀의 색상이 동일한 경우 두 개의 정점이 인접 해 있습니다. 연결된 구성 요소를 찾으려고합니다.

노조 찾기 데이터 구조를 사용하는 방법은 다음과 같습니다. 먼저 셀만큼 많은 요소를 가진 노조 찾기 데이터 구조를 만듭니다. 그런 다음 세포를 통해 반복하고 union 동일한 색상을 가진 경우 인접한 두 개의 세포. 결국, 달리기 find 각 셀에 응답을 저장하십시오. 같은 세포 find 연속적인 색상 영역에 있습니다.

좀 더 훌륭한 곡물 제어를 원한다면 사용에 대해 생각할 수 있습니다. ㅏ* 알고리즘 및 유사성 타일을 포함하도록 휴리스틱을 사용하십시오.

당신은 스캔 라인으로 지역을 반복하여 왼쪽 오른쪽 상단 바닥으로갑니다. 각 세포에 대해 세포 사이의 동일한 메모리 객체로 공유 된 세포 목록을 만듭니다. 각 셀에 대해 현재 셀을 목록에 추가합니다 (공유 또는 생성). 그런 다음 오른쪽 또는 아래의 셀이 동일한 색상이라면 해당 목록을 해당 셀과 공유합니다. 해당 셀에 이미 목록이있는 경우 목록을 결합하고 목록에 나열된 각 셀의 목록 개체에 대한 참조를 새 병합 목록으로 바꿉니다.

그런 다음 각 셀에 위치한 것은 해당 셀과 함께 모든 인접한 셀을 포함하는 목록에 대한 참조가 있습니다. 이것은 모든 세포 사이의 홍수 수유의 작업을 적절하게 결합합니다. 각 셀에 대해 반복하는 대신. 데이터를 병합 된 데이터로 바꾸는 목록이 있으므로 목록을 통해 반복됩니다. 여기서 n은 셀의 수이고 C는 그래프가 얼마나 연속적인 지에 대한 척도입니다. 완전히 분리 된 그리드는 N 시간입니다. N^2/2 인 완전히 인접한 1 컬러 그래프.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top