では、Notebook に 爆発的バックトラッキングの仕組み図 を追加する教材を作ります。
Python の graphviz や matplotlib を使って、マッチの分岐や再試行の流れを可視化します。
爆発的バックトラッキングの仕組み図付き Notebook 追加例
# ==========================
# セル6: 爆発的バックトラッキングの仕組み図
# ==========================
# この例では簡単な (a+)+ に対して分岐の試行を可視化
from graphviz import Digraph
# ノード作成
dot = Digraph(comment='Catastrophic Backtracking Example')
# 状態ノード
dot.node('S', 'Start')
dot.node('A1', 'a+ を1回目')
dot.node('A2', 'a+ を2回目')
dot.node('F', 'Fail (bで不一致)')
dot.node('M', 'Match (成功)')
# 矢印（試行の流れ）
dot.edges(['SA1', 'A1A2', 'A2F'])
# バックトラックの矢印（失敗して再試行）
dot.edge('A2', 'A1', label='バックトラック')
dot.render('backtracking_example', format='png', cleanup=True)
from IPython.display import Image
Image('backtracking_example.png')
説明
S→A1→A2→Fの流れで、最後に失敗。- 失敗したため
A2からA1に バックトラック。 A1→A2の組み合わせを変えて再試行。- この再試行が文字列長や量指定によって指数的に増えるため、処理時間が爆発します。
- 実際には
(a+)+のように 多重ネストされた貪欲量指定 が典型例。
Notebook に追加するとどうなる？
- 前のセルで危険パターンと安全パターンの処理時間を体感
- このセルで 分岐とバックトラックの流れを図解
- 視覚的に「なぜ遅くなるのか」が直感的に理解できる
💡 さらに発展させる場合：
- 各文字列長でのノード数の増え方をアニメーションで可視化
- 実際の文字列に対してマッチの「どの分岐で再試行したか」をログ出力して図に反映