인프런 커뮤니티 질문&답변
작성한 질문수
A* 알고리즘 질문입니다
작성
·
286
0
안녕하세요 강사님
강의를 여러번 돌려보다보니 이해가 안되고 넘어갔었던 부분들도 조금씩 이해가 가고 있는 중입니다
A* 강의를 모두 듣고 궁금한점이 생겨서 질문드립니다
최단 거리가 아니라 방문했었던 모든 길들을 표시해보고싶어서
List<Pos> visitedPoint = new List<Pos>(); 로 리스트를 만들고
마지막에 pq.Push() 부분에서 visitedPoint.Add(new Pos(nextY, nextX)); 로 방문한 자점들을 모두 등록한 후에
플레이어 위치 업데이트 부분에서 visitedPoint 에 있는 좌표를 하나씩 표시하도록 하였는데
처음 예상에는 일단 길이 있는 부분으로 간뒤에 막히면 다시 왔던 길로 돌아간 뒤에 방문하지 않은 쪽으로 이동할 줄 알았는데
미리 예약된(?) 좌표인건지 플레이어의 위치가 이리저리 워프가 되는데 pq노드 안에 등록되었던 예약된 좌표 중에 g+h가 더 적은 위치로 이동이 되는건가요?
그리고 하나더 궁금한게 closed를 이용해서 한번 방문한 지점은 더이상 방문하지 않도록 하였는데
방문했었던 지점도 더 효율적으로 재방문 할수 있을것 같은데 한번만 방문할수 있도록 만들어져있는데 이건 현재 타일맵이라서 작성된 부분일까요?
답변 2
0
0
처음 예상에는 일단 길이 있는 부분으로 간뒤에 막히면 다시 왔던 길로 돌아간 뒤에 방문하지 않은 쪽으로 이동할 줄 알았는데
-> 아닙니다!
미리 예약된(?) 좌표인건지 플레이어의 위치가 이리저리 워프가 되는데 pq노드 안에 등록되었던 예약된 좌표 중에 g+h가 더 적은 위치로 이동이 되는건가요?
-> 이게 맞습니다!
그리고 하나더 궁금한게 closed를 이용해서 한번 방문한 지점은 더이상 방문하지 않도록 하였는데
방문했었던 지점도 더 효율적으로 재방문 할수 있을것 같은데 한번만 방문할수 있도록 만들어져있는데 이건 현재 타일맵이라서 작성된 부분일까요?
-> 타일맵과는 무관하고 알고리즘 자체가 그렇습니다.
이미 방문한 지점을, 뒤늦게 더 효율적으로 재방문할 수 있는 경로를 찾을 수 없다는 것은
수학적 귀납법으로 증명할 수 있습니다.
(예약만 하고 방문은 아직 안 한 시점에서, 뒤늦게 더 효율적인 경로를 찾을 수는 있습니다)
closed를 사용하지 않으면 이미 방문이 끝난 점을
또 다시 pq에 넣고~ 하면서 로직이 꼬이기 때문에 꼭 넣어줘야 합니다.