여기

Question

는 내가 수를 찾기 위해 재귀 알고리즘을 사용하고 HashMap의

private int steps=0; 
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>(); 
private HashMap<MazeCell, Boolean> visitedCells = new HashMap<MazeCell, Boolean>(); 
public int stepsToSolveMaze(MazeCell cell) 
{  
    if (visitedCells.get(cell) == null) 
    { 
     visitedCells.put(cell, true); 
     breadCrumbs.push(cell); 
    }  

를 사용하여, 지금이 권리를 구현하고 어떻게 내가 미로에 입력 한 세포의 추적을 유지하기위한 최선의 데이터 구조를 무엇입니까 미로의 끝에 단계. 내가 다음 단계를 밟기 전에 나는 내가 어디를 밟고 있는지 확인해야한다. 내가 있었던 곳을 제외하고는 null로 가득 찬 HashMap보다 나은 데이터 구조가있는 것처럼 느껴진다.하지만 실마리가 없다. 누구든지 이것에 대한 더 나은 데이터 구조를 알고 있습니까?

Answer 1

HashMap 대신 HashSet을 사용해야합니다. 이 코드는 읽기 쉽습니다. HashSet은 HashMap<E,Object>에 의해 백업되므로 성능은 동일합니다.

private int steps=0; 
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>(); 
private Set<MazeCell> visitedCells = new HashSet<MazeCell>(); 
public int stepsToSolveMaze(MazeCell cell) 
{  
    if (!visitedCells.contains(cell)) 
    { 
     visitedCells.add(cell); 
     breadCrumbs.push(cell); 
    } 
} 

HashSetoffers constant time performance for the basic operations.

Answer 2

현재의 디자인은 괜찮습니다. 셀 수가 고정되어 있으면 셀을 배열에 저장하고 비트 벡터를 사용하여 방문한 셀을 나타낼 수 있습니다. 예를 들어, 32 비트 정수는 32 개의 셀을 나타낼 수 있습니다.

Answer 3

전체 매트릭스에 대해 boolean[][]일까요?

너가 너무 큰 행렬을 다루지 않는다면, 나는 아마이 옵션을 가지고 갈 것이다.

1000x1000은 그리 크지 않고 전체 매트릭스가 약 1MB의 저장 공간 (implementation dependent)을 차지합니다.

읽기/쓰기의 오버 헤드는 해시 사용보다 적어야합니다. 나쁜 해시 함수를 사용하면 해싱 성능이 끔찍할 수 있다는 점도 유의해야합니다. 2D 어레이 솔루션에는 이러한 단점이 없습니다.

적은 스토리지 집약적 솔루션은 BitSet[]이고 1000x1000 매트릭스의 경우 약 125KB 스토리지로 들어갑니다. 당신은 더 많은 저장 공간을 줄이기 위해 빈 행/열 (구현에 따라)가 어느 경우 (boolean[] 또는 BitSet가 널 (NULL) 일 수있는)에 null 값을 가질 수 있습니다

참고.

면책 조항 : 위의 수치는 추정치이며, 몇 가지를 무시했습니다.

Answer 4

Disjoint Set

그것은 데이터 구조의이 종류를 구현하는 가장 효율적인 방법입니다.

간단히 말해서 미로를 나타내는 정수의 2 차원 배열을 만드는 것입니다. 배열의 각 행 열은 미로의 x, y 좌표입니다. 좌표 위치에있는 값은 그 안에있는 "세트"를 나타냅니다.

위치를 방문한 경우 해당 위치에 1을 넣으십시오.

그래서 좌표를 방문하지 않으면 0이 포함됩니다.