Python-分割統治
分割統治法では、手元の問題をより小さなサブ問題に分割し、各問題を個別に解決します。サブ問題をさらに小さなサブ問題に分割し続けると、最終的にはそれ以上分割できない段階に達する可能性があります。それらの「原子的」で可能な最小のサブ問題(分数)が解決されます。元の問題の解決策を得るために、すべてのサブ問題の解決策が最終的にマージされます。
大まかに理解できます divide-and-conquer 3段階のプロセスでアプローチします。
分割/分割
このステップでは、問題をより小さなサブ問題に分割します。サブ問題は、元の問題の一部を表す必要があります。このステップでは、通常、再帰的なアプローチを使用して、サブ問題がさらに分割できなくなるまで問題を分割します。この段階で、サブ問題は本質的にアトミックになりますが、それでも実際の問題の一部を表しています。
征服/解決
このステップには、解決すべき小さなサブ問題がたくさんあります。一般に、このレベルでは、問題はそれ自体で「解決済み」と見なされます。
マージ/結合
小さなサブ問題が解決されると、この段階では、元の問題の解決策が定式化されるまで、それらを再帰的に結合します。このアルゴリズム的アプローチは再帰的に機能し、征服とマージのステップは非常に近く機能するため、1つに見えます。
例
次のプログラムはの例です divide-and-conquer バイナリ検索がPythonを使用して実装されるプログラミングアプローチ。
二分探索の実装
二分探索では、要素のソートされたリストを取得し、リストの中央にある要素の検索を開始します。検索値がリストの中央の値と一致する場合、検索を完了します。それ以外の場合は、検索されたアイテムの値に応じて、リストの右半分と左半分のどちらで続行するかを選択することにより、要素のリストの半分を削除します。これは、リストがソートされており、線形検索よりもはるかに高速であるために可能です。ここでは、与えられたリストを分割し、リストの適切な半分を選択して征服します。要素が見つかるか、リストに要素がないことを結論付けるまで、このアプローチを繰り返します。
def bsearch(list, val):
list_size = len(list) - 1
idx0 = 0
idxn = list_size
# Find the middle most value
while idx0 <= idxn:
midval = (idx0 + idxn)// 2
if list[midval] == val:
return midval
# Compare the value the middle most value
if val > list[midval]:
idx0 = midval + 1
else:
idxn = midval - 1
if idx0 > idxn:
return None
# Initialize the sorted list
list = [2,7,19,34,53,72]
# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))
上記のコードを実行すると、次の結果が生成されます。
5
None