组合几何中的最优化问题
本帖最后由 数学星空 于 2009-11-5 12:23 编辑我们知道对于组合几何中的问题很有趣,但的确很难,幸好现在非线最优化算法逐步发展起来...
一个老问题:在一个长为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最大值? 让我想到了难度更大的开普勒猜想，sphere-packing problem。
还想到了project Euler 第222题也与这相关，
http://projecteuler.net/index.php?section=problems&id=222 呵,开普勒猜想的完整证明已经被科学界接受了...
篇幅太长,不是专业人士是很难看明白的... 本帖最后由 数学星空 于 2009-11-6 11:46 编辑
用CAD 画了一下,只画出211个圆,见附图
不知最优答案是多少...
一般说的单位圆都是指半径为1的 呵呵,所以我另外说明了一下,这与理解解题没有太大关联... 一个2.1*100的长方形内可以放多少个单位圆?
立起来之后是否靠重力能够得到最优解呢？
感觉这类问题复杂了还是要靠模拟来做。 呵,"靠重力能够得到最优解"??是重力实验?
对于这类最优化问题,一般采用遗传算法....等一些智能的算法,才能在比较短的时间内得到比较好的答案 呵,"靠重力能够得到最优解"??是重力实验?
对于这类最优化问题,一般采用遗传算法....等一些智能的算法,才能在比较短的时间内得到比较好的答案
数学星空 发表于 2009-11-18 08:14 http://bbs.emath.ac.cn/images/common/back.gif
是这样的，将圆考虑成有重量的物体，将容器竖立放置，靠圆的重力实现自动平衡，
我感觉很有可能解会比较优，
因为前段时间看到一个类似的问题，就是工厂车间选址问题，书上说目前没有合适的解法，最好的方法一般是转换成物理模型来自动平衡。
-----------------
就这个题目我看看我能编个模拟的程序不。 一个个的放，放的时候使重力势能最小？
页:
[1]
2