2

给定一个画布，比方说 10x10，并给定 3 个矩形/正方形。

画布 = 10x10

矩形 1 = 2x2 矩形 2 = 3x3 矩形 3 = 2x4

我创建了一个递归函数，它循环画布上每个矩形的每个位置，它工作正常。（我已经包含了下面的功能，以防有人想看到它，但我认为没有必要）。

我们可以看到矩形 1 和 2 是不可旋转的，即，如果将它们中的任何一个旋转 90 度，它们基本上是相同的形状。但是矩形 3 是可旋转的。

如何更改/构造循环/递归函数，使其循环每个矩形的每个位置以及每个可能的旋转？

目的是遍历画布上所有可能的形状拟合。

谢谢你的帮助！

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 的结果与未旋转矩形的结果相同，只是 Canvas 的原点不同。想象一下，让 Rectangle 3 不旋转，然后将画布向另一个方向旋转 90 度。这意味着您应该能够对相同的结果使用一些数学来得到答案。

于 2010-06-24T08:57:53.467 回答
0

将您的 (x,y) 坐标循环放在它自己的函数中。然后在一个WxH的矩形上调用(x,y)坐标循环，然后在旋转的矩形HxW上再次调用。

或者，您可以将分支放在 (x,y) 循环内的矩形的两个旋转上，在两个坐标都被拾取之后，但在您进行递归调用之前。

在这两种情况下，您都需要注意旋转是否会导致矩形超出边界框的高度或宽度。

于 2010-06-24T22:47:11.300 回答
0

您不能简单地扫描形状列表并为矩形 ( SizeX != SizeY) 添加一个克隆矩形{ SizeX = source.SizeY, SizeY = source.SizeX }（例如：旋转矩形）吗？

这当然意味着循环两次（一次用于未旋转的形状列表，一次用于旋转的形状）。

=> 做类似的事情

squareObjects(startPoint) = squareObjects(startPoint).Rotate();
recurse(startPoint);
于 2010-07-05T15:26:32.917 回答
0

如果您在单独的例程中提取循环，则解决方案相对容易出现。

我已经稍微更改了validSolution 逻辑以使代码更短——现在如果解决方案无效，我们就不会调用recurse，并且我们不需要在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

坦率地说，我不认为你的实现是最好的——但如果你不想做大的改变和做单独的例程，你可以把矩形的代码两次放在同一个函数迭代中。

所以之后：

'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 回答