인프런 커뮤니티 질문&답변
작성한 질문수
closed list를 비교하는 부분이 궁금합니다.
작성
·
67
0
24분 24초에 나오는 palyer.cpp, while문 안에 해당 코드에서
closed list는 방문 유무만 체크를 하는데 최소 거리를 찾는것과 무슨 관계가 있는지 모르겠습니다.
closed list에는 다른 경로와 값을 비교하는 부분(비용계산 하는부분)이 없는 것 같은데 어떻게 체크가 되는지 궁금합니다.
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. dpe2233님.
질문하신 closed 리스트에 대한 부분은 A* 알고리즘이나 다익스트라 알고리즘에서 중요하게 사용됩니다. 이 리스트는 이미 처리된 노드나 포인트를 기록하여, 중복된 경로 계산을 피하기 위해 사용됩니다.
Closed 리스트의 역할
방문 여부 확인: 특정 노드를 방문했는지 여부를 빠르게 알기 위함입니다. 이미 처리된 노드라면 다시 연산할 필요가 없으므로, 연산을 줄이고 성능을 향상시킵니다.
최적 경로 보장: 알고리즘에서 최단 경로를 찾기 위해 여러 경로를 탐색합니다. 만약 여러 경로를 통해 같은 노드에 도달할 수 있는 경우가 생긴다면, 이미 방문한 노드는 현 상황에서 최단 경로로 도달한 것임을 의미합니다. 그렇기 때문에 고정할 수 있습니다.
비용 계산과의 관계
비용 계산 자체는 open 리스트(혹은 우선순위 큐)에서 이루어집니다. 특정 노드를 방문하기 전에 해당 노드의 g값(G + H)이나 F값(총 예상 비용)이 최소인지 비교하여 최소 값을 가지는 경로만 선택하고 방문하게 됩니다. closed 리스트는 이러한 과정을 합리화하고 반복적인 계산을 피함으로써 알고리즘의 효율성을 높여줍니다.
궁금하신 부분을 더 명확히 이해하기 위해 A* 알고리즘 코드 질문입니다.라는 게시글을 참고해 보시면 이해하는 데 도움이 될 것입니다. 이 게시물에서도 방문 체크와 최단 경로의 맥락을 알기 쉽게 설명하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.