「8人の女王の問題」のようなアルゴリズムを理解するこのようなお気に入りのタスクを検討してください。 古典的な定義は、「8人の女王をチェス盤に配置して、他の女王が他の女王に勝てないようにすること」です。 タスクはさまざまなインタビューで非常に人気があり、ウィキペディアはすぐ
に私のお気に入りのPythonで解決策を提供します。
そして、これはおそらく普通の人の観点からは正しい決定ですが、ハッカーの観点からは絶対に意味がありません。ここでその理由を説明します。
アルゴリズムを分析してみましょう：リターン付きの古典的な検索を使用して、ソリューション領域をグラフの形で表します。各頂点は女王の位置であり、彼は戦闘中ではなく、すでにボードに配置されている女王を倒しません 正確に8つのピークで構成される「ブランチ」をすべて収集する必要があります。 これらの「ブランチ」を検索する方法として、著者は古典的な幅優先の検索アルゴリズム、すなわち グラフ走査順序は次のようになります。
そして、アルゴリズムが機能するとすぐに、すべての可能な解決策が得られます。
それで問題は何ですか？ 私たちの場合、8x8ボードの場合、92種類のソリューションがあり、実際のタスクでよくあることですが、ボードのサイズがわからないことを想像してください。 大将のようにボードが25x25の場合、ソリューションの数は既に275,986,683,743,434になります。
表、決定の数のボードのサイズへの依存性：
| n ： | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | .. | 24 | 25 | 26 |
|---|
| ユニーク： | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1,787 | 9,233 | 45.752 | .. | 28,439,272,956,934 | 275,986,683,743,434 | 2,789,712,466,510,289 |
|---|
| さまざまな： | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2,680 | 14,200 | 73,712 | 365,596 | .. | 227,514,171,973,736 | 2,207,893,435,808,352 | 22,317,699,616,364,044 |
|---|
これはスクリプトにとって何を意味しますか？ そして、彼が非常に長い検索を行い、すべてのソリューションを頭に入れなければならないので、Pythonは15分で300メガバイトのメモリを消費します。 強力なプロセッサと大量のRAMを持っている人は、このプロセスが完了したかどうかを確認できます...
そして、同様の問題を解決するために必要なのは、正しいグラフトラバーサルアルゴリズムを選択することでした。これは、この場合、通常の深さ検索であり、グラフトラバーサルは次の順序で発生します。
また、コードははるかに単純になり、15分後でも、スクリプトは起動後1秒とまったく同じ量のメモリを消費します。 そして、Pythonでの実装は次のようになります。
def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: for n_row in range(width): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width, sol+[n_row]) def safe_queen(new_row, new_col, sol): for col in range(len(sol)): if (sol[col] == new_row or abs(col - new_col) == abs(sol[col] - new_row)): return 0 return 1 if __name__ == "__main__": for n in range(8): rc_queens(1, 8, [n])
PSこれは、ハッカーの側から見た問題にすぎません。誰かが「理論的なコンピュータサイエンス」の側から見てみることはできますか？