组合几何中的最优化问题

数学星空

我们知道对于组合几何中的问题很有趣,但的确很难,幸好现在非线最优化算法逐步发展起来...
一个老问题:在一个长为L正方形内可以放多少个单位圆?(圆彼此不能交叉)
这个问题好像有了答案,具体结果没有收集到

另一个问题:在一个2.1*100的长方形内可以放多少个单位圆?
(单位认为是1,单位圆直径为1)
这个可以利用坐标法得到一个优化方程问题设放入第i单位圆的坐标为x(i),y(i),
以长方形的左下角为原点,建立坐标系)
$| x(i)-x(k)|<=1 ( k=i+1,i+2,i+3,i+4 ,k<=n) $(因为每个圆相邻的圆最多为4个)

$ |y(i)-y(k)|<=1 (i=1....n)$

$  1<=x(i)<=100 $

$1<=y(i)<=2.1$

$(x(i)-x(k))^2+(y(i)-y(k))^2>=1$

求n最大值?

wayne

让我想到了难度更大的开普勒猜想，sphere-packing problem。

还想到了project Euler 第222题也与这相关，
http://projecteuler.net/index.php?section=problems&id=222

数学星空

呵,开普勒猜想的完整证明已经被科学界接受了...
篇幅太长,不是专业人士是很难看明白的...

数学星空

用CAD 画了一下,只画出211个圆,见附图
不知最优答案是多少...

wayne

一般说的单位圆都是指半径为1的

数学星空

呵呵,所以我另外说明了一下,这与理解解题没有太大关联...

winxos

一个2.1*100的长方形内可以放多少个单位圆?
立起来之后是否靠重力能够得到最优解呢？
感觉这类问题复杂了还是要靠模拟来做。

数学星空

呵,"靠重力能够得到最优解"??是重力实验?
对于这类最优化问题,一般采用遗传算法....等一些智能的算法,才能在比较短的时间内得到比较好的答案

winxos

呵,"靠重力能够得到最优解"??是重力实验?
对于这类最优化问题,一般采用遗传算法....等一些智能的算法,才能在比较短的时间内得到比较好的答案
数学星空 发表于 2009-11-18 08:14

是这样的，将圆考虑成有重量的物体，将容器竖立放置，靠圆的重力实现自动平衡，
我感觉很有可能解会比较优，
因为前段时间看到一个类似的问题，就是工厂车间选址问题，书上说目前没有合适的解法，最好的方法一般是转换成物理模型来自动平衡。
-----------------
就这个题目我看看我能编个模拟的程序不。

风云剑

一个个的放，放的时候使重力势能最小？