（できたら）配列指向で経路探索問題を

Advent of Code y2022 day19のBQN解法に大変苦労した（している）のでちょこっとメモしておこう。

基本的には最短経路問題なのでRust版だとこんな感じ。

let mut to_visit: BinaryHeap;
let mut visited: HashSet;

while let Some(state) = to_visit.pop() {
  for next in state.expand() {
    if !visited.contains(&next) {
      visited.insert(&next);
      to_visit.insert(&next);
    }
  }
}

これを基にBQN版を作っていったのだがとても遅くて解けるとは言えなかったのでさらに知恵を絞ることになった。 ちなみにdzaima版は実行してない。

1. 時間を単位とする遷移からロボット追加を単位とする遷移へ

これはRust版でも実装済み。状態空間を縮小するため、何もしないで資源が増えるだけの次クロック状態を保持するのではなく、ロボットの増加させた後の状態への遷移で次状態を定義しよう。

2. 必要以上にロボットを溜め込む必要はない

clayロボットだけを作り続ける遷移は意味がない。他のロボットも作らねば。 ということで必要以上にロボットを溜め込むような次状態は探索対象に追加しないようにした。 これで状態数が有限に抑えられ、時間計算量も空間計算量も削減できる。

3. N台のロボットの状態からN+1台のロボットの状態に遷移したあとではN台のロボットの状態を記憶しておく必要はない。

ロボット数の増加が状態遷移をもたらすなら、ロボット数Nの状態からなる集合をそれぞれ展開（探索）してできる状態集合は（全ての）ロボット数N+1の状態なので探索済みかどうかはその集合内要素が重複していないことの判定に帰着する。 N未満のロボット数の状態を記憶しておく必要はない。Life gameのように2つのbagを切り替えながら展開していけばよい。

4. 状態の枝刈

さらに状態が完全に順序付け可能なら枝刈ができる。つまり

• 時刻が早い
• 資源（鉱石量）が多い
• ロボットが多い

ならば、小さな方の状態を展開対象に追加する必要はない。

Rust版では完全一致だけしか見ていなかったのでより良い枝刈ができる。多分$O(N)$の総当たりな実装でも見合うはず。

5. 深さ1のリスト化

性能に寄与するのかしないのかわからないのだが、状態の表現をネストをやめてフラットなベクターにしてみた。

time‿⟨nore‿nclay‿nobsidian‿ngeode⟩‿⟨rore‿rclay‿robsidian‿rgeode⟩

がこうなった。

time‿nore‿nclay‿nobsidian‿ngeode‿rore‿rclay‿robsidian‿rgeode

6. 時間方向を逆転することによる状態の半順序関係定義の簡略化

状態の順序関係の定義は時刻だけが不等号の向きが逆で残念なことになっているので、統一しよう。 そのため、時刻は0から始まり¯∞に向かって進むことにすると時刻が早いとは値が大きいことを意味するので、

{(𝕨(>○⊑)𝕩)∧(𝕨((∧´<)○(1↓))𝕩)}

はこうなる：

(∧´<)

golf!

7-X. 既に状態集合に登録された状態の枝刈

新しい状態を登録するかどうかを既に登録されている次状態との順序関係に基づき判定することが有効なら、 逆に登録済みの状態の削除も有効なはずなんだが速度が2倍ほど低下してしまった。 計算コストの問題だろうか。

7. 状態集合の整列

一方、Nロボットの状態からの遷移先を全て求めた後で、N+1状態の展開を始める前に状態集合をソートしてやるとなぜか実行時間が半分ほどになった。 ソートは昇順でなければならず、降順だと1時間経っても終わらなかった。 ただし´でfoldしているので実際には降順、つまり終了時刻に近い方から展開しているので、 深さ優先探索になったようだ。

ここまでで脳みそ切れ。頑張ったのだがpart2は10分掛かる。

追記

syntax highlighterのどれかがBQNに対応したという話を見たのでちょっと貼り付けてみよう。

こちらはapl:

  Examine ← { u 𝕊 n:
    best‿bp‿upto ← ⟨0,n⊏data,-u⟩
    masks‿limits ← ⟨0<˘bp,0‿0‿0‿∞⌈⌈´˘⍉bp⟩
    Expand ← {
      𝕊 ⟨⟩: best;
      𝕊 cands:
        𝕊 ∧ ⟨⟩ { time‿resources‿robots 𝕊 next:
          { 𝕊 i:
            upto< t ← time- w ← 1+⌈⌈´(i⊏masks)/robots÷˜(n ← i⊏bp)(0⊸⌈-)resources ?
              { ¬∨´(∧´𝕩⊸≤)¨next ? next ⟨𝕩⟩⊸∾ ↩, best ((4⊑𝕩)+(t-upto)ׯ1⊑𝕩)⊸⌈ ↩ ;@
              } t∾(n-˜resources+w×robots)∾((1⊸+)⌾(i⊸⊑)robots)
            ;@
          }¨{robots<○(𝕩⊸⊑)limits }¨⊸/↕4
          next
        }´{⟨⊑𝕩,4↑1↓𝕩,5↓𝕩⟩}¨cands
    }
    (•Fmt n) lib.Debug Expand ⟨⟨0⟩∾⟨0,0,0,0⟩∾⟨1,0,0,0⟩⟩ # ⟨time,resources,robots⟩
  }

こちらはbqn:

  Examine ← { u 𝕊 n:
    best‿bp‿upto ← ⟨0,n⊏data,-u⟩
    masks‿limits ← ⟨0<˘bp,0‿0‿0‿∞⌈⌈´˘⍉bp⟩
    Expand ← {
      𝕊 ⟨⟩: best;
      𝕊 cands:
        𝕊 ∧ ⟨⟩ { time‿resources‿robots 𝕊 next:
          { 𝕊 i:
            upto< t ← time- w ← 1+⌈⌈´(i⊏masks)/robots÷˜(n ← i⊏bp)(0⊸⌈-)resources ?
              { ¬∨´(∧´𝕩⊸≤)¨next ? next ⟨𝕩⟩⊸∾ ↩, best ((4⊑𝕩)+(t-upto)ׯ1⊑𝕩)⊸⌈ ↩ ;@
              } t∾(n-˜resources+w×robots)∾((1⊸+)⌾(i⊸⊑)robots)
            ;@
          }¨{robots<○(𝕩⊸⊑)limits }¨⊸/↕4
          next
        }´{⟨⊑𝕩,4↑1↓𝕩,5↓𝕩⟩}¨cands
    }
    (•Fmt n) lib.Debug Expand ⟨⟨0⟩∾⟨0,0,0,0⟩∾⟨1,0,0,0⟩⟩ # ⟨time,resources,robots⟩
  }