Максимизируйте область, используемую прямоугольниками, помещенными в круг

Question

У меня есть круг, который мне нужно заполнить прямоугольниками. Складывается один над другим. Прямоугольники доступны только в определенных размерах. И нам также дается количество прямоугольников, которые мы должен положить. Мне нужно получить набор прямоугольных длин, которые покрывают большую площадь круга. Например, если круг имеет диаметр 100, прямоугольники длин [100,95,90,85, ... 15,10 , 5]. Я попытался использовать метод грубой силы, проанализировав все возможные комбинации. Это дает хорошие результаты, когда числа малы. Другой алгоритм, который я пытался, - это ограничить диапазон длин, которые каждый прямоугольник занимает. первый прямоугольник будет иметь длину 95 или 90, чтобы дать лучший результат. Но даже этот метод громоздкий, когда количество прямоугольников, которые нужно положить, действительно велико. Вот как расположены прямоугольники

Если первый прямоугольник имеет длину l, а диаметр круга d, его толщина составляет sqrt (d2-l2). Толщина второго, если его длина равна k, равна sqrt (d2-k2) -sqrt (d2-L2).

Есть ли какой-либо алгоритм, чтобы я мог сформулировать результаты.

Answer 1

Зачем нужна грубая атака на эту проблему? Вам просто нужно приложить некоторые усилия в вашем расчетном коде, и я уверен, что он будет работать нормально. У него всего 19 уровней. Это не должно быть слишком сложным и даст вам результат в течение ... ну, несколько часов, как я только что узнал. 19 уровней приведут к расчетам 3.3e17.

Об алгоритме:
С помощью одного прямоугольника вы получаете наибольшую площадь покрытия, когда прямоугольник представляет собой квадрат. Я думаю, это очень легко понять. Угол квадрата находится на расстоянии 45 ° от центра круга (при условии, что горизонталь равна 0 °, но на самом деле это не имеет значения, поскольку вся структура является точечной симметричной), размер (0.707*diameter)^2 = 5000.
Самый близкий к ширине 70,7 - 70. В общем, я предлагаю точный результат (70.7) для числа ниже (70) и выше (75). Площадь прямоугольника составляет 70 * 71,41 = 4999. (Но было бы приятно знать, если высота также должна быть значением из вашей 5's сетки!)

Теперь это становится все более трудным и Я надеюсь, что я прав:
Как я пишу этот ответ, оказывается, я не прав. :-(округленные значения имеют более высокий результат, чем теоретический максимум, но я опубликую его независимо, может быть, это поможет найти реальный ответ.

Если у вас есть 2 прямоугольника, наибольшая площадь для покрытия должна быть когда

• углы rect1 находятся на 30 ° (150 °, 210 °, 330 °), а
• в углах от rect2 находятся на 60 ° (120 °, 240 °, 300 °) ,

Размеры будут:

• Rect 1: 0.866*dia * 0.5 *dia = 4330
• прямоугольник 2: 0.5 *dia * 0.866*dia = 4330 - минус перекрытие = >>0.5*0.36*dia^2 = 1830
• сумма: 6160

округляется до сетка 5:

• Rect 1, # 1) 85*52.86 = 4478
• прямоугольник 2: # 1) 50*(86.60-52.86) = 1696.2 # 2) 55*(83.52-52.86) = 1696.1 # 3) 45*(89.30-52.86) = 1648

• суммы: 6173.87 // 6173.75 // 6126

• Rect 1, # 2) 90*43.59 = 3923

• прямоугольник 2: # 1) 50*(86.60-43.59) = 2151 2 #) 55*(83.52-43.59) = 2196 3 #) 45*(89.30-43.59) = 2057
• суммы: 6074 // 6119 // 5980

победителя представляет собой комбинацию 1,1: rect1 = 85, rect2 = 50.

В связи с использованием округленные значения, вы должны проверить каждую комбинацию верхней и нижней (и точным, если он находится на сетка) каждого прямоугольника, в результате чего максимум 3^n проверяет, является ли n числом прямоугольников (кроме n = 1). Грубая сила не лучше, но, может быть, проще. (И как выяснилось и написано выше, возможно, он вернет лучшие результаты, так как этот метод является неточным).

EDIT 1: Формула 1 прямоугольника (что приводит к площади) составляет:

A = x * sqrt(D²-x²) 
calculate the maximum using the derivative of A: 
A' = D²-2x²/sqrt(D²-x²) = 0 

Вы также можете найти его здесь: http://oregonstate.edu/instruct/mth251/cq/Stage8/Lesson/rectangle.html

Формула 2 прямоугольников:

A = f(x,y) = x * sqrt(D²-x²) + y * [sqrt(D²-y²)-sqrt(D²-x²)] 
(x = width of r1, y = width of r2) 

Формула для n прямоугольников зависит от n неизвестных переменных. Поэтому вам нужно вычислить n частных производных. Повеселись!(Или рассмотреть перебор, как вы уже приведены сетки и не нужно делать итерации ;-))

Answer 2

перебором алгоритм

количество расчетов:

levels calculations 
1  19 
2  19 + 19*18 = 361 
... 
5  19 + 19*18 + 19*18*17 + 19*18*17*16 + 19*18*17*16*15 = 1494559 
... 
10  3.7e11 
15  6.3e15 
19  3.3e19 

C# (или C++):

double dDia = 100; 
int nSizes = 20; 
int nmax = 2; // number of rectangles 

int main() 
{ 
    int n = 1; 
    double dArea = 0.0; 

    dArea = CalcMaxArea (n, 0); 
} 

double CalcMaxArea (int n, double dSizeYParent) 
{ 
    double dArea = 0.0; 
    double dAreaMax = 0.0; 

    for (int iRun = nSizes-n; iRun >= 1; iRun--) 
    { 
    double dSizeX = iRun * 5; 
    double dSizeY = Math.Sqrt(dDia * dDia - dSizeX * dSizeX) - dSizeYParent); 
    double dAreaThis = dSizeX * dSizeY; 

    double dAreaOthers = 0.0; 
    if (n < nmax) 
     dAreaOthers = CalcMaxArea (n+1, dSizeY); 
    if (dArea > dAreaMax) 
     dAreaMax = dArea; 
    } 
} 

VBA, которые будут использоваться в MS Excel

Dim dDia As Double 
Dim nmax As Integer 
Dim nSizes As Integer 

Sub main() 

dDia = 100 
nmax = 2 
nSizes = 20 

Dim n As Integer 
Dim dArea As Double 

n = 1 
dArea = CalcMaxArea(n, 0) 

End Sub 

Function CalcMaxArea(n As Integer, dSizeYParent As Double) As Double 
    Dim dArea As Double 
    Dim dAreaMax As Double 
    dArea = 0 

    For iRun = nSizes - n To 1 Step -1 
    Dim dSizeX As Double 
    Dim dSizeY As Double 
    Dim dAreaThis As Double 
    Dim dAreaOthers As Double 

    dSizeX = iRun * 5 
    dSizeY = Sqr(dDia * dDia - dSizeX * dSizeX) - dSizeYParent 
    dAreaThis = dSizeX * dSizeY 

    dAreaOthers = 0 
    If n < nmax Then 
     dAreaOthers = CalcMaxArea(n + 1, dSizeY) 
    End If 
    dArea = dAreaThis + dAreaOthers 
    If dArea > dAreaMax Then 
     dAreaMax = dArea 
    End If 
    Next 

    CalcMaxArea = dAreaMax 
End Function 

Протестировано в VBA с заданными значениями, получило тот же результат: 6173.87.
Дополнительный код может быть добавлен, чтобы помнить, какие значения имеют максимально допустимый.

Answer 3

Я снова прочитал вопрос и понял, что полностью пропустил пару ключевых моментов в вашем посте. Картина смутила меня, но это не очень хорошее оправдание. Мое предыдущее предложение в комментариях было абсолютно плохим. Извините, и я надеюсь, вы не отправили много времени на это. Если бы мне пришлось решить эту проблему, я бы это сделал, правильно или неправильно.

Так что я думал об этой проблеме. Лучшее решение, о котором я могу думать, - использовать алгоритм поиска, такой как A *. A * его сам это довольно просто реализовать. Я предполагаю, что у вас уже есть метод расчета площади, которая мне кажется самой сложной. У меня есть идея, как я буду продолжать вычислять область перекрывающихся прямоугольников, но это причина, по которой я не писал программу, которая могла бы доказать, что мое предложение является хорошим.

Что бы я сделал, это иметь главный список всех потенциальных прямоугольников. Добавьте к своей границе копию всех прямоугольников, не находящихся в текущем пути, в качестве размещенного n-го прямоугольника. Это позволит вам установить ширину и, следовательно, рассчитать площадь круга, которую нужно заполнить. Сохраняя это, каждый раз выбирая путь с самой низкой стоимостью от границы, и после того, как будут исследованы узлы m, вы должны иметь наилучшее соответствие. Где m - общее количество прямоугольников, которые вы должны разместить.

Для оценки стоимости использование объема пространства для заполнения кажется естественным выбором. Одна вещь, чтобы отметить, однако, заключается в том, что площадь слева уменьшается с течением времени, и вам понадобится тот, который увеличивается. Я бы подумал, что разделение области, оставшейся на оставшееся количество прямоугольников, должно дать вам хорошую функцию затрат для поиска пути с наименьшей стоимостью до наименьшей площади, оставшейся в круге. Это звучит хорошо для меня, но я уверен, что есть и другие, которые можно использовать.

В отношении эвристики, без эвристической функции, у вас все еще есть лучший первый поиск, поэтому я ожидаю, что он будет работать лучше, чем метод слепой грубой силы. Имея хорошую эвристическую функцию, я ожидаю, что производительность значительно возрастет. Если подумать о том, что сделало бы хорошую эвристическую функцию, я подумал, что оценка количества круга, заполненного прямоугольником, может работать хорошо. Например, 10% площади прямоугольника делится на количество прямоугольников, оставшихся для размещения. Поскольку нет заранее заданного состояния цели, любая оценка должна основываться исключительно на области следующего прямоугольника. Мы знаем, что полная площадь прямоугольника не будет способствовать решению проблемы. Большинство каждого прямоугольника после первого пустого пространства, насколько решение идет, как я пришел с эвристикой. Как и функция стоимости, мне кажется разумной идеей, но если кто-то может подумать о лучшем, тем лучше.

Есть все виды сайтов на A *, но вот один, который выглядит хорошо написанным.http://web.mit.edu/eranki/www/tutorials/search/

Я надеюсь, что это поможет вам.

Answer 4

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

1. Определите максимальную ширину и высоту прямоугольника, которые можно прикрепить к кругу. Для этого существует множество решений. Например, посмотрите: Find Largest Inscribed Rectangle Этот прямоугольник затем завершит большую часть площади максимума.

2. Следующая задача - заполнить оставшуюся часть круга прямоугольником разного размера. Найдите подходящий прямоугольник, как показано на рисунке ниже. Это может быть сделано путем проверки, если точки окружности лежат внутри прямоугольника для заданной высоты и ширины

я снова согласен, что это очень трудно реализовать.