Помогите изменить рекурсивную функцию

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

Честно говоря, я не думаю, что ваша реализация лучшая, но если вы не хотите вносить большие изменения и делать отдельные подпрограммы, вы можете просто поместить код для прямоугольников дважды в одну и ту же итерацию функции.

Итак, после:

'Phyiscally place it in canvas placeSquareOnCanvas(x, y, squareObjects(startPoint).sqRows, squareObjects(startPoint).sqCols)</p> <pre><code>[......]

End If

            squareObjects(startPoint).removeSquare(canvas)

Вы можете сделать чек

ЕСЛИ квадрат является прямоугольником (ширина <> высота) затем скопируйте тот же код снова (в коде Then), изменив sqRows с sqCols в placeSquareOnCanvas ().

Рекурсия больше не будет линейной, так как это создаст 2 рекурсивных ветви для каждого прямоугольника. Может быть, это не очень хорошо написано, копируя один и тот же код 2 раза, но результат будет правильным, изменение кода минимально, и это прямое решение, основанное на вашем коде, будет иметь большую производительность, чем попытки других настроек.

Answer 2

Если вы извлекаете циклы в отдельной процедуре, решение возникает относительно легко.

Я немного изменил логику validSolution, чтобы сделать код короче - теперь мы не вызываем recurse, если решение неверно, и нам не нужно проверять isSolutionValid () в начале recurse ().Эти изменения усложняют подсчет итераций, поэтому я удалил этот код, но его можно будет добавить позже.

Процедура recurse () без последнего оператора «If» должна вести себя точно так же, как ваш код.Последний оператор «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 3

Поместите ваш (x, y) координатный цикл в его собственную функцию.Затем вызовите (x, y) координатный цикл для прямоугольника WxH, а затем вызовите его снова для повернутого прямоугольника HxW.

В качестве альтернативы вы можете поместить разветвление на два поворота вашего прямоугольника внутри (x, y), после того, как обе координаты были выбраны, но перед тем, как вы сделаете рекурсивный вызов.

В обоих случаях вам нужно быть осторожным в том, что ваш поворот заставляет прямоугольник превышать высоту или ширину вашегоограничительная коробка.

Answer 4

Разве вы не можете просто отсканировать список фигур и для прямоугольников (SizeX != SizeY) добавить клонированный прямоугольник с { SizeX = source.SizeY, SizeY = source.SizeX } (например, повернутый прямоугольник)?

Это, конечно, означало бы делать циклы дважды (один для не повернутого списка фигур и один для повернутого).

=> делать что-то вроде

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

Answer 5

Если холст всегда квадратный, вам не нужно много менять. Результат для повернутого прямоугольника 3 такой же, как и для не повернутого, но источник Холста отличается Представьте, что Rectangle 3 оставлен без поворота и поверните холст на 90 градусов в другом направлении. Это означает, что вы должны быть в состоянии использовать некоторые математические вычисления для получения одинаковых результатов, чтобы получить свой ответ.