폭이 넓은 첫 번째 검색에 유용한 것은 무엇입니까?
https://stackoverflow.com/questions/1657174
-
11-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
일반적으로 그래프를 걸어야 할 때, 나는 공간 복잡성이 낮기 때문에 항상 깊이 우선 검색을 사용했습니다. 나는 내 경험이 있지만 폭이 넓은 검색을 요구하는 상황을 정직하게 본 적이 없다. ~이다 꽤 제한적입니다.
폭이 큰 검색을 사용하는 것이 언제 의미가 있습니까?
업데이트: 내 대답이 있다고 생각합니다 여기 BFS를 사용한 상황을 보여줍니다 (DFS라고 생각했기 때문에). 그래도이 경우에도 여전히 유용한 이유가 궁금합니다.
해결책
가능한 한 적은 모서리를 횡단하여 노드에 도달하려면, 즉 비가 중 그래프에서 가장 짧은 경로를 찾으려면.
또한 깊이의 공간 복잡성은 첫 번째 검색의 공간 복잡성을 폭 넓은 첫 번째 검색보다 높을 수 있습니다. 예를 들어 각 노드에 하위 노드가 하나만있을 때, 즉 그래프가 깊지 만 넓지는 않을 때.
다른 팁
검색 도메인이 무한한 경우, 유한 솔루션이 존재하더라도 깊이 우선 검색은 솔루션을 종료/찾는 것을 보장하지 않습니다.
또한 a*와 같은 더 정교한 알고리즘이 너비 우선 검색의 특수 하위 유형이라는 것을 볼 수 있습니다.
일반적으로 BFS는 최적이며 완전한 (유한 분지 계수)이며 DFS는 그렇지 않습니다.
최소 수의 단계로 검색 문제를 해결하는 데 사용할 수 있습니다. 깊이로 가면 먼저 (어쨌든 제한되지 않는 경우) 무한 깊이로 이어질 수 있습니다.
예 : 조건을 만족시키는 루트에서 가장 가까운 노드를 찾습니다.
폭이 먼저 검색이 유용한 경우의 핵심 요소를 아직 언급 한 사람은 없습니다. 한 가지 방법으로 노드를 방문하면 다른 방법으로 노드를 방문해야 할 요구 사항을 제거 할 수 있습니다. 경우에 따라 노드가 방문한 순서에 관계없이 동일한 작업을 수행하지만 BFS는 DFS보다 한 번에 계류중인 조치가 훨씬 적습니다. 다른 경우, 한 순서로 노드를 방문하는 경우 다른 순서보다 더 많은 작업이 필요할 수 있습니다. 그 예로서 다양한 가장 짧은 경로 알고리즘이 제공됩니다. 노드를 방문하면 현재 노드보다 짧은 경로로 노드가 도달 할 수있는 것으로 알려져 있지 않으면 폭이 넓은 순서의 노드를 방문하면 일반적으로 노드가 가장 짧은 경로를 할당하거나 그와 가까운 것입니다. -첫 방문. 대조적으로, 깊이 우선 검색은 처음으로 매우 긴 경로로 많은 노드를 방문하게 한 다음 약간 더 짧은 경로, 약간 더 짧은 경로 등을 초래할 수 있습니다.
BTW, 깊이 우선과 폭이 먼저 알고리즘의 차이에 대한 멋진 그래픽 그림 중 하나는 홍수 채우기로, 흰색 노드가 검은 색으로 칠하고 이웃을 홍수로 채색하여 홍수로 채워집니다. 옥수수에서 시작하여 NXN 사각형 영역을 홍수로 채우려고한다면, 깊이 우선 조작은 나선형 또는 지그재그 시퀀스의 사각형을 채우고 NXN-1 작업이 스택에 남아 있습니다. 폭이 넓은 충전물은 출발점에서 "쏟아 질"하며, 채워질 모양에 관계없이 최대 o (n) 작업이 보류 중입니다. BTW, IBM BASICA의 홍수 채우기는 그런 식으로 일했습니다 (QBASIC에 대해서는 잘 모르겠습니다).
한 가지 예는 파일 시스템을 가로 지르는 것입니다 (재귀 깊이 제한된 깊이).
에 따르면 위키 백과, 특정 그래프 알고리즘 (양파, 연결된 구성 요소)에도 유용합니다.
폭이 큰 검색을 사용하는 것이 언제 의미가 있습니까?
예를 들어, 그래프에서 가장 짧은 경로를 찾아야 할 때 DFS는 그렇게 할 수 없습니다. 다른 응용 프로그램이 있지만 일반적으로 DFS와 BFS는 다른 데이터 구조에서 작업하는 동일한 알고리즘입니다 (BFS는 큐를 사용하고 DFS가 스택과 함께 작동 함).
가장자리 무게가없는 그래프에서 정점으로 가장 짧은 경로를 가져와야 할 때.
깊이있는 첫 번째 검색에서 "로컬"솔루션을 찾을 수 있습니다. 전체 그래프를 가로 지르거나 휴리스틱을 사용해야하는 글로벌 솔루션을 실제로 찾을 수 있습니다.
BFS는 때때로 정말 유용합니다. WBS라고 말하자 나무가 있다고 가정 해 봅시다. 사용자에게 1 레벨 만 제시 할 수 있습니다.
폭이 먼저 검색 알고리즘은 시작점에 최대한 가깝게 유지하는 것을 좋아합니다. 내가 생각할 수있는 상황 중 일부는 다음과 같습니다.
- 소셜 네트워킹 웹 사이트는 지정된 거리에서 사람들을 찾는 데 사용할 수 있습니다.
- 이웃 컴퓨터를 찾기 위해 급류/피어 투 피어 네트워크에 유용 할 수 있습니다.
- GPS 내비게이션 시스템은이를 사용하여 인근 위치를 찾을 수 있습니다.
