组合几何中的最优化问题

数学星空

我们知道对于组合几何中的问题很有趣,但的确很难,幸好现在非线最优化算法逐步发展起来... 一个老问题:在一个长为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

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

风云剑

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