アルゴリズム設計思想(1)——窮挙法

本文は王暁華先生GitChat【アルゴリズムはどのように遊ぶべきです】課程のノートです.

1.窮挙法の概念

窮挙法は窮挙探索法とも呼ばれ,問題ドメインの解空間において可能なすべての解窮挙探索を行い,条件に基づいて最適解を選択する方法の総称である.
数学的にも窮挙法を列挙法と呼ぶのは,有限要素からなる集合の中で,すべての要素を一つ一つ列挙して研究する方法である.
窮挙法は一般に条件に合致するすべての解を探し出すために用いられるが,最適解の判断条件が与えられると,窮挙法は最適解問題を解くためにも用いられる.

2.設計構想

窮挙法を用いて問題を解決するには、基本的に以下の2つのステップがあります.

は、問題の解(または状態)の定義、解空間の範囲、および正確な解の判定条件を決定する.

解空間の特徴に基づいて検索ポリシーを選択し、解空間における候補解が正しいかどうかを1つずつ検証する.

2.1空間定義を解く

解空間はすべての可能な候補解の制約範囲であり、問題の解がこの制約範囲内にあることを決定し、検索ポリシーをこの制約範囲に適用すれば問題の解を見つけることができる.

2.2窮挙解空間の策略

窮挙解空間の戦略は探索アルゴリズムの設計戦略であり、問題のタイプに応じて、解空間の構造は線形表、集合、木または図である可能性があり、異なるタイプの解空間に対して、それに適応する窮挙探索アルゴリズムを設計する必要がある.
もし1種の捜索の策略を選択するならば、いかなる仮定の貧乏な捜索を持たないで、行がだめであるに関わらず、眉のひげをつかんで、すべての可能な解をすべて検査して、このような捜索は通常“盲目的な捜索”と呼ばれます.
これに対応して、あるポリシーまたは計算根拠を利用して、啓発関数によって目的のある検索行為を策動し、これらのポリシーと根拠は通常アルゴリズムの収束速度を速めることができ、あるいはより小さく、最も解が現れる可能性のある空間を画定し、この空間で検索することができ、このような検索は通常「啓発的検索」と呼ばれる.
一般的に、アルゴリズムの解を速めるために、通常、探索アルゴリズムの実行過程でいくつかの剪断アルゴリズムを補助し、明らかに正確な解ではない検査過程を排除し、貧挙の効率を高める.
剪断は,ある状態ノードが結果を発展させることが不可能であると判断した場合,この状態ノードからの探索を停止すべきであり,状態ツリー上のこの分枝に相当する.
剪断ポリシーに加えて、探索深さを制限する方法を使用してアルゴリズムの収束を速めることもできますが、探索深さを制限すると無解になるか、最適解を逃す可能性があります.通常、ゲームツリーの探索など、特定の状況でのみ使用されます.

2.3枝切り戦略

解空間を窮屈に探索する場合,問題から与えられた情報に基づいて最適解の進化が不可能であると明確に判定できる状態ノードがある場合,すなわち,このノードから得られたサブツリーを遍歴すると,正しい解が存在する可能性があるが,最適解ではないに違いない,この状態ノードの遍歴をスキップすることができ,アルゴリズムの実行効率が極めて向上する,これが剪断戦略である.剪断戦略を適用する難点は,状態ノードを評価する評価方法(推定関数)をどのように見つけるかである.

3.例

3.1百元で鶏を買う問題

100元で100羽の鶏を買うのは、典型的な貧乏挙法の応用だ.问题描述:1羽の大きい雄鶏は5つのお金に値して、1羽の雌鶏は3つのお金に値して、3羽のニワトリは1つのお金に値して、今100つのお金があって、100羽のニワトリを买いたいですが、どのように买いますか?いくつの方法がありますか.

盲目的に検索してx羽の雄鶏を買うと仮定して、y羽の雌鶏、z羽のニワトリ、コードを使って以下のように解きます:

%%time
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            if x + y + z == 100 and 5*x + 3*y + z/3.0 == 100:
                print x, y, z

出力結果

4 18 78
8 11 81
12 4 84
CPU times: user 76.3 ms, sys: 0 ns, total: 76.3 ms
Wall time: 75.2 ms

啓発探索x羽雄鶏、y羽雌鶏を買うと仮定すると、xは最大20羽、yは最大33羽、ニワトリは100-x-y羽となり、コードを用いて以下のように解く:

%%time
for x in range(1, 21):
    for y in range(1, 34):
        if 5*x + 3*y + (100-x-y)/3.0 == 100:
            print x, y, 100-x-y

出力結果

4 18 78
8 11 81
12 4 84
CPU times: user 4.43 ms, sys: 0 ns, total: 4.43 ms
Wall time: 2.56 ms

第2の探索アルゴリズムは第1の探索アルゴリズムより明らかに速いことがわかる.

3.2鶏とウサギの同籠問題

貧乏挙法の経典のテーマ:鶏とウサギの同籠問題.鶏とウサギが1つのかごの中にいて、頭を数えて50頭、足を数えて120匹の足があって、鶏とウサギはそれぞれ何匹ありますか?

盲目的にx鶏を買うと仮定して、y匹のウサギ、コードを使って以下のように解きます:

%%time
for x in range(1, 51):
    for y in range(1, 51):
        if x + y == 50 and 2*x + 4*y == 120:
            print x, y

出力結果

40 10
CPU times: user 0 ns, sys: 3.19 ms, total: 3.19 ms
Wall time: 2.17 ms

啓発検索x鶏を買うと仮定すると、ウサギの数は50-xしかなく、コードを使って以下のように解く:

%%time
for x in range(1, 51):
    if 2*x + 4*(50-x) == 120:
        print x, 50-x

出力結果

40 10
CPU times: user 190 µs, sys: 0 ns, total: 190 µs
Wall time: 137 µs

同様に,第2の探索アルゴリズムが第1の探索アルゴリズムよりも著しく速いことも分かる.