priority queue・best-first列挙

概要

全候補を作るには多すぎても、必要なのが先頭の少数だけなら、次に選べる候補を保つことで列挙を途中で止められる。この単元では、候補集合の外に、もっと先に選ぶべきものがない理由を学ぶ。

priority queue・best-first列挙

優先度付きキュー(priority queue)は、候補の追加と、優先値が最小または最大の候補の取り出しを行うデータ構造である。代表的な実装がヒープ(heap)で、最小値を取り出すものをmin-heap、最大値を取り出すものをmax-heapと呼ぶ。

現在の候補の中から最も優先するものを取り出し、そこから次の候補を生成する探索をbest-first探索と呼ぶ。これで全体を値の順に列挙するには、まだ生成していない候補が先に選ばれるべきものではない、と保証する必要がある。まずは二つの配列の和で、その保証を考えよう。

考え方

昇順の配列 A=(1,4),B=(2,5)A=(1,4), B=(2,5) から一つずつ選び、和を小さい順に取り出したい。和を行ごとに並べると、次の表になる。添字は0から始める。

行最初の和次の和
i=0i=01+2=31+2=31+5=61+5=6
i=1i=14+2=64+2=64+5=94+5=9

各行は既に昇順なので、未出力の先頭だけをmin-heapに入れる。和と一緒に添字の組を保持すれば、どの行を進めるかも分かる。最初は3と6。3を出力したら同じ行の次の6を追加し、以後も「取り出した行の先頭」だけを進める。結果は3、6、6、9となる。同じ値の6でも選んだ組が違うので二回数える。

このような「既に生成した、次に選べる候補の集合」を探索境界(frontier)と呼ぶ。まだheapにない値は、その行の先頭以上である。したがってheapの最小値は、未出力の全候補の最小値でもある。heapを使うことに加えて、この不変条件が順序の正しさを保証する。

成立条件と計算量

この例で、小さい方から最大 KK 組を求めるとする。∣A∣,∣B∣|A|,|B| はそれぞれの配列の要素数を表す。各行の先頭を一括でheap構築すると O(∣A∣)O(|A|)。実際に出力する組数を L=min⁡(K,∣A∣∣B∣)L=\min(K,|A||B|) とすれば、列挙は O(Llog⁡(∣A∣+1))O(L\log(|A|+1))、配列を除く空間は O(∣A∣)O(|A|)。どちらかの配列が空なら終了し、全組数より多く要求されてもheapが空になったら止める。

この例の状態は選んだ添字の組であり、各組を一つ前の列から一度だけ生成する。ABC391 Fのように複数方向から同じ状態を生成する列挙でも、優先値と後続の遷移が状態だけで決まり、到達経路によらないなら、heapへの追加時に生成済み状態を記録して二重登録を防げる。「同じ状態」と「同じ値の別状態」は区別する。

ABC297 Eでは、買い方が違っても同じ金額は一回だけ数える。同額なら次に一個足して作れる金額も同じなので、金額そのものを状態にできる。解説では同額を取り出した際に、順位の更新と次候補の生成を両方省いている。ABC391 Fでは添字の組、ABC297 Eでは金額を区別する、という数える対象の違いに注目して読み比べたい。

一方、ABC305 Eのように、同じ頂点へ後からより良い値で到達できる探索では、追加済みという理由で再登録を禁止できない。頂点ごとに、これまでに見つけた最良値を暫定値として持ち、改善したら更新してheapへ再登録する。この更新を緩和と呼ぶ。取り出した候補の値が現在の最良値と一致しなければ、古い候補として捨てる。

例えば、辺を一つ進むごとに体力が1減るとする。パス 1–2–3–4 の頂点1に体力4、頂点2に体力1の警備員がいるとき、頂点2は初期登録済みでも、頂点1から届く体力3へ更新する必要がある。再登録して伝播すれば、各頂点の最大残り体力は順に 4,3,2,14,3,2,1 となる。頂点2の再登録を禁止すると、その先の頂点4まで警備できることを見落とす。

最大値から列挙するならmax-heapを使う。ABC391 Fでは、最大の組から添字を一つずつ増やすと値は増えない。任意の未出力状態へ至る経路で最初の未出力状態は、出発点として、または直前の状態を取り出したときに登録され、heapに残っている。その値は経路の先の値以上なので、heapの外に最大値を見落とすことはない。最小値からの列挙では不等号の向きが逆になる。符号や遷移が変わる問題では、この性質を改めて確認する。

復習では、heapの外にもっと良い候補がないのはなぜかを説明してから、ABC391 Fの三方向への展開と比べる。操作自体を確認するなら概念上の親単元へ戻る。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。優先度付きキューで、現在選べる候補だけを管理して順に取り出す。

対象色の読み方は本書の読み方を参照してください。

概念上の親: heap・ordered setで全候補の極値を保つ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-priority-queue-best-first

習得する技能

  • 未出力の候補を代表する探索境界を設計し、集合の外により良い候補がない理由を説明する。
  • 何を同じ状態とみなすか、登録時に重複を除けるかを判断し、生成する候補数から計算量を評価する。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: path matchingのheap縮約greedy。

全候補を最初からheapへ入れる場合から一歩進み、必要な候補だけを生成して探索する場合を扱う。

このUnitでは扱わないもの

  • priority queue・best-first列挙の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠