帮助修改递归函数

Question

给定一个画布，比方说 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

Answer 1

如果将循环提取到单独的例程中，解决方案就会相对容易地出现。

我对 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

Answer 2

如果画布始终是正方形，那么您不需要做太多改变。旋转后的矩形 3 的结果与未旋转的相同，只是 Canvas 的原点不同。想象一下，让矩形 3 保持不旋转，并将画布向另一个方向旋转 90 度。这意味着您应该能够对相同的结果进行一些数学计算来获得答案。

Answer 3

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

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

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

Answer 4

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

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

=>做类似的事情

squareObjects(startPoint) = squareObjects(startPoint).Rotate();
recurse(startPoint);

Answer 5

坦率地说，我不认为您的实现是最好的，但是如果您不想进行大的更改并创建单独的例程，您可以将矩形的代码放在同一个函数迭代中两次。

所以之后：

<代码>
'将其物理地放置在画布上
placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)

[......]

End If

            squareObjects(startPoint).removeSquare(canvas)

您可以检查

正方形是否为矩形（宽度 <> 高度） ）
然后再次复制相同的代码（在“Then 代码”中），在 placeSquareOnCanvas() 中更改 sqRows 和 sqCols。

递归将不再是线性的，因为这将为每个矩形创建 2 个递归分支。也许将相同的代码复制两次并不是很好，但结果是正确的，代码更改很小，并且这种基于代码的直接解决方案将比尝试其他调整具有更高的性能。