minimize-apsp-sum

작성 수정

Minimize APSP Sum

  • 방향 그래프에서 모든 edge에서 edge 간의 거리를 최소화 하는 접근 방법
  • QUBO를 문제로 바꾸기 위해서 Heuristic하게 접근
    • 그림 1에서 보이듯 APSP와 n-hop 이웃의 수는 반비례 관계
    • 모든 edge에 2차 이웃(2-hop Neighbor)과 3차 이웃(3-hop Neighbor)의 수를 최대화 하는 문제로 바꿈

result_v15_Delaunay.png

result_v50_Delaunay.png

result_v100_Delaunay.png

그림 1. 각각 정점 15개($v=15$), 정점 50개($v=50$), 정점 100개($v=100$)인 평면 그래프에서의 APSP 구조 및 이웃 정점 간 관계

QUBO

제약 조건 없는 이진 변수 이차 최적화

Binary variable

binary variable: $e_{ij}$

$$ \text{Let } \forall i, j \in V \text{ such that } i < j: $$ $$ \text{Direction}(i, j) = \begin{cases} i \to j & \text{if } e_{ij} = 0 \newline j \to i & \text{if } e_{ij} = 1 \end{cases} $$

Objective Function

$$ \text{min } \sum_{\forall e_{ij} \in E} (-I_{i\rightarrow j} \cdot I_{j\rightarrow k}) + \sum_{\forall e_{ik}, e_{kj}}( - I_{i\rightarrow j} \cdot I_{j\rightarrow k} \cdot I_{k\rightarrow l}) $$ $$ I_{i\rightarrow j} = \begin{cases} 1-e_{ij} & \text{if } i < j \ e_{ij} & \text{if } i > j \end{cases} $$

  • $\sum_{\forall e_{ij} \in E} (-I_{i\rightarrow j} \cdot I_{j\rightarrow k})$
    • 모든 Edge의 2차 이웃의 수
  • $\sum_{\forall e_{ik}, e_{kj}}( - I_{i\rightarrow j} \cdot I_{j\rightarrow k} \cdot I_{k\rightarrow l})$
    • 모든 Edge의 2차 이웃의 수