Kruskal / Prim / Dijkstra 템 플 릿

이 세 가지 알고리즘 은 모든 알고리즘 책 에서 말 해 야 하 는데 이번에 을 보고 다시 한 번 복습 을 했 는데 새로운 깨 달 음 이 있다 고 생각 하여 템 플 릿 을 써 서 기록 해 보 세 요.
Kruskal 과 Prim 알고리즘 이 해결 하 는 문 제 는 최소 생 성 트 리 문제 입 니 다. 즉, 그림 G < V, E > 에 대해 최소 생 성 트 리 T < V, E > 를 찾 습 니 다. 그 중에서 E '는 E 에 포함 되 어 모든 V 를 연결 합 니 다.Dijkstra 알고리즘 은 단일 소스 다 중 가장 짧 은 경로 문 제 를 해결 합 니 다. 즉, 그림 G < V, E > 와 하나의 출발점 S 에 대해 그림 의 다른 모든 노드 에 S 에서 가장 가 까 운 경 로 를 찾 습 니 다.
그림 은 모두 가중 도 입 니 다. 균일 권 도 나 가중치 가 하나 인 그림 이 라면 최소 생 성 트 리 라 는 개념 은 존재 하지 않 습 니 다. 모든 생 성 트 리 의 크기 가 일치 하기 때 문 입 니 다.이른바 단원 멀 티 포인트 최 단 경로 도 BFS 로 풀 수 있다.
이 세 가지 알고리즘 의 본질은 모두 욕심 이 고 세 가지 문 제 는 모두 탐욕 선택 성 을 가지 기 때문에 욕심 알고리즘 을 사용 하면 가장 좋 은 결 과 를 얻 을 수 있다.
일단 Kruskal 알고리즘 을 살 펴 보 겠 습 니 다.먼저 알고리즘 을 설명 한 다음 에 최 우수 성 을 증명 하 다.
두 개의 사 이 드 집합 을 만 듭 니 다. 초기 에 Q 는 모든 변 의 집합 이 고 A 는 빈 집합 입 니 다. 알고리즘 이 끝 날 때 A 가 원 하 는 최소 생 성 트 리 입 니 다.Q 의 가중치 가 가장 작은 변 을 삭제 하고 고찰 할 때마다 A 에 가입 하면 순환 로 가 형성 되 지 않 으 면 A 에 가입 합 니 다. A 중 변 수 를 | V | - 1 에 맞 추 면 해 제 를 끝 냅 니 다.

Q=E

A=NULL

while(n<|V|-1)

      e=min(Q)

      Q=Q-e

      if(e  A       )

            A=A AND e

최소 생 성 트 리 에 포 함 된 변 수 는 | V | - 1 이라는 것 을 쉽게 알 수 있 습 니 다.그래서 최소 생 성 트 리 를 구 하 는 과정 은 | V | - 1 개의 변 을 선택 하 는 과정 입 니 다.문제 의 시작은 모든 노드 가 분 리 된 것 과 같 고 문제 의 결말 은 모든 노드 의 연결 을 요구한다.모든 변 의 가입 은 그림 의 연결 도 를 하나 더 해 야 합 니 다 (그렇지 않 으 면 순환 로 를 구성 하면 불필요 한 삭제 가능 한 변 이 생 깁 니 다).문 제 를 한 숲 과 잠재 적 인 변 에 대해 가중치 의 최소 변 을 넣 어 숲 의 연결 도 를 하나 더 해 야 한다. 즉, 숲 속 나무의 개 수 를 하나 줄 여야 한다.이런 문 제 는 탐욕 적 인 선택 성격 을 가진다. 매번 회로 가 되 지 않 는 가중치 가 가장 작은 변 을 선택해 야 하고 다음 탐욕 선택 은 한 가지 문제 만 야기 해 야 한다.또한 이 문 제 는 가장 좋 은 서브 구 조 를 가지 기 때문에 반드시 서브 문 제 를 포함 하 는 가장 좋 은 해 를 가장 잘 풀 수 있다. 그렇지 않 으 면 서브 문제 의 가장 좋 은 해 를 현재 서브 문제 의 해 를 대체 하여 전체 문제 의 더욱 좋 은 해 를 얻어 모순 을 도 출 할 수 있다.따라서 최소 생 성 트 리 문 제 를 욕심 스 러 운 전략의 Kruskal 알고리즘 으로 해결 하 는 것 이 옳다.
프 림 알고리즘 다시 봐.Kruskal 알고리즘 은 변 의 가중치 를 욕심 으로 고려 하고 매번 에 역할 을 할 수 있 는 가중치 가 가장 작은 변 을 넣 어서 가장 좋 은 해 를 얻 는 것 은 직관 적 인 사고 이다.다른 사고방식 은 문제 의 초기 단 계 를 모든 노드 가 독립 된 것 으로 간주 한 다음 에 연 결 된 집합 을 구축한다. 매번 탐 욕 스 러 운 전략 에 따라 이 집합 에 점 하 나 를 넣 으 면 모든 점 이 집합 안에 있 고 최소 생 성 트 리 의 구축 을 완성 한다.그렇다면 점 마다 어떤 값 을 부여 해 탐욕 선택 을 해 야 할 까?각 점 에 기 존 집합 과 의 거 리 를 부여 해 야 한다.
의사 코드 는 다음 과 같 습 니 다:

Q=V

A=NULL

while(|A|<|V|-1)

      v=Q  A       

      A=A AND v

        v   ，  Q     A   

Prim 알고리즘 은 풀이 과정 에서 중간 해 를 유지 하 는 것 은 나무 이 고 Kruskal 의 중간 해 는 숲 이다.문 제 를 한 그루 의 나무 와 한 조 의 산 노드 로 추상 화하 고 산 노드 중의 하 나 를 나무 에 넣 어서 나무의 노드 수 를 하나 늘 리 고 증가 하 는 가중치 가 가장 적다.이런 문 제 는 가장 좋 은 서브 구조 와 탐욕 선택 성격 을 가지 고 있다.모든 단계 에서 해결 한 서브 문제 의 최 적 화 는 반드시 전체 문제 의 최 적 화 된 해석 에 포함 되 고 반증 법 도 증명 할 수 있다.매번 탐 욕 스 러 운 선택 은 한 가지 문제 만 남는다.이렇게 해서 Prim 알고리즘 의 정확성 을 증명 했다.
Dijkstra 알고리즘 과 Prim 알고리즘 은 똑같다.또한 매번 한 그루 의 나무 (또는 서브 맵) 에 욕심 많은 전략 에 따라 노드 를 추가 하고 가입 한 후에 새로 가입 하 는 노드 에 영향 을 받 을 수 있 는 미 가입 노드 정 보 를 업데이트 하고 상기 과정 을 모든 노드 가 가입 할 때 까지 반복 합 니 다.욕심 이 생각 하 는 지표 가 다르다 는 차이 가 있다.최소 생 성 트 리 는 연결 을 요구 하기 때문에 구 축 된 부분 생 성 트 리 의 임 의 노드 와 의 거리 에서 가장 작은 거 리 를 욕심 으로 고려 해 야 합 니 다. 단원 다 점 의 가장 짧 은 경 로 는 모든 노드 와 특정한 원점 의 거 리 를 고려 해 야 합 니 다.따라서 탐욕 적 인 선택 을 할 때 도 가입 하지 않 은 모든 점 중에서 이 원점 과 가장 짧 은 거 리 를 가 진 노드 를 선택해 야 한다. 가입 한 후에 업데이트 할 정보 도 이것 이다. 업데이트 방법 은 기 존의 거리 와 갓 가입 한 노드 를 통 해 원점 에 도착 하 는 거리 가 어느 것 이 더 작은 지 고찰 하 는 것 이다.
의사 코드 는 다음 과 같 습 니 다:

Q=V

A=NULL

while(|A|<|V|-1)

      v=Q  s      

      A=A AND v

        v   ，  Q     A   

      for each x in Q

            dist[x]=min(dist[x],dist[v]+e(u,v))