그래프에서 정점을 검색하는 가장 좋고 쉬운 알고리즘?

https://stackoverflow.com/questions/2471755

20-09-2019
|

문제

그래프 구현에 대부분의 공통 및 필요한 기능을 구현 한 후 몇 가지 기능 (정점 제거, 검색 정점 및 vertex get vertex)에 "최상의"구현이 없다는 것을 깨달았습니다.

그래프 구현에 링크 된 목록이있는 인접력 목록을 사용하고 있으며 원하는 것을 찾을 때까지 다른 정점을 검색했습니다. 내가 말했듯이, 나는 "최고의"구현을 사용하고 있지 않다는 것을 깨달았습니다. 나는 10000 개의 정점을 가질 수 있고 마지막 정점을 검색해야하지만, 그 정점은 첫 번째 정점에 대한 링크를 가질 수 있으므로 상당히 속도를 높일 수 있습니다. 그러나 그것은 단지 가상의 경우 일뿐입니다.

그렇다면 검색 조회에 어떤 알고리즘을 권장합니까? 우리 교사들은 너비 우선과 깊이 우선에 대해 주로 이야기했지만 (그리고 Dikjstra '알고리즘이지만, 그것은 완전히 다른 주제입니다). 그 두 사람 사이에서 어떤 것을 추천합니까?

둘 다 구현할 수 있다면 완벽 할 것입니다.하지만 시간이 없어야합니다. 하나를 집어 들고 구현해야합니다. 첫 번째 위상 마감일이 다가오고 있습니다 ...

내 추측은 깊이 우선으로 가고, 구현하기가 더 쉬워지고 그들이 작동하는 방식을 보는 것 같아서 가장 좋은 방법 인 것 같습니다. 그러나 그것은 실제로 입력에 달려 있습니다.

하지만 너희들은 무엇을 제안합니까?

해결책

인접력 목록이있는 경우 정점을 검색하면 단순히 해당 목록을 가로 지르는 것을 의미합니다. 필요한 조회 작업을 줄이기 위해 목록을 주문할 수도 있습니다.

그래프 트래버스 (예 : DFS 또는 BFS)는 성능 관점에서이를 향상시킬 수 없습니다.

다른 팁

그래프에서 노드 찾기 및 삭제는 그래프 문제가 아닌 "검색"문제이므로 O (n) = 선형 검색, BFS, DFS보다 더 나은 문제를 해결하려면 검색에 최적화 된 다른 데이터 구조에 노드를 저장해야합니다. 또는 정렬하십시오. 이것은 찾기 및 삭제 작업을위한 O (log n)를 제공합니다. 칸디다타는 B- 트리 또는 해시 테이블과 같은 나무 구조입니다. 당신이 물건을 직접 코딩하고 싶다면 나는 일반적으로 매우 우수한 성능을 제공하고 구현하기 쉽습니다.

BFS는 일반적으로 평균이 빠를 것이라고 생각합니다. 위키 페이지를 읽으십시오 DFS 그리고 BFS.

내가 BFS가 더 빠르다고 말하는 이유는 시작 노드와 거리를두고 노드에 도달하는 속성이 있기 때문입니다. 그래 그래프가 있다면 N 노드와 노드를 검색하려고합니다 N 그리고 노드 1, 검색 양식을 시작하는 노드는 다음과 같습니다. N, 그러면 즉시 찾을 수 있습니다. 그러나 DFS는 이런 일이 발생하기 전에 전체 그래프를 확장 할 수 있습니다. 운이 좋으면 DFS가 더 빠르며 검색하는 노드가 시작 노드에 가깝면 BFS가 더 빠릅니다. 요컨대, 그들은 둘 다 입력에 의존하지만 BFS를 선택합니다.

DFS는 재귀없이 코딩하기가 더 어렵 기 때문에 BFS는 반복 알고리즘이기 때문에 실제로 BFS를 조금 더 빠르게 만듭니다.

노드를 정규화 할 수 있다면 (1에서 10,000까지 번호로 액세스 할 수 있다면) 쉽게 보관할 수 있습니다. Exists[i] = true if node i is in the graph and false otherwise, O (1) 조회 시간 제공. 그렇지 않으면 a를 사용하는 것을 고려하십시오 해시 테이블 정규화가 불가능하거나하고 싶지 않은 경우.

깊이 우선 검색이 가장 좋습니다

기억이 훨씬 적습니다
더 쉽게 구현할 수 있습니다

깊이의 첫 번째 및 너비 첫 번째 알고리즘은 하나 (DFS), 다른 하나의 대기열 (BFS) 및 몇 가지 필요한 멤버 변수를 사용하는 것을 제외하고는 거의 동일합니다. 둘 다 구현해도 시간이 많이 걸리지 않아야합니다.

또한 정점의 인접성 목록이있는 경우 O (v)를 찾아보십시오. 다른 두 검색 중 하나를 사용하여 얻을 수는 없습니다.

Konrad의 게시물에 대해 언급하지만 아직 언급 할 수는 없습니다 ... 목록을 통해 간단한 선형 검색을 통해 DFS 또는 BFS를 구현하면 성능에 차이가 없다는 두 번째로 말하고 싶습니다. 그래프에서 특정 노드에 대한 검색은 그래프의 구조에 의존하지 않으므로 알고리즘 그래프로 제한 할 필요는 없습니다. 코딩 시간 측면에서 선형 검색이 최선의 선택입니다. 그래프 알고리즘에서 기술을 닦으려면 DFS 또는 BFS를 구현하십시오.

특정 정점을 검색하고 찾을 때 종료하는 경우 사용하는 것이 좋습니다. ㅏ*, 이는 가장 좋은 검색입니다.

아이디어는 소스 정점에서 처리중인 현재 정점까지의 거리를 계산 한 다음 현재 정점에서 대상까지의 거리를 "추측"한다는 것입니다.

소스에서 시작하여 거리 (0)와 추측 (무엇이든지)를 계산하고 우선 순위가 거리 + 추측 인 우선 순위 대기열에 추가합니다. 각 단계에서 가장 작은 거리 + 추측으로 요소를 제거하고 인접성 목록에서 각 정점에 대한 계산을 수행하고 우선 순위 대기열에 고착하십시오. 대상 정점을 찾으면 중지하십시오.

당신의 휴리스틱 (당신의 "추측")이 허용되는 경우, 즉 언제나 과소 평가 한 경우, 처음 방문 할 때 대상 정점에 가장 짧은 경로를 찾을 수 있습니다. 휴리스틱이 허용되지 않는 경우, 가장 짧은 경로를 찾기 위해 완료하기 위해 알고리즘을 실행해야합니다 (가장 짧은 경로에 관심이 없지만 경로 만있는 것처럼 들리지만).

폭이 먼저 검색하는 것보다 구현하기가 더 어렵지는 않지만 (실제로 휴리스틱을 추가하면됩니다) 더 빠른 결과를 얻을 수 있습니다. 유일한 어려운 부분은 휴리스틱을 파악하는 것입니다. 지리적 위치를 나타내는 정점의 경우, 일반적인 휴리스틱은 "크로우 플라이"(직접 거리) 휴리스틱을 사용하는 것입니다.

선형 검색은 BFS 및 DFS보다 빠릅니다. 그러나 선형 검색보다 빠르게 단계 비용이 0으로 설정된 경우*입니다. 단계 비용이 0 인 경우 A*는 골 노드에 가장 가까운 노드 만 확장합니다. 단계 비용이 0 인 경우 모든 노드의 경로 비용은 0이고 A*는 더 짧은 경로로 노드를 우선 순위로 삼지 않습니다. 가장 짧은 경로가 필요하지 않기 때문에 원하는 것입니다.

a*는 선형 검색이 O (N/2) 반복 후에 완료 될 가능성이 높기 때문에 (각 노드는 목표 노드가 될 가능성이 동일)이지만* 골 노드가 될 가능성이 높은 노드를 우선시하기 때문에 선형 검색보다 빠릅니다. .

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow