backtracking・可逆な探索状態
再帰へ入る直前に局所選択を反映し、復帰時に必ずundoして現在pathだけの制約を保ちながら探索木を列挙する。
この典型を扱う単元: backtracking・可逆な探索状態
検索別名: backtracking、mark-and-unmark DFS、バックトラック
未知問からこの典型を見つける手掛かり
- 扱う対象
- current path
- search tree
- used set
- 使う手掛かり
- 単純pathを列挙
- 選択を戻して別branch
- 保つ不変量
- push/pop symmetry
- used means current recursion path
- 求めるもの
- 制約付き列挙
- 解候補探索
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- rollback・DFS入退場の状態復元: 再帰へ入る前の更新と復帰時のundoを対にし、現在pathだけの不変条件を保つ設計が共通する。
学習成果と学習単位
再帰の前後で使用状態を対称に更新・復元し、現在pathだけの制約を保って探索木を漏れなく列挙できる。
backtracking・可逆な探索状態で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。