一道算法题，求解

一个农夫在一块长x宽y的矩形田地上放牧n头奶牛（n≤25），它们互相之间非常仇视，所以都希望离其它奶牛尽量远，它们有自己的标准，就是离其它奶牛的距离的倒数越小越好，因为农夫想让它们尽量高兴，所以他必须找到一种使所有奶牛之间的距离的倒数和尽量小的方案，请你编程为农夫找到这种方案。
输入：x,y,n
输出：n头奶牛的坐标

49 个解决方案

#1

自己UP

#2

顶一下

#3

好难啊

#4

用lingo语言求解去

#5

Mark

#6

mark!!!

#7

UP

#8

这是什么算法哦，不懂

#9

UP

#10

MARK!!

#11

晕，好难

#12

       面积 /  牛的头数  = 这个面积内相互内切的圆的个数   

#13

 这样能够保证各头牛之间距离的倒数之和为最小值吗？

#14

不用问，绝对是距离相等的时候。

这是广义绝对不等式决定的。

高中数学的东西。

#15

(1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2  =>
(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn);
又r1+r2+...rn<=根号下n*(r1^2+r2^2+....rn^2);
=>(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+...rn)>=n^2/(根号下(n*(r1^2+r2^2+....rn^2)))
取等号的条件是：r1=r2=,,,,,=rn;
具体用到了数学中的一个重要不等式 柯西不等式
其原型为：
(a1*b1+a2*b2+.....an*bn)^2<=(a1^2+a2^2+,,,,an^2)*(b1^2+b2^2+,,,,bn^2);
本式取等号的条件是：a1/b1=a2/b2=,,,,,=an/bn;

有了理论依据 剩下的就是找出各个圆的圆心坐标了

#16

以各头牛的坐标为圆心做半径相同的且互相切的圆，应该是这样的

#17

就是要任何一头牛与其它牛的距离都相等？　这在平面上是画不出来的

#18

这题不知道用遗传算法能不能解

#19

引用 4 楼 phil1984 的回复:

用lingo语言求解去

人家是要算法
不是要结果啊...
我觉得这题如果不加上一个精度限制
就算用电脑 也要算很久的

#20

学习

#21

设输入的点位(x1,y1),(x2,y2),...,(xn,yn)
则要求1/sqrt((xi-xj)^2+(yi-yj)^2)对所有的i!=j求和后极小，限制条件为每个点都在矩形内
可以看成一个多元函数f(x1,y1,x2,y2,...,xn,yn)求极小值的问题
看以参照任意一本数学分析书中多元函数极小值的部分求解

有一点值得欣喜的是
求解过程要对每个变量求一次倒数，假设对xi求导，那么df/dxi中只有变量xj,yi,yj，其他变量都变成0项了
不过最后解方程的时候还是有点困难

#22

引用 15 楼 shanpobaiyang 的回复:

(1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2  => 
(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn); 
又r1+r2+...rn <=根号下n*(r1^2+r2^2+....rn^2); 
=>(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+...rn)>=n^2/(根号下(n*(r1^2+r2^2+....rn^2))) 
取等号的条件是：r1=r2=,,,,,=rn; 
具体用到了数学中的一个重要不等式 柯西不等式 
其原型为： 
(a1*b1+a2*b2+.....an*bn)^2 <=(a1^2+a2^2+,,,,an^2)*(b1^2+b2^2+,,,,bn^2); 
本式取等…

没看明白啊

#23

引用 14 楼 hikaliv 的回复:

不用问，绝对是距离相等的时候。 

这是广义绝对不等式决定的。 

高中数学的东西。

支持下这个，这个应该正确的了！！

#24

所有奶牛之间的距离的倒数和 ？ 一共是 C(n,2) 个距离吗？

#25

引用 23 楼 zbihong 的回复:

引用 14 楼 hikaliv 的回复: 
 不用问，绝对是距离相等的时候。  
  
 这是广义绝对不等式决定的。  
  
 高中数学的东西。 
  
 支持下这个，这个应该正确的了！！

不对，

你试试平面上找4各点，使得两两之间距离相等！

但直观上肯定是“均匀分布”。

#26

UP

#27

引用 22 楼 sunnyplain 的回复:

引用 15 楼 shanpobaiyang 的回复:
(1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2  => 
(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn); 
又r1+r2+...rn <=根号下n*(r1^2+r2^2+....rn^2); 
=>(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+...rn)>=n^2/(根号下(n*(r1^2+r2^2+....rn^2))) 
取等号的条件是：r1=r2=,,,,,=rn; 
具体用到了数学中的一个重要不等式 柯西不等式 
其原型为： 
(a1*b1+a2*b2+.....an*bn)^2 <=(a1^2+a2^2+,,,,an^2…

看一下这个吧：[img=http://www.namipan.com/d/b6eb74dbd87fb90613d5c91681da74db03e754a3bced0000][/img]
取等号的条件是相等

#28

呃，看高手的解答

#29

引用 27 楼 shanpobaiyang 的回复:

引用 22 楼 sunnyplain 的回复: 
 引用 15 楼 shanpobaiyang 的回复: 
 (1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2  =>  
 (1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn);  
 又r1+r2+...rn  <=根号下n*(r1^2+r2^2+....rn^2);  
 =>(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+...rn)>=n^2/(根号下(n*(r1^2+r2^2+....rn^2)))  
 取等号的条件是：r1=r2=,,,,,=rn;  
 具体用到了数学中的一个重要不等式 柯西不等式  
 其原型为：  
 (a1*b1+…

一点疑惑： 两个函数， f(),g(),对于同一个输入x, f(x)>=g(x),等号成立当且仅当x=x0。
然而，这一点并不能直接保证f(x0)<=f(x)，对于任意的x。
换句话讲，x=x0 可以使f-g最小化，但并不一定使f本身最小化。

第二点疑惑：平面上不可能找出多于4个点，使得两两之间距离相等。


直观的感觉是：让n个点“均匀分布"在矩形内。不过我也不知道怎么严格定义，严格实现。

胡乱两个想法：

1）转换成统计量去算，考虑”均匀分布的特性“

2）如果精度要求不太高的话，让n个点从矩形中心随机散开，（有点像模拟分子扩散）。
不过每一次随机游走要满足一个条件: 使得目标函数变小。 如此运行下去，系统会达到平衡点，
也就是，目标函数达到最小值，所有点停止游走。不过这种算法计算量太大了，（估计得变步长），
而且什么时候能达到平衡点也是个问题。



期待optimization的牛人出现。

#30

引用 15 楼 shanpobaiyang 的回复:

(1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2  => 
(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn); 
又r1+r2+...rn <=根号下n*(r1^2+r2^2+....rn^2); 
=>(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+...rn)>=n^2/(根号下(n*(r1^2+r2^2+....rn^2))) 
取等号的条件是：r1=r2=,,,,,=rn; 
具体用到了数学中的一个重要不等式 柯西不等式 
其原型为： 
(a1*b1+a2*b2+.....an*bn)^2 <=(a1^2+a2^2+,,,,an^2)*(b1^2+b2^2+,,,,bn^2); 
本式取等号的条件…

n^2  => 
(1/r1+1/r2+....+1/rn)
如果每个ri都小于1，等式就不成立了

另外，只给出了结果是r1=r2=...=rn，但怎么求各个点却没说

#31

引用 30 楼 sunnyplain 的回复:

引用 15 楼 shanpobaiyang 的回复:
(1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2  => 
(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn); 
又r1+r2+...rn <=根号下n*(r1^2+r2^2+....rn^2); 
=>(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+...rn)>=n^2/(根号下(n*(r1^2+r2^2+....rn^2))) 
取等号的条件是：r1=r2=,,,,,=rn; 
具体用到了数学中的一个重要不等式 柯西不等式 
其原型为： 
(a1*b1+a2*b2+.....an*bn)^2 <=(a1^2+a2^2+,,,,an^2…

对于每个ri都小于1的话，不等式仍然是成立的，最终化简出来的结果是1/r1+1/r2+....+1/rn>=根号下[n^3/(r1^2+r2^2+....+rn^2)]，你可以找个具体数值再验证一下；
有了上面的依据，问题也就转化为如何在一个已知矩形内画出n个面积相等，相互外切的圆；到了这里就是问题的关键了，期待！！！

#32

好难啊```

#33

引用 31 楼 shanpobaiyang 的回复:

对于每个ri都小于1的话，不等式仍然是成立的，最终化简出来的结果是1/r1+1/r2+....+1/rn>=根号下[n^3/(r1^2+r2^2+....+rn^2)]，你可以找个具体数值再验证一下； 
有了上面的依据，问题也就转化为如何在一个已知矩形内画出n个面积相等，相互外切的圆；到了这里就是问题的关键了，期待！！！

不正确的推导过程，得出一个正确的结论！。。。
另外这个问题难就难在怎么求出那些圆的圆心

#34

引用 27 楼 shanpobaiyang 的回复:

看一下这个吧： 
取等号的条件是相等

那张图看不到啊

#35

引用 33 楼 sunnyplain 的回复:

不正确的推导过程，得出一个正确的结论！。。。 
另外这个问题难就难在怎么求出那些圆的圆心

哪地方出错了
步骤我写的不是很调理
但是方法是没有错的
另外补充一点，就是不用柯西不等式的话，用凸函数的性质同样是可以证出上面的结论的。

#36

引用 34 楼 sunnyplain 的回复:

引用 27 楼 shanpobaiyang 的回复:
看一下这个吧： 
取等号的条件是相等 
那张图看不到啊

你到百度搜一下柯西不等式，对可以看明白上边的推理过程了

#37

引用 35 楼 shanpobaiyang 的回复:

哪地方出错了 

我在30楼有写啊

#38

引用 37 楼 sunnyplain 的回复:

引用 35 楼 shanpobaiyang 的回复:

哪地方出错了 
 

我在30楼有写啊

我在36楼不是说过了吗！
小于1的时候仍然是成立的

#39

不好意思，有点看错

不过这个不等式
n^2  => (1/r1+1/r2+....+1/rn) 

在r1,r2,...,rn都小于1/n的时候是不成立的

#40

引用 33 楼 sunnyplain 的回复:

引用 31 楼 shanpobaiyang 的回复: 
 对于每个ri都小于1的话，不等式仍然是成立的，最终化简出来的结果是1/r1+1/r2+....+1/rn>=根号下[n^3/(r1^2+r2^2+....+rn^2)]，你可以找个具体数值再验证一下；  
 有了上面的依据，问题也就转化为如何在一个已知矩形内画出n个面积相等，相互外切的圆；到了这里就是问题的关键了，期待！！！ 
  
  
 不正确的推导过程，得出一个正确的结论！。。。 
 另外这个问题难就难在怎么求出那些圆的圆…

你的意思是，那些圆心就是要求的点么？ 可是有些圆并不一定要全部落在矩形内吧。最后结果必然是有些牛落在边界上，要不然
我们就没有充分利用这个矩形。
换句话，假设已经求出这样n个点，考虑它们的凸包，如果凸包上的点不在矩形边界上，总可以把那些点往边界方向上挪一挪，
使得这个点和其他所有点距离变大。

#41

引用 39 楼 sunnyplain 的回复:

不好意思，有点看错 

不过这个不等式 
n^2  => (1/r1+1/r2+....+1/rn) 

在r1,r2,...,rn都小于1/n的时候是不成立的

你没有看懂我上面写的推导过程
写的有些乱
我在重新写一下吧！
具体用到了数学中的一个重要不等式 柯西不等式 
其原型为： 
(a1*b1+a2*b2+.....an*bn)^2 <=(a1^2+a2^2+,,,,an^2)*(b1^2+b2^2+,,,,bn^2); 
本式取等号的条件是：a1/b1=a2/b2=,,,,,=an/bn; 
由柯西不等式可得：
(1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2；
从而(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn); 
又由柯西不等式得：r1+r2+...rn <=根号下n*(r1^2+r2^2+....rn^2); 
所以(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+...rn)>=n^2/(根号下(n*(r1^2+r2^2+....rn^2))) 
最终得：1/r1+1/r2+....+1/rn>=根号下[n^3/(r1^2+r2^2+....+rn^2)]；
注意观察r1^2+r2^2+....+rn^2的值一定小于定值x*y/π的，所以上式取最小值式是r1=r2=r3=,,,,,=rn;

#42

引用 40 楼 shex4 的回复:

你的意思是，那些圆心就是要求的点么？ 可是有些圆并不一定要全部落在矩形内吧。最后结果必然是有些牛落在边界上，要不然 
我们就没有充分利用这个矩形。 
换句话，假设已经求出这样n个点，考虑它们的凸包，如果凸包上的点不在矩形边界上，总可以把那些点往边界方向上挪一挪， 
使得这个点和其他所有点距离变大。

说的对！

#43

UP

#44

学习啦。

#45

无约束最优化问题，有好几种方法

#46

引用 15 楼 shanpobaiyang 的回复:

(1/r1+1/r2+....+1/rn)(r1+r2+....rn)>=n^2  => 
(1/r1+1/r2+....+1/rn)>=n^2/(r1+r2+....rn); 

哦！非常抱歉！
把上面行“=>”，看成“>=”了

#47

UP

#48

我是来 学习的``呵呵`

#49

模拟退火啥的。。。
。
那个不等式什么的应该和这题无关。。