- 분류 전체보기 (322)
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | ||||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 |
- 구조 패턴
- 14일 공부
- ssh
- 디자인 패턴
- Go-lang
- terraform
- 커머스
- github
- AWS 비용 절감
- study
- 청첩장 모임
- 논문 정리
- 실용주의 프로그래머
- Playwright
- leetcode
- Til
- amazon ecs
- 회고
- Rust
- docker
- PostgreSQL
- 오블완
- 지표
- 티스토리챌린지
- 경로 계획 알고리즘
- MAPF
- 신혼 여행
- DevOps
- AWS
- 생성 패턴
- Today
- Total
밤 늦게까지 여는 카페
Fully Dynamic Algorithms for Maintaining Shortest Paths Trees 리뷰 #1 - 논문을 읽게 된 이유 및 용어 정리 본문
Fully Dynamic Algorithms for Maintaining Shortest Paths Trees 리뷰 #1 - 논문을 읽게 된 이유 및 용어 정리
Jㅐ둥이 2025. 3. 25. 01:05안녕하세요. 벌써 겨울이 지나가고 봄이 오고 있습니다.
작년에 시작했던 Anytime Lifelong Multi-Agent Pathfinding in Topological Maps 논문 공부가 아직도 안 끝났는데
그 사이에 새로운 논문을 또 보고 있습니다...
일을 시작하는 것도 중요하지만 마무리하는 것도 중요하기에 일을 너무 벌리기만 하는 것이 아닌가 우려도 되지만
그래도 정리해보겠습니다!
FRIGIONI, Daniele; MARCHETTI-SPACCAMELA, Alberto; NANNI, Umberto. Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms, 2000, 34.2: 251-281.
1. 이 논문을 읽게 된 이유
작업 배정은 모든 노드에서 모든 노드까지의 최적 경로에 대한 최소 비용을 저장하고 있는 distance table을 이용해서 실행 속도를 향상시킬 수 있습니다.
모든 노드에서 모든 노드까지의 최적 경로를 구하는 가장 간단한 방법은 floyd warshall 알고리즘을 이용하는 것이고 이는 O(N^3)의 시간복잡도를 가지고 있습니다.
노드, 엣지가 삭제되거나 엣지의 weight이 변경되면 최적 경로가 바뀌므로 floyd warshall 알고리즘을 다시 실행해야 하는데 그래프가 클수록 시간이 오래 소요됩니다.
- 노드, 엣지 수가 많아지면 수십초까지 걸릴 수 있습니다.
평소라면 'agent가 움직이지 않는 것을 확신할 수 있을 때만 노드, 엣지를 삭제하면 되지!'하고 넘겼을 것입니다.
하지만 agent가 몰려 있는 상황을 엣지 weight의 변경으로 해소하고 싶다면 어떨까요?
방법을 고민하던 와중에 Perplexity AI의 도움을 받아서 해당 논문을 읽게 되었습니다.
그리고 Abstract를 읽자마자 이거다 싶더라고요!
- 제가 원하는 것은 모든 노드에서 모든 노드로의 최단 경로지만 O(V)만큼 반복하면 되니깐요!
2. 논문을 읽기 전 기본적인 개념 정리
논문을 읽으면서 느꼈던 점은 굉장히 어렵다는 것이었습니다.
특히 처음 보는 용어들이 너무 많았는데 한번 정리하고 가겠습니다.
2.1. Dynamic version of Single Agent Path Finding(SAPF)
graph가 변하는 상황에서 최단 경로를 구하는 문제를 dynamic SAPF problem이라고 합니다.
만약 graph가 변하는 연산이 엣지와 노드의 추가 삭제, 엣지의 weight 변경 모두 포함한다면 fully dynamic problem 이고
엣지의 추가(삭제)만 고려한다면 incremental(decremental) dynamic problem이라고 합니다.
2.2. output information
논문에서 말하는 output information은 다음 값들로 구성되어 있습니다.
- 최단 거리값: 시작 노드 s에서 다른 노드 x까지의 거리값
- 최단 경로 트리: 시작 노드 s가 root이고 각 leaf까지의 노드들이 최단 경로를 의미하는 트리
2.3. d(x), d'(x) - 최단 경로 비용 함수
d(x)는 시작 노드 s에서 노드 x로의 최단 경로의 비용을 알려주는 함수입니다.
d'(x)는 graph 수정 연산이 실행된 후의 시작 노드 s에서 노드 x로의 최단 경로 비용을 알려주는 함수입니다.
2.4. T(s), T(x) - 최단 경로 트리 함수
T는 파라미터로 전달된 노드를 root르 가지는 최단 경로 트리를 반환하는 함수입니다.
만약 시작 노드인 s를 전달한다면 전체 최단 경로 트리가 반환되고,
시작 노드 s가 아닌 다른 노드 x를 전달한다면 전체 최단 경로 트리 중 노드 x를 root르 가지는 부분 트리만 반환됩니다.
2.5. parent(x)=P(x), children(x)
parent(x)(P(x))와 children(x)은 전체 최단 경로 트리에서 x의 parent 노드와 children 노드들을 반환하는 함수입니다.
2.6. A(x, y) - 엣지를 소유하고 있는 노드를 반환하는 함수
Accounting Function A(x, y)는 엣지(x, y)를 소유하고 있는 노드 x 혹은 y를 반환합니다.
만약 모든 노드들이 k개 이하의 엣지를 소유하고 있다면 A를 k-bounded라고 합니다.
2.7. owner(x, y), ownership(x)
owner(x, y)는 A(x, y)와 동일하게 엣지 (x, y)를 소유하고 있는 노드를 반환합니다.
ownership(x)는 노드 x가 소유하고 있는 엣지들을 반환합니다.
논문에서 알고리즘 부분을 보면 노드가 소유하고 있는 엣지들에 대해서 최단 경로가 바뀌었는지 확인하는 로직이 있습니다.
그런데 어떤 노드가 어떤 엣지들을 소유하는지는 명확히 설명되어 있지 않습니다.
아마도 인용된 논문 [23]C. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 를 읽어야 알 수 있을 것 같습니다.
2.8. backward level, forward level, B_x, F_x
x에 대한 엣지 (x, y)의 backward level은 d(y) - w(x, y)입니다. b_level_x(y)라고도 표현합니다.
- x에 대한 엣지 (x, y)의 forward level은 d(y) + w(x, y)입니다. f_level_x(y)라고도 표현합니다.
B_x는 x에서 시작하는 엣지들을 backward level 내림차순으로 정렬한 큐입니다.
- F_x는 x에서 시작하는 엣지들을 forward level 오름차순으로 정렬한 큐입니다.
backward level 값이 크다면 엣지의 weight이 줄어들었을 때 최단 경로가 바뀔 확률이 높으므로 먼저 확인해봐야 할 것입니다.
반대로 forward level 값이 작다면 엣지의 weight이 증가했을 때 최단 경로가 바뀔 확률이 높으므로 먼저 확인해봐야 할 것입니다.
용어만 이해하고 정리하는데 시간이 한참 걸렸습니다... ㅜㅠ
다음에는 edge weight 업데이트 알고리즘을 정리해보겠습니다!
