半環行列・min-plus/max-min遷移
遷移の結合と候補選択を半環の積・和として行列化し、結合則を使って固定長walkを二分累乗または区間積で処理する。
この典型を扱う単元: 半環行列・min-plus/max-min遷移
検索別名: max-min matrix exponentiation、min-plus matrix exponentiation、半環行列累乗
未知問からこの典型を見つける手掛かり
- 扱う対象
- fixed-length walk
- semiring
- transition matrix
- 使う手掛かり
- min-plus/max-min composition
- ちょうどK回の遷移
- 保つ不変量
- associative matrix product
- semiring identity
- 求めるもの
- 固定長path最適化
- 巨大回数遷移
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 組合せ・多項式・線形代数への変換
関連する典型
- monoid exponentiation・連結演算doubling: 閉じた結合的合成を二分累乗する共通原理を、行列半環と一般monoidの二つの表現から比較する。
学習成果と学習単位
遷移を半環行列として定義し、結合則と単位元を保つ二分累乗・区間積で巨大回数の最適化遷移を計算できる。
半環行列・min-plus/max-min遷移で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC236 G「Good Vertices」 公式問題主題: 半環行列・min-plus/max-min遷移 / 主タグ
- ABC429 F「Shortest Path Query」 公式問題主題: 区間monoid要約 / 補助タグ
- ABC445 F「Exactly K Steps 2」 公式問題主題: 半環行列・min-plus/max-min遷移 / 主タグ
- ABC456 F「Plan Holidays」 公式問題主題: SWAG・two-stack queue aggregation / 補助タグ
技能・出典
主題: SWAG・two-stack queue aggregation
主タグ: SWAG・two-stack queue aggregation / 補助タグ: 半環行列・min-plus/max-min遷移