猪流感的数学问题

lsbbox

我想问的问题其实是怎样在一个密闭空间中让N个点尽量散开。用猪流感举例。猪流感流行，N个人在一个房间里，为了不互相传染，每个人都想离别人远些，问这些人怎么分布？
“尽量分散”这个描述怎么转换成数学描述是个问题，我目前想到两种描述：1)N个点间两两距离中最小值，为最大。2)N个点间两两距离，求和，结果为最大。
我目前用了一个简单的数值解法。把空间平均划分成很多离散的小格子。先在正方形角上放一个A点。然后遍历所有小格子，按照1的要求找到最适合的点B。再用同样的方法找点C，一直这样放完N个点。这个方案很简陋，得到的解很不精确。还有一种得到近似数值解的方法是，当N很大时，忽略边界，则问题大大简化，点均匀分布，只需要用面积除以N就是每个点拥有的面积。但是点是呈三角形还是正方形排列呢？而且这种算法在点个数少的时候就不能用了。
目前我貌似想到了一个数学解的方法。首先要给点之间定义影响力，影响力跟是距离的函数F(r)。比如仿照电荷力，定义斥力和距离平方成正比。这样带电粒子在密闭空间的静止稳定态就是一个解。貌似这样就变成跟三体问题有点象了。不过我们这个N体问题是静止情况，粒子不能自由运动，在空间中有阻尼存在，时间趋于无穷时才能达到静止稳定态。这个问题怎么解？
问题最终要扩展到三维，甚至N维。边界形状不固定。
请指教！[br][br]-=-=-=-=- 以下内容由 lsbbox 在 时添加 -=-=-=-=-
纠正一下我主贴里的命题2，“各点之间距离总和最大”可能不符合实际情况。还是应该定义为“两点间影响力跟距离平方成反比，求影响力之和最小的分布情况”，这样比较吻合实际应用。例如考虑1维情况，A、B两点占据线段两端，这时插入C，如果按照“各点之间距离总和最大”，则C插在AB间任意位置都是一样的。但ABC三点无论是电荷，猪流感患者，垃圾堆，核电站。。。显然都应该把C放在AB的中点。
然后我也说一下我的实际应用吧。我目前要解决的问题是选色问题。要求选出的N种颜色尽量不相似。我用RGB色彩空间模型，因此是一个三维立方体里的分散问题。

lsbbox

再进一步扩展，F(r)可以是任意形式。

lsbbox

这个问题很难吗？没有人有点思路吗？[br][br]-=-=-=-=- 以下内容由 lsbbox 在 时添加 -=-=-=-=-
我想了一下，这个问题跟电荷分布的情况是相同的。两点间影响力跟距离平方成反比，求影响力和最小的分布情况

wangyangke

  
    个人观点：这是个域内格点问题；n个皆处在格点中央；在平面或曲面，对给定区域按n分格；在空间或球体，亦按n分成单位体积；类乎整点问题；

技术员

下面引用由lsbbox在 2009/07/14 00:57pm 发表的内容： 我想问的问题其实是怎样在一个密闭空间中让N个点尽量散开。用猪流感举例。猪流感流行，N个人在一个房间里，为了不互相传染，每个人都想离别人远些，问这些人怎么分布？
“尽量分散”这个描述怎么转换成数学描 ...

你必须将房间的形状定下来，园或方。

技术员

可看看陆教授的大圆包小圆问题作为命题参考。

luyuanhong

如果 N 很大，我们只想得到一个近似解，那还是很容易的。

wangyangke

[这个贴子最后由wangyangke在 2009/07/15 09:27am 第 1 次编辑]

    妙！请教luyuanhong 老师，如此摆布，如何推广到空间？

luyuanhong

[这个贴子最后由luyuanhong在 2009/07/15 10:09am 第 1 次编辑]

注意：问题要求的是“各点之间距离的最小值达到最大”。
在按照正方形格点排列的情况下，各点之间距离的最小值，不是正方形的对角线，而是正方形的边长。
将正方形的边长与按照正三角形排列时各点之间的距离相比，正方形排列的距离就不如正三角形排列的距离了。
如果不是用是用“各点之间距离的最小值达到最大”作为标准，而是用“各点之间距离总和最大”作为标准，楼上的做法也是不对的。
因为算总和时，“各点之间的距离”不仅是相邻点之间距离，还要考虑更远点之间的距离，区域中所有的点两两之间的距离都要算进去。
其实，即使用“各点之间距离总和最大”作为判断标准，正方形格点排列也是不如正三角形格点排列的。

lsbbox

首先非常感谢各位的讨论，我不是数学专业，甚至算不上数学爱好者，只是个程序员，这个问题我一个人憋了好几天了，终于得到些专业意见
@技术员,目前暂且考虑正方形的房间。其实圆形也需要求（会不会太贪心） PS,我也是成都的，呵呵
@luyuanhong，您的这个算法我也考虑到了，确实蜂窝状是个很好的排列。遗憾的是实际应用中N数值不大是很常见的情况，比如不到10。这种情况下就不能应用蜂窝状分布了。
另外我想纠正一下我主贴里的命题2，“各点之间距离总和最大”可能不符合实际情况。还是应该定义为“两点间影响力跟距离平方成反比，求影响力之和最小的分布情况”，这样比较吻合实际应用。例如考虑1维情况，A、B两点占据线段两端，这时插入C，如果按照“各点之间距离总和最大”，则C插在AB间任意位置都是一样的。但ABC三点无论是电荷，猪流感患者，垃圾堆，核电站。。。显然都应该把C放在AB的中点。
然后我也说一下我的实际应用吧。我目前要解决的问题是选色问题。要求选出的N种颜色尽量不相似。我用RGB色彩空间模型，因此是一个三维立方体里的分散问题。[br][br]-=-=-=-=- 以下内容由 lsbbox 在 时添加 -=-=-=-=-
不过我的应用里有需求要放弃鲜艳的颜色，因此立方体顶点附近的颜色不要，只要立方体大圆内的颜色。这样就是球体里的分散问题。