BQNの始め方 -- How to start BQN in Japanese

9.4 最短経路探索問題

Dijkstraのアルゴリズムやその改良版である\(A^{*}\)アルゴリズムはヒープが必要であり、道具立てが大変なので、 APL界隈ではBellman-Fordアルゴリズムが好まれるようだ。 Advent of Codeに限れば、毎年のように最短経路探索問題に帰着する問題は出ているものの、これまで負の重みが与えられたことはないので、非負の重みのみに簡単化した Bellman-Fordのアルゴリズムを実装すればよい。 この場合、アルゴリズムは辺を追加しながら全てのノード対に対する総コスト表を繰り返し更新するという極めて見通しのよいものになる。

ここで、始点終点対\((a, b)\)が点\(c\)を経由する際のコストの最小値は

  {𝕊 a‿b : ⌊´{𝕊 c : (a‿c⊑w)+(c‿b⊑w)}¨nodes}

と表せるが、これを従来の記法で書けば \[ \min_{i} w(a,c_i) + w(c_i, b) \] であり、行列積\(W \times W\) \[ \Sigma_{i} w(a,c_i) \times w(c_i, b) \] との類似が見て取れる¹。 従ってBQNcrateにある配列積のコードm +˝∘×⎉1‿∞ nを利用して以下のようになる。

    # 以下はwikipediaでのDijkstraアルゴリズムの項で使われている問題例
    edges ← [
      ⟨0,1,7⟩,⟨0,2,9⟩,⟨0,5,14⟩
      ⟨1,2,10⟩,⟨1,3,15⟩
      ⟨2,3,11⟩,⟨2,5,2⟩,⟨2,5,14⟩
      ⟨3,4,6⟩
      ⟨4,5,9⟩
    ]
    d ← ([0,∞]⊸(⊑˜)∘¬=)⌜˜↕ n ← 1+0(1⊸⊑⊸⌈)˝edges
    •Show d ↩ d {i‿j‿w 𝕊 𝕩 : w˙⌾(j‿i⊸⊑)w˙⌾(i‿j⊸⊑)𝕩}˝edges

    SmallestCost ← (⌊˝∘+⎉1‿∞)˜
    •Show SmallestCost⍟(⌈2⋆⁼n)d    # 再帰的に経路を追加するので log n 回で不動点

→ Try it online⌨️

ただし、これではコストのみしかわからない。 実際の経路も必要なら以下のようになる(これは少し苦労した)。

    Shortest ← {𝕊 m‿p :
      q ← (m⋈¨p)⋈¨∾¨˝⍉m(+⎉1‿∞)m
      ⟨(⌊´1⊸⊑)¨q,{(1⊑⊑𝕩)>⌊´1⊑𝕩 ? ⊑⍋1⊑𝕩 ; 1⊑⊑𝕩}¨q⟩
    }
    route ← 1+1⊑Shortest⍟(⌈⋆⁼2)d‿(∞¨d)
    # startからendに行くには以下が最小コスト列
    Traverse ← {r T start‿end :
      m ← ((-¬)¨start‿end)⊑r    # 次に選ぶべきノード
      {⊑m∊⟨start,end⟩ ?         # 始点または終点なら直接遷移可能
        ⟨start,end⟩
       ;
        (r T start‿m)∾1↓(r T m‿end)
      }
    }

→ Try it online⌨️