k개의 경로를 구하는 간단한 알고리즘.jl로 실현

배경.

지난번 LightGraphis.jl 및 확장된 SimpleWeightedGraphisjl에 관한 일을 썼다.
https://zenn.dev/takilog/articles/3012e77e242666649369
여기 LightGraphis가 있습니다.jl의 조작에 익숙해졌기 때문에 예를 들면 Dijkstra법을 사용한다

g = # something graph
ds = dijkstra_shortest_paths(G, s)
distance = ds.dists[t]
path = enumerate_paths(ds)[t]

과 같은 형식은 단번에 이용할 수 있다는 것을 저는 깊이 기억했습니다(이 사용 방법에 관해서는 문서의 Paths and Traversal를 보십시오.
이 글에서 우리는 이러한 기본 기능을 사용하여 두 점 사이의 약간의 경로를 찾는 알고리즘을 실현하려고 시도한다. 가장 대표적인 것은 k-shortpath 문제blems(KSP)이다.어떤 k본을 선택하느냐에 따라 다양한 변화가 있다. 예를 들어 도쿄역에서 신주쿠역까지 갈 때 다양한 노선 중에서 자신이 좋아하는 지하철을 선택하기 위해 두 점 사이를 연결하는 몇 개의 노선을 준비했다.

Yen's k-shortest path problems

이것은 모두가 알고 있는 k조의 가장 짧은 경로를 찾는 알고리즘이다.jl에서 (상) 이루어졌다!문서 좀 볼게요.

yen_k_shortest_paths(g, source, target, distmx=weights(g), K=1; maxdist=Inf);

Perform Yen's algorithm on a graph, computing k-shortest distances between source and target other vertices. Return a YenState that contains distances and paths.
오, 쓸 수 있잖아!그렇게 생각하지만 유감스럽게도 버그가 있어서 사용할 수 없을 것 같습니다. (사용할 수 있는 경우도 있을 수 있지만, 이 버그를 확인했습니다. (2021/4 현재)
https://github.com/JuliaGraphs/LightGraphs.jl/issues/1505
어쩔 수 없다.스스로 다른 수법을 설치하다.

수법

여기에 두 가지 기법을 실시해 봤다. 예제의 도표는 이렇다. 기점 s=1과 종점 t=8을 사용하여 일반적인 가장 짧은 경로를 묘사한다. 변의 이동 비용은 평면상의 유클리드 거리를 직접 설정했다.

경로 벌칙

그렇다면 Yen's algorithm과 다른 KSP의 알고리즘도 진지하게 실시할 수 있지만, 이미 알려진 고전 KSP의 알고리즘은 비슷한 경로를 많이 포함하는 집합을 되돌려준다. 조금만 생각해 보면 가장 짧은 경로의 경로를 조금 바꾸면 상당히 짧은 비용을 초래할 수 있다는 것을 알 수 있다.이를 피하기 위해 우리는 진지하게 연구하고 있다. 여기서 우리는 간단한 실복을 만들어야 한다.
경로 P{s, t} 을 선택하면 이 P{s, t}에 이미 포함된 모서리 e\in P{s,t}에 관해서는 다른 해에 포함되지 않아도 될 것 같다(정말요?가능한 한 기존의 Dijkstra 방법을 이용하여 이를 실현하기 위해 e\in P{s,t}의 무게 wP e 를 통해{s,t}를 계산할 때마다 큰 폭으로 변할 수 있었으면 좋겠어요.
w(e)\to w(e)\times (1 + p)
변화를 주었으면 좋겠어요. 이걸 실시해 봅시다. 지난번에 사용했던 Simple Weighted Graphs의 가장자리 자체는 무게 정보가 있고 시원하지만 데이터 구조가immutable이어서 변경할 수 없습니다. 그래서,차트 G(일반 LightGraphis.jl의 차트)와 복원된 가중치 정보\{w e\}를 한 번 준비하고, 행렬의 동작 가중치는 Dijkstra를 참조하여 계산할 때 변화하는 가중치입니다. 계산된 수량은 K=5이고, 벌칙 배율은 p=0.5입니다.

s = 1
t = 8
p = 0.5
K = 5
dists = []
for k in 1:K
    # dmat情報でs-t最短経路を求める
    ds = dijkstra_shortest_paths(G, s, dmat)
    path_st = enumerate_paths(ds)[t]
    push!(paths, path_st)
    
    # ペナルティ
    for i in 1:length(path_st) - 1
        u, v = path_st[i], path_st[i + 1]
        nw = dmat[u, v] * (1 + p)
        dmat[u, v] = dmat[v, u] = nw
    end
end

아주 간단하게 (또는 아무것도 하지 않았다고) 설치했지만 시험 결과를 나타낸다.
1 (st)
2
3
4
5

차트 가중치 임의화

상기 방법에서 계산된 경로 P-{s,t} 위의 정보를 편집하여 이미 계산된 경로를 피하는 다음 경로를 찾습니다. 또한 다른 방법으로 도표의 가장 짧은 경로를 계산하면 도표의 정보를 무작위로 촬영하는 더욱 과감한 방법을 고려합니다. 전체적으로 변화가 발생하면Dijkstra를 사용하면 얻을 수 있는 경로도 달라질 수 있습니다. 당신의 이런 솔직한 마음은 어떤 변화가 일어날까요?가장 간단한 방법은 현재의 무게 w(e)를 평균으로 하는 정적 분포 정도의 떨림이 생기는 것이다(단 Dijkstra를 사용할 때 무게가 마이너스로 변하지 않도록 주의해야 한다).
특히, 가중치를 마이너스(이어서 0)로 바꾸지 않는 매개변수\tau>0 및 적절한 값\delta 사용
w(e)\to\max\left(\tau, w(e) +\mathcal{N}(0, w(e)^2\delta^2)\right)
기본적으로 똑같아요. 경로 벌금을 계산하는 곳에서.

for e in edges(G)
    nw = max(τ, e.weight + e.weight ^ 2 * delta ^ 2 * randn())
    dmat[e.src, e.dst] = dmat[e.dst, e.src] = nw
end

처럼 다시 쓰고 남은 처리와 경로벌칙법처럼 결과도 살펴봅시다.
1
2
3
4
5





육안으로는 차이를 거의 분간할 수 없지만, 라이트그래피스.jl의 기능을 충분히 발휘한 상태에서 가능한 한 여러 가지 경로를 간단하게 얻었다.

참조 정보

https://en.wikipedia.org/wiki/Yen's_algorithm

Eppstein's Algorithm(Fid the K shortpaths) 설명 및 구현(Pythn)

D. Cheng et al., Shortest-path diversification through network penalization: a washington dc area case study, Proc. of IWCTS 2019

my notebook