path matchingのheap縮約greedy
pathの非隣接edgeからk本を選ぶ最小重みmatchingを、最小edgeの採用と近傍二辺の補正縮約 w_l+w_r-w_i により全cardinalityについて順に求める。
この典型を扱う単元: path matchingのheap縮約greedy
検索別名: minimum k-matching on a path、path matching contraction、path matching縮約
未知問からこの典型を見つける手掛かり
- 扱う対象
- linked alive edges
- nonadjacent selection
- weighted path edges
- 使う手掛かり
- pathから隣接しないk辺
- 全kの最小費用
- 最小辺を選んで近傍を縮約
- 保つ不変量
- selected prefix is optimal by cardinality
- 補正edge preserves every remaining optimum
- 求めるもの
- cardinality別最小matching費用
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- priority queue・best-first列挙: 現在もっとも有利な局所matching候補をheapから取り出し、縮約後の候補を再挿入する。
学習成果と学習単位
重み付きpathの最小k-matchingについて、最小edge採用後の補正縮約を証明し、heapと双方向linkで全cardinalityの最適値を求められる。
path matchingのheap縮約greedyで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。