노드 사이에 비용 저장

Question

저는 Uniform Cost Search를 사용하여 미로 솔버를 만들고 있습니다. 기본적으로 내가하고 싶은 것은 제 미로 룸의 임의 비용을 저장하는 것입니다. 객실

데이터 구조 (명명 된 세포) :

struct Cell 
    { 
     int row; 
     int column; 
     vector<Cell*> neighbors; 
     State state; 
    }; 

행 및 열은 셀의 미로 벡터 위치이다는 vector<Cell*> neighbors은 특정 셀이 접속되어있는 셀과 정의하고 상태는 유지 세포의 상태 (방문, 비어 있음).

내가 시도한 것은 Cell 구조체의 속성을 다음과 같이 만들었습니다. vector<int> cost 배열의 모든 요소가 인접 요소와 일치합니다. 예를 들어

:

0 ###### 
1 # ## 
2 # # # 
3 ###### 

미로 [1] [1] 그것의 이웃 벡터에 있습니다

neighbors[0] = *maze[1][2]; 
neighbors[1] = *maze[2][1]; 

는 비용 벡터는 이제입니다 :

cost[0] = 5; 
cost[1] = 10; 

그러나 그 방법 그것을하는 것은 많은 문제를 일으켰습니다.

내가 생각하는 나는,이 같은 또 다른 하나 개의 노드를 일치 매트릭스의 비용을 저장하는 비용 행렬을 필요로한다는 것입니다 :

0 1 2 
0[0][2][4] 
1[2][0][6] 
2[4][6][0] 

그러나 순서

이 작업을 수행하기 위해 어떻게 그럴께요 내 행렬에 어떤 셀이 있는지 알려주시겠습니까? 어떻게 0과 1 대신에 [0] [0] [1] [0] [2] 등등인지 알 수 있습니다.

이렇게하려면 3D 벡터를 사용해야합니까? 3D 벡터로 경험이 없기 때문에 나는 그것을 피하기를 원합니다.

Answer 1

다른 방으로 연결되는 링크에 맞춤 개체를 사용할 수 없습니까? 예 :

struct Cell; 

struct CellLink { 
    const Cell *cell; 
    const int weight; 
    .. 
}; 

struct Cell { 
    int row; 
    int column; 
    vector<CellLink> neighbors; 
    State state; 
}; 

이렇게하면 비용과 셀을 걱정없이 유지할 수 있습니다. 단점은 각 비용을 두 번 저장한다는 것입니다 (대칭이라고 가정). 그러나 이것은 다른 많은 접근법 (매트릭스 포함)에서도 마찬가지입니다.