closed list를 비교하는 부분이 궁금합니다.
138
投稿した質問数 4
24분 24초에 나오는 palyer.cpp, while문 안에 해당 코드에서
closed list는 방문 유무만 체크를 하는데 최소 거리를 찾는것과 무슨 관계가 있는지 모르겠습니다.
closed list에는 다른 경로와 값을 비교하는 부분(비용계산 하는부분)이 없는 것 같은데 어떻게 체크가 되는지 궁금합니다.
回答 1
0
안녕하세요, 인프런 AI 인턴입니다. dpe2233님.
질문하신 closed 리스트에 대한 부분은 A* 알고리즘이나 다익스트라 알고리즘에서 중요하게 사용됩니다. 이 리스트는 이미 처리된 노드나 포인트를 기록하여, 중복된 경로 계산을 피하기 위해 사용됩니다.
Closed 리스트의 역할
방문 여부 확인: 특정 노드를 방문했는지 여부를 빠르게 알기 위함입니다. 이미 처리된 노드라면 다시 연산할 필요가 없으므로, 연산을 줄이고 성능을 향상시킵니다.
최적 경로 보장: 알고리즘에서 최단 경로를 찾기 위해 여러 경로를 탐색합니다. 만약 여러 경로를 통해 같은 노드에 도달할 수 있는 경우가 생긴다면, 이미 방문한 노드는 현 상황에서 최단 경로로 도달한 것임을 의미합니다. 그렇기 때문에 고정할 수 있습니다.
비용 계산과의 관계
비용 계산 자체는 open 리스트(혹은 우선순위 큐)에서 이루어집니다. 특정 노드를 방문하기 전에 해당 노드의 g값(G + H)이나 F값(총 예상 비용)이 최소인지 비교하여 최소 값을 가지는 경로만 선택하고 방문하게 됩니다. closed 리스트는 이러한 과정을 합리화하고 반복적인 계산을 피함으로써 알고리즘의 효율성을 높여줍니다.
궁금하신 부분을 더 명확히 이해하기 위해 A* 알고리즘 코드 질문입니다.라는 게시글을 참고해 보시면 이해하는 데 도움이 될 것입니다. 이 게시물에서도 방문 체크와 최단 경로의 맥락을 알기 쉽게 설명하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
컴퓨터 구조에서 CPU에 대해 궁금한게 있습니다.
0
4
0
전공 필기 관련 질문
1
59
2
안녕하세요 큰돌님!
0
64
2
프로젝트 현실 때문에 차선의 기술 선택을 했던 경험, 이력서에 적어도 괜찮을까요?
1
98
2
경력관련 이력서 경험 분량 질문
1
72
2
지원동기에 대하여
1
65
2
프론트엔드 이력서 관련 질문
1
65
2
Replace함수 질문
0
117
2
A*, 다익스트라, Bfs차이 질문
0
211
2
부모가 2개 이상일경우 질문
0
207
2
sort함수 쓰려면 알고르즘헤더를 추가해야하는거 아닌가요?
0
218
2
빅오 표기법 2단계
0
356
1
list의 insert, erase에서 매개변수는 왜 iterator를 복사형으로 받나요?
0
317
1
Pop()함수에서 레퍼런스를 반환하지 않는 이유가 궁금합니다
0
432
3
iterator의 begin, end, insert, erase함수에서 iterator를 반환할 때 일어나는 현상이 궁금합니다
0
262
1
언리얼 part.4 는 안나오나요?
0
468
1
재귀함수 질문
0
493
1
클레스 템플릿 헤더파일 분리시 주의 사항이 있나요?
0
605
3
Pos operator< 어디서 사용하나요?
0
540
2
Disjoint Set 클래스 수정해도 괜찮나요?
0
486
1
A*알고리즘 작성과정에서 블록 안에서 초기화를 한 이유가 궁금합니다.
0
617
1
1강에서의 List와 자료구조편에서의 List의 차이가 뭘까요?
0
620
1
이진 탐색 트리 삭제 질문
0
741
1
해당 문제 유형을 수학적으로 표현 가능할까요?
0
537
1