Помощь, изменяющая рекурсивную функцию

Question

Учитывая холст, допустим, 10x10 и зададим 3 прямоугольника/квадрата.

Canvas = 10х10

Прямоугольник 1 = 2х2 прямоугольник 2 = 3x3 прямоугольник 3 = 2x4

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

Мы можем видеть, что прямоугольник 1 и 2 не вращаются, IE, если вы поворачиваете любой из них на 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 

Answer 1

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

Я немного изменил логику 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 2

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

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

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

Так после:

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

[......] 

End If

  squareObjects(startPoint).removeSquare(canvas) 

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

Если квадрат прямоугольник (ширина <> высота) затем скопировать тот же код снова (в Тогда код) изменение sqRows с sqls на местеSquareOnCanvas().

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