在半径r1=180的圆盘里，不重叠最多能放多少个半径r2=30的圆盘？

shamohu

转自：http://www.matlabsky.com/thread-12742-1-1.html

蛮有意思的题目。

bainhome

实际可以看作在半径为150的圆内，可以布置多少个点，这些点满足两个条件：
1.点总数小于36；
2.每个点和其他任意一个点之间的距离不小于60
这种条件在lingo中，印象里很好表示，很久没做过数学建模的题目，忘记了。在MATLAB中，这个问题比较麻烦，一来没有整数线规的官方命令，二来这种条件似乎也不是特别好写。
个人见解，不一定准确。

qibbxxt

1.可以用有限元三角剖分的思想去考虑，因为顶点间最好就是构成等边三角形
2.可以把1的结果作为初值，用lingo来写程序计算

bainhome

用没有最起码编程觉悟的方式，给出我的提示：
1.算法中也许需要体现这些边长大于等于60的等边三角形从外围向内扩展，这是因为充分利用外围空间优于里面空间的优化效果；
2.用AUTOCAD简单画了画，好像答案是27个，不知对否。

qibbxxt

b] 4# bainhome
老兄的思想真是灵活，算法才是王道了！
原来以为Lingo没有初值，很难计算的出来，谁知道9.0的全局优化很强悍
用下面的代码，直接以老兄的结果为初值，27个，可以计算出结果，但是28个，算了10分钟还是没有算出来，估计最优解应该是27个，从图形看也是，也许加上初值会不会有更好的结果，就不知道了。

1. 
   
2. model:
   
3. sets:
   
4. dot/1..27/:x,y;
   
5. link(dot,dot):;
   
6. endsets
   
7. data:
   
8. @text('x1.txt')=x;
   
9. @text('y1.txt')=y;
   
10. enddata
    
11. @for(dot(i):x(i)^2+y(i)^2<150*150);
    
12. @for(link(i,j)|i#ne#j:(x(i)-x(j))^2+(y(i)-y(j))^2>3600);
    
13. @for(dot:@free(x);@free(y));
    

复制代码

用Matlab验证并出图

1. 
   
2. clear;clc;close all
   
3. x=load('x1.txt');
   
4. y=load('y1.txt');
   
5. distofP=pdist([x,y]);
   
6. mindist=min(distofP);% check
   
7. t=linspace(0,2*pi);
   
8. r=30;
   
9. r1=180;
   
10. x0=repmat(x',length(t),1);
    
11. y0=repmat(y',length(t),1);
    
12. x0=bsxfun(@plus,x0,r*cos(t)');
    
13. y0=bsxfun(@plus,y0,r*sin(t)');
    
14. plot(x0,y0)
    
15. xx=cos(t)*r1;
    
16. yy=sin(t)*r1;
    
17. hold on
    
18. plot(xx,yy)
    
19. arrayfun(@(i)text(x(i),y(i),num2str(i),'HorizontalAlignment','center '),1:length(x))
    
20. axis equal
    

复制代码

AeroMusic

用没有最起码编程觉悟的方式，给出我的提示：
1.算法中也许需要体现这些边长大于等于60的等边三角形从外围向内扩展，这是因为充分利用外围空间优于里面空间的优化效果；
2.用AUTOCAD简单画了画，好像答案是27个，不 ...
bainhome 发表于 2011-1-13 11:39

来个搞一点的解题模式.


http://www.wolframalpha.com/input/?i=pack+r%3D30+circles+in+a+r%3D180+circle%3F

paradiseboy

有意思，下来查点资料，用MATLAB试试。

shamohu

延伸讨论：http://forum.simwe.com/thread-968275-1-1.html

yemaozi

qibbxxt 发表于 2011-1-13 15:33
b] 4# bainhome
老兄的思想真是灵活，算法才是王道了！
原来以为Lingo没有初值，很难计算的出来，谁知道9. ...

你好，能给个具体的过程吗，没试过你说的LINGO软件，谢谢