difference constraints・不等式系の最短路化
差の上界 x_v-x_u≤c を有向辺 u→v の重みcへ写し、Bellman–Ford等の緩和と負閉路から可解性・極値・具体解を求める。
この典型を扱う単元: difference constraints・不等式系の最短路化
検索別名: constraint graph、difference constraints、差の不等式、差分制約
未知問からこの典型を見つける手掛かり
- 扱う対象
- constraint graph
- variables
- x_v-x_u<=c
- 使う手掛かり
- prefix sum inequality
- 差の上界または下界
- 整数列の区間個数制約
- 保つ不変量
- edge relaxation preserves every upper bound
- negative cycle iff infeasible
- 求めるもの
- 制約を満たす列の構成
- 可解性判定
- 変数の極値
- 適用しない条件
- online union/query
- 等式だけのpotential伝播
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 最短路モデル: 各不等式 x_v-x_u<=c を有向辺 u->v の緩和条件へ写し、可解性・極値を最短路または負閉路判定へ帰着する。
学習成果と学習単位
差の不等式をconstraint graphへ変換し、緩和と負閉路判定により可解性・極値・具体解を求められる。
difference constraints・不等式系の最短路化で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。