closed list를 비교하는 부분이 궁금합니다.
119
投稿した質問数 4
24분 24초에 나오는 palyer.cpp, while문 안에 해당 코드에서
closed list는 방문 유무만 체크를 하는데 최소 거리를 찾는것과 무슨 관계가 있는지 모르겠습니다.
closed list에는 다른 경로와 값을 비교하는 부분(비용계산 하는부분)이 없는 것 같은데 어떻게 체크가 되는지 궁금합니다.
回答 1
0
안녕하세요, 인프런 AI 인턴입니다. dpe2233님.
질문하신 closed 리스트에 대한 부분은 A* 알고리즘이나 다익스트라 알고리즘에서 중요하게 사용됩니다. 이 리스트는 이미 처리된 노드나 포인트를 기록하여, 중복된 경로 계산을 피하기 위해 사용됩니다.
Closed 리스트의 역할
방문 여부 확인: 특정 노드를 방문했는지 여부를 빠르게 알기 위함입니다. 이미 처리된 노드라면 다시 연산할 필요가 없으므로, 연산을 줄이고 성능을 향상시킵니다.
최적 경로 보장: 알고리즘에서 최단 경로를 찾기 위해 여러 경로를 탐색합니다. 만약 여러 경로를 통해 같은 노드에 도달할 수 있는 경우가 생긴다면, 이미 방문한 노드는 현 상황에서 최단 경로로 도달한 것임을 의미합니다. 그렇기 때문에 고정할 수 있습니다.
비용 계산과의 관계
비용 계산 자체는 open 리스트(혹은 우선순위 큐)에서 이루어집니다. 특정 노드를 방문하기 전에 해당 노드의 g값(G + H)이나 F값(총 예상 비용)이 최소인지 비교하여 최소 값을 가지는 경로만 선택하고 방문하게 됩니다. closed 리스트는 이러한 과정을 합리화하고 반복적인 계산을 피함으로써 알고리즘의 효율성을 높여줍니다.
궁금하신 부분을 더 명확히 이해하기 위해 A* 알고리즘 코드 질문입니다.라는 게시글을 참고해 보시면 이해하는 데 도움이 될 것입니다. 이 게시물에서도 방문 체크와 최단 경로의 맥락을 알기 쉽게 설명하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
회사의 시스템 아키텍처를 포트폴리오에 써도 되나요?
1
38
2
REST API (Self-descriptive messages)
0
22
1
네트워크 전체 흐름 복습 질문
0
29
2
프로필 사진 세팅과 관련하여 질문 드립니다
1
47
2
시스템 엔지니어 관련 질문입니다.
0
50
2
구글 폼 작성 완료!
1
40
1
개발과 연관없는 경력 기입 여부
1
102
2
Replace함수 질문
0
83
2
A*, 다익스트라, Bfs차이 질문
0
172
2
부모가 2개 이상일경우 질문
0
172
2
sort함수 쓰려면 알고르즘헤더를 추가해야하는거 아닌가요?
0
187
2
빅오 표기법 2단계
0
329
1
list의 insert, erase에서 매개변수는 왜 iterator를 복사형으로 받나요?
0
290
1
Pop()함수에서 레퍼런스를 반환하지 않는 이유가 궁금합니다
0
386
3
iterator의 begin, end, insert, erase함수에서 iterator를 반환할 때 일어나는 현상이 궁금합니다
0
228
1
언리얼 part.4 는 안나오나요?
0
448
1
재귀함수 질문
0
464
1
클레스 템플릿 헤더파일 분리시 주의 사항이 있나요?
0
563
3
Pos operator< 어디서 사용하나요?
0
519
2
Disjoint Set 클래스 수정해도 괜찮나요?
0
470
1
A*알고리즘 작성과정에서 블록 안에서 초기화를 한 이유가 궁금합니다.
0
594
1
1강에서의 List와 자료구조편에서의 List의 차이가 뭘까요?
0
599
1
이진 탐색 트리 삭제 질문
0
701
1
해당 문제 유형을 수학적으로 표현 가능할까요?
0
507
1