2

キャンバスが与えられ、たとえば10x10で、3つの長方形/正方形が与えられたとします。

キャンバス=10x10

長方形1=2x2長方形2=3x3長方形3=2x4

キャンバス上のすべての長方形のすべての位置をループする再帰関数を作成しましたが、これは正常に機能します。（誰かが見たいと思う場合に備えて、以下の関数を含めましたが、それは必要ではないと思います）。

長方形1と2は回転できません、つまり、どちらかを90度回転させると、基本的に同じ形状になります。ただし、長方形3は回転可能です。

可能なすべての回転とともに、すべての長方形のすべての位置をループするように、loop / recurisve関数を変更/構築するにはどうすればよいですか？

目的は、キャンバス上の形状の可能なすべてのフィッティングをループすることです。

助けてくれてありがとう！

Sub recurse(ByVal startPoint As Integer)

    Dim x As Integer
    Dim y As Integer
    Dim validSolution As Boolean = isSolutionValid()
    Dim loopXTo As Integer
    Dim loopYTo As Integer
    Dim solutionRating As Integer

    'If parent nodes create invalid solution, we can skip (375 iterations from 1,600 iterations saving)
    If validSolution = True Then

        If (startPoint = 0) Then
            loopXTo = Math.Floor((canvasCols - squareObjects(startPoint).sqRows()) / 2)    '576 iterations from 1,680 iterations
            loopYTo = Math.Floor((canvasRows - squareObjects(startPoint).sqCols) / 2)       '31,104 iterations from 90,720 iterations
        Else
            loopXTo = canvasCols - squareObjects(startPoint).sqRows
            loopYTo = canvasRows - squareObjects(startPoint).sqCols

        End If

        'Loop all positions on canvas
        For x = 0 To loopXTo
            For y = 0 To loopYTo

                'Set coords of square
                squareObjects(startPoint).setSquareCords(x, y)

                'Phyiscally place it in canvas
                placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)

                'Recursive, get next square
                If (startPoint + 1 < totalSquares) Then
                    recurse(startPoint + 1)
                Else
                    validSolution = isSolutionValid()

                    'Is solution valud
                    If (validSolution = True) Then
                        solutions = solutions + 1
                    End If

                    iterations = iterations + 1

                    'Response.Write("<br /><b>Iteration " & iterations & "</b>")
                    If (validSolution) Then

                        'Rate solution, record if best
                        solutionRating = rateSolution()
                        If solutionRating > bestCellSaving Then
                            bestCellSaving = solutionRating
                            copySolution()
                        End If
                        'Response.Write(" <span style='color:green'> <B>VALID SOLUTION</B></span> (" & rateSolution() & ")")
                    End If
                    'printCanvas(canvas)

                End If

                squareObjects(startPoint).removeSquare(canvas)

            Next
        Next
    End If

End Sub
4

5 に答える 5

0

キャンバスが常に正方形である場合は、あまり変更する必要はありません。回転した長方形3の結果は、キャンバスの原点が異なることを除いて、回転していない場合と同じです。Rectangle 3を回転させずに、キャンバスを反対方向に90度回転させることを想像してみてください。これは、同じ結果に対していくつかの数学を使用して答えを得ることができるはずであることを意味します。

于 2010-06-24T08:57:53.467 に答える
0

（x、y）座標ループを独自の関数に配置します。次に、WxHの長方形で（x、y）座標ループを呼び出し、回転した長方形HxWで再度呼び出します。

または、両方の座標が選択された後、再帰呼び出しを行う前に、（x、y）ループ内の長方形の2つの回転に分岐を配置することもできます。

どちらの場合も、回転によって長方形がバウンディングボックスの高さまたは幅を超えるかどうかに注意する必要があります。

于 2010-06-24T22:47:11.300 に答える
0

率直に言って、あなたの実装が最善だとは思いませんが、大きな変更を加えて別のルーチンを作成したくない場合は、同じ関数反復で四角形のコードを 2 回入れるだけで済みます。

だから後：

'Phyiscally place it in canvas placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)

[......]

End If

            squareObjects(startPoint).removeSquare(canvas)

チェックを行うことができます

正方形が長方形 (幅 <> 高さ) の場合は、同じコードを (Then コードで) 再度コピーし、placeSquareOnCanvas() で sqCols を使用して sqRows を変更します。

これにより、各長方形に対して 2 つの再帰分岐が作成されるため、再帰は線形ではなくなります。同じコードを 2 回コピーするのはあまり良くないかもしれませんが、結果は正しく、コードの変更は最小限であり、コードに基づいたこのストレートなソリューションは、他の微調整を試すよりもパフォーマンスが高くなります。

于 2010-07-08T02:25:40.117 に答える
0

別のルーチンでループを抽出すると、ソリューションは比較的簡単に現れます。

コードを短くするために、validSolution ロジックを少し変更しました。ソリューションが無効な場合は再帰を呼び出さず、recurse() の先頭で isSolutionValid() をチェックする必要もありません。これらの変更により反復のカウントが難しくなったため、そのコードを削除しましたが、後で追加できるはずです。

最後の「If」ステートメントのない recurse() ルーチンは、コードとまったく同じように動作する必要があります。最後の "If" ステートメントは、基本的に、回転した四角形のループを実行します。

removeSquare() がどのように実装されているかはわかりませんが、正しく機能させるには方向を知る必要があるかもしれません。

Sub recurse(ByVal startPoint As Integer)
    Dim loopXTo As Integer
    Dim loopYTo As Integer
    If (startPoint = 0) Then
        loopXTo = Math.Floor((canvasCols - squareObjects(startPoint).sqRows) / 2)
        loopYTo = Math.Floor((canvasRows - squareObjects(startPoint).sqCols) / 2)
    Else
        loopXTo = canvasCols - squareObjects(startPoint).sqRows
        loopYTo = canvasRows - squareObjects(startPoint).sqCols
    End If
    fitSqare(loopXTo, loopYTo, False)
    If (squareObjects(startPoint).sqCols <> squareObjects(startPoint).sqRows) Then
        fitSqare(loopYTo, loopXTo, True)
    End If
End Sub

Sub fitSquare(ByVal loopXTo As Integer, ByVal loopYTo As Integer, ByVal rotate As Boolean)
    Dim x As Integer
    Dim y As Integer
    Dim solutionRating As Integer
    Dim validSolution As Boolean

    'Loop all positions on canvas
    For x = 0 To loopXTo
        For y = 0 To loopYTo
            'Set coords of square
            squareObjects(startPoint).setSquareCords(x, y)

            'Phyiscally place it in canvas
            If (rotate) Then
                placeSquareOnCanvas(x, y, squareObjects(startPoint).sqCols, squareObjects(startPoint).sqRows)
            Else
                placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)
            End If

            validSolution = isSolutionValid()
            'Is solution valud
            If (validSolution) Then
                'Recursive, get next square
                If (startPoint + 1 < totalSquares) Then
                    recurse(startPoint + 1)
                Else
                    solutions = solutions + 1
                    'Rate solution, record if best
                    solutionRating = rateSolution()
                    If solutionRating > bestCellSaving Then
                        bestCellSaving = solutionRating
                        copySolution()
                    End If
                End If
            End If
            squareObjects(startPoint).removeSquare(canvas) 'removeSquare may require additional work to handle rotated state
        Next
    Next
End Sub
于 2010-07-06T15:14:45.287 に答える
0

単純に形状のリストをスキャンして、長方形 ( SizeX != SizeY) のクローンを作成した長方形{ SizeX = source.SizeY, SizeY = source.SizeX }(例: 回転した長方形) を追加することはできませんか?

もちろん、これはループを 2 回行うことを意味します (1 つは回転されていない形状のリスト用で、もう 1 つは回転された形状のリスト用です)。

=>次のようなことをする

squareObjects(startPoint) = squareObjects(startPoint).Rotate();
recurse(startPoint);
于 2010-07-05T15:26:32.917 に答える