![enter image description here](https://istack.dev59.com/GOne1.webp)
是否有任何算法可以让我制定结果?
为什么这个问题的暴力攻击会很困难?你只需要在计算代码中付出一些努力,我相信它会正常工作。最多只有19个级别。这不应该太复杂,并且将在...嗯,几个小时内给出结果,就像我刚刚发现的那样。19个级别将导致3.3e17次计算。
关于算法:
使用一个矩形时,当矩形是正方形时,可以获得最大的覆盖面积。我认为这非常容易理解。正方形的角位于圆心的45°处(假设水平为0°,但实际上整个结构都是点对称的),大小为(0.707*直径)^2 = 5000
。
最接近宽度70.7的是70。通常建议检查精确结果(70.7)下面(70)和上面(75)的数字。您的矩形的面积为70 * 71.41 = 4999。(但是如果高度也必须是5格网格之一的值,那就太好了!)
现在变得更困难了,希望我是对的:
当我写这个答案时,事实证明,我是不对的。:-( 四舍五入的值比理论最大值要高。但我会发表它,也许有助于找到真正的答案。
当您有两个矩形时,应该覆盖的最大区域是
尺寸应为:
0.866*dia * 0.5 *dia = 4330
0.5 *dia * 0.866*dia = 4330
- 减去重叠部分 =>> 0.5*0.36*dia^2 = 1830
6160
四舍五入到5的网格:
85*52.86 = 4478
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
矩形1,#2)90*43.59 = 3923
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外)。暴力搜索并不美观,但可能更容易。 (正如上面发现和写的那样,这种方法可能会返回更好的结果,因为该方法不准确)。
编辑1: 一个矩形(结果为正方形)的公式为:
A = x * sqrt(D²-x²)
calculate the maximum using the derivative of A:
A' = D²-2x² / sqrt(D²-x²) = 0
A = f(x,y) = x * sqrt(D²-x²) + y * [sqrt(D²-y²)-sqrt(D²-x²)]
( x = width of r1, y = width of r2 )
暴力算法
计算量:
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。
可以添加进一步的代码来记住达到最大值的值。
我再次阅读了您的问题,并意识到我在您的帖子中完全错过了几个关键点。图片让我感到困惑,但这并不是一个好借口。我之前在评论中提出的建议完全是个坏主意。我很抱歉,希望您没有花费太多时间研究它。如果我必须解决这个问题,这就是我会做的,对或错。
所以我一直在思考这个问题。我能想到的最好的解决方案是使用搜索算法,如A*。A*本身实现起来相当简单。我假设您已经有了计算面积的方法,这对我来说似乎是最难的部分。我有一个关于计算重叠矩形面积的想法,但这也是我没有编写可以证明我的建议是好的程序的原因。
我会有一个包含所有潜在矩形的主列表。将所有不在当前路径中的矩形的副本作为第n个放置的矩形添加到您的frontier中。这将允许您设置宽度,从而计算剩余要填充的圆的面积。继续这样做,每次从frontier中选择最低成本路径,并在探索m个节点后,您应该得到最佳拟合。其中m是您必须放置的矩形的总数。
对于成本评估,使用剩余填充空间的数量似乎是一个自然的选择。但需要注意的一点是,剩余区域会随着时间的推移而减少,因此您需要一个增加的区域。我认为将剩余区域除以剩余矩形的数量应该可以给您一个很好的成本函数,以找到在圆中留下最少面积的最低成本路径。这个听起来对我来说不错,但我相信还有其他可用的方法。
关于启发式,如果没有启发式函数,您仍然拥有最佳优先搜索,因此我预计它的性能要比盲目的蛮力技术更好。通过一个良好的启发式函数,我预计性能将显著提高。在思考什么样的启发式函数会更好时,我认为估计矩形填充圆的面积可能效果很好。例如,矩形面积的10%除以剩余放置的矩形数。由于没有预先确定的目标状态,任何估计都必须仅基于下一个矩形的面积。我们知道矩形的全部面积不会对解决方案产生贡献。每个矩形之后的大部分都是浪费空间,这就是我提出这个启发式的原因。与成本函数一样,对我来说这似乎是一个合理的想法,但如果有人能想到更好的方法,那就更好了。
网络上有各种关于A*的网站,但这个看起来写得很好。http://web.mit.edu/eranki/www/tutorials/search/
希望这能帮到你。
我知道设计一个可行的算法是很复杂的,但这是我想到的方法: 在给定直径的圆中,只能有一个矩形占据最大面积。
找出适合放入圆中的矩形的最大宽度和高度。有很多解决方案。例如,请参考:查找最大内接矩形。该矩形将占据最大面积的主要部分。
接下来的任务是用不同大小的矩形填充圆的剩余部分。如下图所示,找到最佳匹配的矩形。这可以通过检查圆点是否位于指定高度和宽度的矩形内来完成。
我再次同意这很难实现。