기초적인 방법론
이분 그래프(Bipartite graph)
다익스트라 최단경로(Dijkstra's algorithm)
이분 그래프(Bipartite graph)
운전자 - 고객으로 나누어 매칭 시킨 후 각각 최소인 운전자 - 고객인 값을 찾는 알고리즘
Linear sum assignment problem(LSAP)
- LSAP는 이분 그래프 상 cost를 고려하여 총 비용을 최소화하는 배차 조합을 도출한다.
- 위 이분 그래프로 4개의 매칭을 성립했을 때 그 조합의 합이 최솟값이 되도록 하는 것이다.
Dijkstra's algorithm 다익스트라 알고리즘
- 정의: 가장 짧은 경로를 찾는 알고리즘
- 특정 노드에서 다른 모든 노드로 가는 최단 경로를 DP, Greedy 알고리즘을 통해 계산한다.
- 과정
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 위 과정 3~4회 반복
- 표기법
s: source node(start node)
d(j): 출발 노드 s에서 j까지 최단 거리 길이
p(j): 출발 노드 s에서 j까지 최단 거리 경로 상에 위치한 j의 직전 노드
k: 마지막으로 선택된 노드
- 알고리즘
1단계: 초기화
d(s) = 0, p(s)=, d(j) = infinte, p(j) = - for all other nodees, k = s
2단계: 현재 k에서 직접 접근 가능한 인접 지점에 대해 업데이트 수행
k에서 j에 접근이 가능하면~ do:
3단계: 접근 가능한 노드 i를 탐색
4단계: 탐색 종료할 수 있는 노드 j 탐색
5단계: 노드 i에 대한 탐색 종료, 남은 접근 가능한 노드가 없으면 종료
Hi im 재환