Python Algorithm Chapter4
Python Algorithm
그래프 문제
그래프는 문제를 추상적으로 만들어준다.
그래프: 연결된 노드의 집합노드: 정점에지: 노드 간의 연결
1. 지도와 그래프
미국의 대도시를 이어주는 하이퍼루프 문제를 해결해 보자
2. 그래프 프레임워크 구축
비가중치 클래스를 구현하여 가중치 클래스가 상속 받도록 구현한다.
제네릭을 사용하여 정점 타입 추상화한다.
여기서는 무향 그래프 즉, 양방향으로 이동가능한 에지를 구현한다. (reversed() 메소드 사용)
Graph 클래스
- 각 정점은 리스트에 저장되고, 인덱스로 이용하여 활용함
- 그래프 자료 구조 여기서는
정점 행렬말고인접 리스트사용 - 인접 리스트 : 모든 정점에는 그것이 연결된 모든 정점 리스트 존재
- 정점 행렬 : 행렬의 각 셀은 그래프 두정점의 교차점을 나타내며 연결됨과 안됨을 나타냄
3. 최단 경로 찾기
- 경로 : 두 정점을 연결하는 에지의 집합. 하나의 정점에서 다른 정점으로 이동하는 길 즉, 에지가 순차적으로 연결된 정점 리스트
3.1 너비 우선 탐색
가중치가 없는 그래프에서 최단 경로는 시작 지점과 목표 지점 사이에 에지가 가장 적은 경로다.
2장의 너비 우선 탐색 알고리즘을 사용한다.
4. 네트워크 구축 비용 최소화
미국의 하이퍼루트 네트워크를 최소한의 노선을 사용해서 어떻게 다 연결할 수 있을까?
4.1 가중치
에지가 나타내는 거리(두 도시 사이의 거리)를 가중치로 한다.
- WeightedEdge : Edge의 서브클래스 ( 대소 비교 연산자 구현 )
- WeightedGraph : Graph의 서브클래스
4.2 최소 신장 트리 찾기
트리: 두 정점 사이에 한 방향의 경로만 존재하는 그래프의 일종 -사이클없음 (비순환적)사이클: 그래프의 한 시작점에서 같은 에지 반복 없이 다시 같은 시작점으로 되돌아갈 수 있다.신장 트리: 그래프의 모든 정점을 연결하는 트리최소 신장 트리: 가중치 그래프의 모든 정점을 다른 신장 트리와 비교했을 때 최소 비용으로 연결한 트리
최소 신장 트리를 찾는 다는 것은 모든 정점에서 최소 가중치와 연결하는 방법을 찾는 것!
우선순위 큐 수정하기(프림 알고리즘에서 필요)
총 가중치 계산하기 : 모든 에지의 가중치를 합한 총 무게를 찾는 함수 정의
프림 알고리즘 : 최소 신장 트리를 찾는 방법
- 일단 그래프를 두 부분으로 나눈다. 최소신장트리에 포함된 정점과 아닌 정점
그리고 다음 단계를 따른다.
- 포함할 정점 선택
- 아직 포함 안된 정점 중 가장 낮은 가중치 에지 탐색
- 2단계에 선택된 에지에 연결된 정점 최소 신장 트리에 추가
- 모든 정점이 포함될 때까지 2, 3단계 반복
여기서 우선순위 큐가 사용됨(가중치가 낮은 에지가 우선순위가 높다)
5. 가중치 그래프에서 최단 경로 찾기
가중치 그래프의 어느 한 정점에서 모든 다른 정점까지의 최단 경로(총 에지 가중치의 합을 기준)는 얼마일까?
5.1 다익스트라 알고리즘
최단 경로 찾기 문제 해결한다.
과정
- 시작 정점을 우선순위 큐에 추가
- 우선순위 큐에서 가장 가까운 정점(현재 정점)을 팝한다.
- 현재 정점에 연결된 모든 이웃 확인. 아직 방문 안됬거나 에지가 최단 경로면 시작점에서 각 이웃 정점의 거리와 에지 기록 하고 해당 정점을 우선순위 큐에 추가
- 우선순위 큐가 빌 때까지 2,3단계 반복
- 시작점에서 다른 모든 정점까지의 최단 거리 반환
- 다익스트라 노드 : 현재까지 탐색된 각 정점과 해당 비용을 추적하고 이를 비교하기 위한 간단한 자료구조
다익스트라 알고리즘과 프림 알고리즘 둘다 탐욕 알고리즘이다.
A* 알고리즘은 의 다익스트라 알고리즘수정본이다.
다익스트라 알고리즘은 가중치가 양수인 그래프를 위한 설계이다. 음수인 경우 다른 알고리즘을 사용하거나 다익스트라 알고리즘을 수정해야한다.