안녕하세요. 에이스타와 bfs 관련 문의드립니다.
안녕하세요. 에이스타 까지의 강의를 공부하고 궁금한게 있어서 문의드립니다.
에이스타와 bfs는 어쨋든 하나의 정점에서 상하좌우 or 상하좌우-우상-우하-좌상-좌하
로 탐색을 하면서 가장 좋은 길을 선택하는 거잖아요.
근데 제가 저의 포폴에서 확인을 해보니 동일한 타겟 지점으로 에이스타와 bfs 이동을 해보면,
에이스타의 효율이 훨씬 좋더라고요. 오픈리스트 추가되는 갯수가 적습니다.
왜 이런 현상이 발생하는지 알 수 잇을까요?
回答 2
1
A*는 [시작지점]-[목표지점]을 각기 정해두고
휴리스틱이라는 느낌적인 느낌으로 좋을 것 같은 방향으로 먼저 서칭을 합니다.
BFS는 [시작지점]에서 가까운 순서대로 서칭을 하기 때문에,
설령 목표지점이 오른쪽에 있더라도 반대 방향을 먼저 서칭하는 경우가 생길 수 있습니다.
그래서 엄청 장애물이 많거나 하는 특수 상황이 아니면 A* 가 훨 좋은 것이죠.
BFS는 [목표지점]이라는 존재에 대해 아예 모른다는 것을 유의깊게 살펴보세요!
0
BFS는 '순회' 알고리즘이므로, 기본적으로 그래프 내의 연결된 모든 정점을 방문하려고 시도하는 알고리즘입니다.
따라서 그래프의 간선들의 가중치가 모두 같은 상황이 아닐 땐 최단거리를 구할 수 없다는 단점도 있습니다.
반면 A*는 분명한 목적지를 정해두고 시작지점과 도착지점간의 최단거리에만 관심이 있는 알고리즘이기 때문에 BFS와 다르게 동작합니다.
헤더파일에 관한 질문
0
442
1
이진 탐색 트리 삭제 질문
0
705
1
해당 문제 유형을 수학적으로 표현 가능할까요?
0
513
1
vs2022 미로 줄간격
0
1596
2
pos 구조체 초기화 문제
0
502
0
맵이 이상하게 나오는데 무슨 문제인가요?
0
520
1
자동완성 기능 질문
1
527
2
push_back emplace_back 질문있습니다.
0
404
1
Container, Predicate 질문입니다.
0
401
1
_size - 2 질문
0
422
1
Disjoint Set 질문있습니다
0
437
1
우선순위 큐 구현 연습 intellisense 질문
0
408
1
int32 관련 질문
0
282
1
c++에서 처음 보는 문법
0
389
1
학습에 크게 지장이 있는건 아니지만 단순 궁금해서 질문드립니다
0
328
1
힙 정렬과 병합 정렬
0
431
1
resize 질문
0
266
1
처음 보는 for문 문법
0
392
1
환경 설정.. 궁금점
0
394
1
이 비교 연산자를 넣어주는 이유가 있나요?
0
292
1
소멸자 관련 질문
0
256
1
&의 차이
0
295
1
프레임 관리 질문입니다.
0
338
1
연산자 오버로딩 관련 질문입니다.
1
210
1