2

タスクは、N個のクイーンをNxNボードに配置するソリューションの数を数えることです。パフォーマンスを向上させるために考えられるすべてのケースを考えようとしましたが、N=15で実行するにはほぼ50秒かかります。これが私が行ったことです。

Dim resultCount As Integer = 0
Dim fieldSize As Integer = 0
Dim queenCount As Integer = 0
Dim availableCols As Boolean()
Dim availableLeftDiagonal As Boolean()
Dim availableRightDiagonal As Boolean()

Private Sub butCalc_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butCalc.Click
    Dim currentTime As Long = Now.Ticks

    'Reset old result
    resultCount = 0
    fieldSize = CInt(txtFieldSize.Text)
    queenCount = 0

    ReDim availableCols(fieldSize - 1)
    For i As Integer = 0 To fieldSize - 1
        availableCols(i) = True
    Next

    ReDim availableLeftDiagonal((fieldSize - 1) * 2)
    For i As Integer = 0 To (fieldSize - 1) * 2
        availableLeftDiagonal(i) = True
    Next

    ReDim availableRightDiagonal((fieldSize - 1) * 2)
    For i As Integer = 0 To (fieldSize - 1) * 2
        availableRightDiagonal(i) = True
    Next

    'Calculate
    For x As Integer = 0 To fieldSize - 1
        putQueen(x, 0)
    Next

    'Print result
    txtResult.Text = "Found " & resultCount & " in " & (Now.Ticks - currentTime) / 10000 & " miliseconds."
End Sub

Private Sub putQueen(ByVal pX As Integer, ByVal pY As Integer)
    'Put in result
    availableCols(pX) = False
    availableLeftDiagonal(pX + pY) = False
    availableRightDiagonal(pX - pY + (fieldSize - 1)) = False
    queenCount += 1

    'Recursion
    If (queenCount = fieldSize) Then
        resultCount += 1
    Else
        pY += 1 'pY = next row
        For x As Integer = 0 To fieldSize - 1
            If (availableCols(x) AndAlso
                availableLeftDiagonal(x + pY) AndAlso
                availableRightDiagonal(x - pY + (fieldSize - 1))) Then putQueen(x, pY)
        Next
        pY -= 1 'Reset pY
    End If

    'Roll up result
    availableCols(pX) = True
    availableLeftDiagonal(pX + pY) = True
    availableRightDiagonal(pX - pY + (fieldSize - 1)) = True
    queenCount -= 1
End Sub

可能かどうか教えてください（私の先生は正確な時間を教えてくれなかったので、「許容時間」とだけ言っています。可能であれば、方法を教えてください。または、手がかりを教えてください。

4

3 に答える 3

8

ほとんどのソリューションは、他のソリューションのミラーまたは回転バージョンに他ならないことを何らかの形で考慮に入れることを考えています。たとえば、最初のクイーンをすべての列に左から右に配置しようとする必要はありません。左から真ん中だけで十分でしょう。これで、時間はすでに半分に短縮されます。私が間違っていなければ、たとえば 8x8 のボードの場合、クイーンを 7 列目に配置すると、2 列目に配置した場合と同じ結果が得られますが、反転しただけです。なぜそうしないのですか？

指数関数的な複雑さの問題への対処: 正直なところ、20x20 のボードに 20 個のクイーンを配置すると非常に巨大なツリーが作成されるため、適切な時間内に正確な結果を得ることができる最適化はないと思います。調べてみたところ、n=20 の解が 400 億近くありました。oeis.org/A000170を参照してください- n=20 には、n=15 の約 17,000 倍の解があります。この要因によってアルゴリズムを最適化できるとは思いません。したがって、最善を尽くして n=15 で 2 秒にまで短縮したとしても、n=20 では 10 時間近くかかることになります。

このように考えることもできます。20 個のクイーンを持つ 20x20 ボードに 39 029 188 884 のソリューションがある場合、それはどのくらいのデータですか? 各ソリューションを記憶するには、1 から 20 までの 20 個の数値 (水平位置、または各クイーンの x 座標) を保存する必要があります。20 未満の数値を表すには 5 ビットが必要であるため、各ソリューションで 5*20 = 100 ビットになります。100 ビット x 39 029 188 884 は 3634 ギガバイトを意味します。

そして、それはあなたのプログラムが生成しなければならないデータの量です (ソリューションを保存する必要がないことはわかっています。単にそれらを数えているだけです: しかし、チェックできるようにそれぞれを生成する必要があります)。教師は、ハートビートで 3634 ギガバイトの意味のあるデータを生成するプログラムを作成することを合理的に期待することはできません。

このような結果を推定する方法があります。たとえば、クイーンをランダムに何度も広げて、基準を満たす位置にクイーンを配置した回数を数えます (互いに攻撃しない)。たとえば、おそらく 0.0013% の時間です。次に、 (n*n)を掛けます! / (n*(n-1))! - 考えられるすべての構成の数と、見積もりが得られます。しかし、それは明らかに推定にすぎません。それらを無計画に広める時間が長ければ長いほど、この推定はより正確になります。

于 2011-08-20T12:56:33.123 に答える
2

私は組み合わせ列挙を行いましたが、特に N クイーンは行いませんでした。これが私が試してみたいことです (ただし、Morawski が指摘しているように、期待値を下げてください)。

  1. availableCols残りの列をリストする配列に置き換えます。対角線をビット配列として格納します。多すぎて 1 つの単語に収まらない場合は、最初の数行のみを含む対角線 (つまり、ツリーの最上部付近のみに関連する行) を個別に処理する価値があります。理想的には、新しい女王をテストするのに数命令しかかからないでしょう。N が積極的に最適化するコンパイラに知られている場合に役立ちます。

  2. 利用可能な二面対称性を使用して、各軌道で辞書編集的に最小の解のみを列挙します。Burnside のものではない補題を介して全体のカウントを回復します。対称性の破れは非常にコストがかかるため、いつ実行するかについてのコツがありますが、簡単に達成できることもあります (たとえば、クイーンを上の列の最初の行に配置しないでください)。行ごとに配置することは、最適な戦略ではない場合があります。

  3. 検索ツリーの内部ノードで一般化アークの一貫性をテストします。これはおそらく宿題にはあまりにも複雑ですが、OEIS シーケンスの背後にある非常に効率的な計算では、このようなものが使用されていると確信しています。

于 2011-08-20T17:30:25.393 に答える
1

プログラミング コンテストでこれが通常行われる方法は、結果をコード内の配列に入れ、正しいものを出力するだけです。これは非常に高速ですが、教師が探しているものではない場合があります。それからまたそうかもしれません。

于 2011-08-20T13:27:20.583 に答える