制限時間を守るために枝刈りする
改善につながらない分岐を切り捨てます
「制限時間を守るために枝刈りする」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
枝刈りが重要な理由
何も考えずにバックトラッキングすると、分岐を探索しすぎて時間制限に達することがあります。枝刈りによって見込みのない分岐を早期に切り捨て、高速に処理できます。✂️
枝刈りとは何か
枝刈りとは、その分岐が有効な答えや、より良い答えに到達できないと証明できた時点で処理を止めることです。その分岐は完全に探索を省略します。
実現可能性による枝刈り
現在の部分的な選択がすでにルールに違反しているなら、すぐに戻ります。この実現可能性チェックにより、壊れた状態をもとに処理を続けずに済みます。
if violates(cur):
return上界による枝刈り
それまでに見つかった最良の答えを記録します。ある分岐が到達できる最良の結果でさえ現在の答えより悪いなら、その分岐を打ち切ります。これが分岐に対する上界です。
コードで枝刈りする
ここでは、楽観的に見積もっても現在の最良解を上回れない場合に上界によって分岐を止めています。
if cur_cost + best_possible <= best:
return選択肢を賢く試す
最も有望な選択肢から試すと、良い答えを早く見つけられます。その結果、上界が引き上げられ、後の分岐をより多く枝刈りできます。
制約伝播
ある選択をした後で、後続の処理で可能なことを絞り込みます。あらかじめ不可能な選択肢を取り除くことを制約伝播といい、探索木を小さくできます。
対称性の除去
2つの分岐が鏡像の関係にあるなら、片方だけを探索します。対称性の除去によって、答えを失わずに処理量を半分以下にできる場合があります。
重複する状態をメモ化する
同じ部分状態が再び現れたら、その結果をキャッシュします。メモ化により、繰り返し現れる部分木を1回の高速な検索に置き換えられます。
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...後回しにせず早く枝刈りする
打ち切り条件は、再帰する前に確認します。早期枝刈りにより、見込みのない分岐を展開する無駄な処理を避けられます。
実行前に見積もる
最悪の場合の分岐数が制約に対して適切か、必ず確認します。大きすぎる場合は、より強い枝刈りか、別の方法が必要です。
クイックチェック
バックトラッキングで枝刈りを行う目的は何ですか？
まとめ：見込みのない分岐を切り捨てる
実現可能性チェックと上界チェック、賢い順序付け、対称性の除去、メモ化によって枝刈りを行い、時間制限を乗り切る方法を学びました。🎯
よくある質問
「制限時間を守るために枝刈りする」レッスンは無料ですか？
はい。「制限時間を守るために枝刈りする」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「制限時間を守るために枝刈りする」で何を学びますか？
改善につながらない分岐を切り捨てます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「制限時間を守るために枝刈りする」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 再帰的に考える: Base と Recurse
- すべての部分集合を生成する
- 順列と N-Queens の考え方
- 制限時間を守るために枝刈りする