再帰の終了条件とバックトラック
呼び出しと戻りの記録から、再帰が終わる条件と探索枝を戻る処理を学びます。
説明
再帰は、処理の途中で同じ関数を呼び出す方法です。小さな問題へ分け、これ以上呼び出さず答えを返す基底条件を設けます。呼び出した側は途中の処理を待ち、戻った値を使って計算を再開します。
最初に配列の合計を左右へ分割して求め、呼び出しと戻りを記録します。その後、2・4・5から合計7になる組を探します。候補を入れた探索が失敗したら外して別の候補へ進む、バックトラックの過程を表示します。
1合計を左右へ分ける
2・4・5・1の合計は、左2個の合計と右2個の合計を足したものです。分割しても元の要素が漏れたり重複したりしないようにします。
values = [2, 4, 5, 1]; middle = len(values)//2入力と分割位置; values[:middle], values[middle:]左右の部分問題, sum(values[:middle]) + sum(values[middle:])部分解を足す左6と右6の合計で12です。左右の合計も同じ規則で分割できます。1個になったらその値が答えなので、そこで分割を止めます。
2呼び出しと戻りを記録する
関数へ入ったときにcall、答えを返す直前にreturnを記録します。0個か1個ならsumで値を返し、2個以上なら左右を再帰呼び出しします。
def total(a, trace):部分配列と履歴
trace.append(('call', a.copy()))入口を記録
if len(a) <= 1:基底条件
answer = sum(a)空なら0、1個ならその値
else:
mid = len(a)//2中央
answer = total(a[:mid], trace) + total(a[mid:], trace)左右の答えを待って加算
trace.append(('return', a.copy(), answer))戻り値を記録
return answer呼び出し元へ返す呼び出しのたびに配列が短くなるため、有限の入力なら基底条件へ到達します。1要素の左と右が返ってから、それらを呼び出した2要素の処理が戻ります。
3戻る順序を確認する
定義した関数で合計を計算し、全履歴を表示します。先頭の4要素が最後に戻る点に注目します。
trace = []; answer = total(values, trace)履歴付きで実行; print(answer)合計; print(*trace, sep='\n')呼び出しと戻りを列挙答えは12です。[2]と[4]が戻った後に[2,4]が6を返し、右側も同様に6を返します。最後に最初の呼び出しが12を返します。単に上から順に同じ関数を実行しているのではなく、呼び出し元の計算が待機しています。
4空配列も終了させる
空配列と1要素を渡します。基底条件を1個だけにすると、空配列を分け続ける実装になり得るため、0個も含めています。
empty_trace = []; one_trace = []別々の履歴; total([], empty_trace), total([9], one_trace)基底条件を実行, empty_trace, one_trace再帰が増えないことを表示空は0、1要素は9です。どちらもcallとreturnだけで追加の再帰がありません。基底条件と、毎回そこへ近づく性質の両方が必要です。
5候補を選ぶ探索
2・4・5から、各値を最大1回使って合計7を作ります。現在の候補をpathに入れ、成功しなければpopで外して次の枝へ戻ります。全て正の数なので、目標を超えた枝は終了できます。
def choose(values, target, i, path, trace):候補・目標・位置・選択・履歴
trace.append(('try', path.copy()))現在の選択を記録
if sum(path) == target: return path.copy()一致したら答え
if i == len(values) or sum(path) > target: return None候補切れ・超過なら失敗
path.append(values[i])使う枝へ
found = choose(values, target, i+1, path, trace)次の候補を探索
path.pop()選択を元へ戻す
if found is not None: return found成功した答えを返す
trace.append(('back', i, path.copy()))枝戻りを記録
return choose(values, target, i+1, path, trace)使わない枝を探索各値を使う枝から先に試し、失敗したら使わない枝を試します。戻るときにpathを元へ戻さないと、別の枝に前の選択が混ざります。成功した答えはコピーして保存します。
6合計7になる枝
2と4を選んだ後に5も入れると11で超過します。5を使わなくても6なので失敗し、4を使わない枝へ戻ります。
search_trace = []; path = []履歴と作業用の選択; found = choose([2, 4, 5], 7, 0, path, search_trace)合計7を探索; print(found)見つかった組; print(*search_trace, sep='\n')試行と枝戻り; print(path)作業用の状態が復元されたか最終的に[2,5]が見つかります。最後のpathは空で、呼び出し前の状態へ戻っています。失敗した[2,4]の選択を残したまま次へ進んでいないことが分かります。
7解がない場合
同じ候補で合計8を探します。どの部分集合でも8にはならないため、全ての必要な枝を調べた後にNoneが返ります。
failed_trace = []失敗時の履歴; choose([2, 4, 5], 8, 0, [], failed_trace)合計8を探索, len(failed_trace)記録したイベント数Noneは答えが空のリストという意味ではなく、解が見つからなかったことを表します。候補数を増やすと使う・使わないの組合せが増え、単純探索では最大2の候補数乗の部分集合を扱います。
8全組合せと照合
小さい入力なので、全ての部分集合の合計を列挙して探索結果を照合できます。
from itertools import combinations部分集合の列挙; possible = sorted({sum(group) for size in range(4) for group in combinations([2, 4, 5], size)})全ての合計; possible, 7 in possible, 8 in possible二つの探索結果を照合可能な合計に7があり、8はありません。列挙はこの小例の検算です。バックトラックでは、条件を満たせない枝を早く打ち切ることで不要な探索を省けますが、枝を切る条件の正しさが必要です。
まとめ
再帰は小さい問題へ進み、基底条件で止め、戻り値を呼び出し元で使います。
バックトラックでは選択を追加して探索し、戻る際に作業用の状態を復元します。
枝の打ち切りには入力条件が必要です。正の値という条件があるから合計超過で終了できます。
操作履歴と解説を振り返れます。
Python 3
values = [2, 4, 5, 1]; middle = len(values)//2; values[:middle], values[middle:], sum(values[:middle]) + sum(values[middle:])([2, 4], [5, 1], 12)
def total(a, trace):
trace.append(('call', a.copy()))
if len(a) <= 1:
answer = sum(a)
else:
mid = len(a)//2
answer = total(a[:mid], trace) + total(a[mid:], trace)
trace.append(('return', a.copy(), answer))
return answertrace = []; answer = total(values, trace); print(answer); print(*trace, sep='\n')12
('call', [2, 4, 5, 1])
('call', [2, 4])
('call', [2])
('return', [2], 2)
('call', [4])
('return', [4], 4)
('return', [2, 4], 6)
('call', [5, 1])
('call', [5])
('return', [5], 5)
('call', [1])
('return', [1], 1)
('return', [5, 1], 6)
('return', [2, 4, 5, 1], 12)empty_trace = []; one_trace = []; total([], empty_trace), total([9], one_trace), empty_trace, one_trace(0, 9, [('call', []), ('return', [], 0)], [('call', [9]), ('return', [9], 9)])def choose(values, target, i, path, trace):
trace.append(('try', path.copy()))
if sum(path) == target: return path.copy()
if i == len(values) or sum(path) > target: return None
path.append(values[i])
found = choose(values, target, i+1, path, trace)
path.pop()
if found is not None: return found
trace.append(('back', i, path.copy()))
return choose(values, target, i+1, path, trace)search_trace = []; path = []; found = choose([2, 4, 5], 7, 0, path, search_trace); print(found); print(*search_trace, sep='\n'); print(path)[2, 5]
('try', [])
('try', [2])
('try', [2, 4])
('try', [2, 4, 5])
('back', 2, [2, 4])
('try', [2, 4])
('back', 1, [2])
('try', [2])
('try', [2, 5])
[]failed_trace = []; choose([2, 4, 5], 8, 0, [], failed_trace), len(failed_trace)(None, 22)
from itertools import combinations; possible = sorted({sum(group) for size in range(4) for group in combinations([2, 4, 5], size)}); possible, 7 in possible, 8 in possible([0, 2, 4, 5, 6, 7, 9, 11], True, False)
演習完了