交換論から選択順を導く

概要

貪欲法と交換論

局所選択の交換または候補の支配関係から、調べる順序・残す候補・定数個のcaseを確定する。

二進操作を木へ写して深い一致を優先する例

ABC254 Exでは整数を二進表記の節点と見なし、末尾を一桁削る操作を親への移動に写す。二つの多重集合の要素を深い節点から照合し、一致できる対をその場で確定する。浅い祖先まで先に動かした対を深い位置で一致させ直しても移動回数は増えないため、余剰だけを親へ渡す順序が安全である。片側で許される移動の違いは別に判定する。この例の再利用点は「操作を祖先関係へ変換すること」と「深い一致を交換論で確定すること」の組合せであり、二進表記専用の独立技能としては扱わない。

考え方

今選ぶ候補を固定しても、任意の最適解をその選択を含む解へ悪化させず変形できることを示す。局所比較から大域最適へつなぐ橋が交換論であり、「良さそうな順」だけでは根拠にならない。

交換後の両者の制約と、縮約後の問題を確認する

区間割当てで最早締切aを現在位置xへ置くなら、元の解でaを置いたyとxの相手bを交換する。aがxへ入るだけでなく、L_b≤x≤y≤R_a≤R_bからbもyへ入ることを示す。二属性の箱割当てでは、後続チョコの第一辺は現在以下、交換で渡す箱の第二辺は元の箱以上という二つの条件を別々に使う。交換する片方だけを検査してはならない。

最適併合では費用をΣ葉重み×深さへ数え直す。最小二重みa,bを最深の兄弟葉へ交換しても費用は増えず、二葉を和a+bへ縮約すると費用がa+bだけ減り、残りも同じ最適併合問題になる。従ってOPT(S)=a+b+OPT((S−{a,b})∪{a+b})を葉数について反復できる。これがABC252 FのHuffman法の根拠である。葉の順序や隣接併合が固定される場合は自由な交換ができず、この証明をそのまま使えない。

緩和した最適値と実現可能性を分ける

操作の削除量だけを硬貨へ写すと、硬貨最小枚数は元の切断数の下界になる。しかし硬貨の表現を、重ならない部分木として配置できるとは限らない。まず枚数を増やさない具体的な交換を示し、次に配置を深さについて帰納する。ABC290 GではK V_j+V_l=V_{j+1}+K V_{l−1}という交換と、V_H−1=KV_{H−1}という子への容量の式が、二つの証明をそれぞれ担う。

交換を直接追う代わりに、全解に共通の下界を達成する方法もある。木上の対応付けでは、各子部分木の供給数と需要数の差δは親辺の正味流量となり、少なくとも|δ|の通過が必要である。内部で一致できる供給と需要を全て相殺し、残りだけを親へ送ればこの下界を達成する。ただし辺ごとの通行方向を確認する。ABC254 Exでは0辺は両向き、1辺は上向きだけなので、1辺の子に需要余剰が残る場合は不可能である。「深い方が得」という直感を、各辺の下界と達成へ接続する。

一操作の下界を、達成する操作列へつなぐ

完成形で0になる整数Fが一操作で高々1しか減らないなら、初期Fは必要操作回数の下界である。しかし「閉路へ分解できる」「局所的に直せる」だけでは、その下界を毎回1ずつ減らして完成することは示せない。達成する操作の順序、使用できる要素、残る問題の条件まで与える。

隣接逆転の例では、異色の逆転数Fは異色の隣接交換でだけ変わる。同色の隣接逆転は無料で直し、異色の隣接逆転は費用1で直す。どちらも全体の逆転数を1減らすので停止し、費用を払ったときだけFを1減らして完成形の0にする。これで必要費用Fを達成する。停止量と費用下界が別の量でもよい。

任意交換のABC302 Gでは、現在値→目標値の4×4誤配置Cを作り、値順序pの前向き重みF(p)を下界にする。逆向きpairの相殺は全pのFを一律1減らす。その後の4頂点の均衡graphは、重み0の辺の補完を含め、二種類の3-cycleと一種類の4-cycleへ表せる。各ℓ-cycleをℓ−1交換で直す具体列が、あるpのFと同じ費用となる。ここでは値種類4によるgraph分類が達成性の鍵であり、任意の種類数に閉路分解の存在だけを根拠に同じpotential式を使えない。

成立条件と計算量

交換後も制約が保たれることを確認し、未確定部分に同じ議論を反復する。sortやheapの費用に加えて交換の対象を探す費用を数える。独立集合の交換公理が使える場合はmatroidの節へ進む。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。選択の直感を交換論法や支配関係で裏付け、反例のある貪欲法を見分ける。

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

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-greedy-exchange

習得する技能

  • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: matroid greedy、path matchingのheap縮約greedy、cut・cycle性質から最適全域木を構成する、01 on Tree・親先行順序のcluster縮約。

局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。

このUnitでは扱わないもの

  • 対称操作による状態の正規化。

根拠