一个来自实践的算法难题(300分)

gofor · 2002-10-11

N个数的递增整数序列,其第一个数为1,且序列中任意两个整数的差均不相同。求第N个数(也就是最大数)最小时的序列。
问题的背景
　　搞通信的del_c_sharp兄从频率分配中提取的数学模型。在同一通信信道中，所使用的频率的差不能相同，而使用的带宽要尽可能小。现在需要36个这样的频点！
以下是先前的讨论
http://www.csdn.net/Expert/TopicView1.asp?id=934268
http://www.csdn.net/Expert/TopicView1.asp?id=931488
http://www.csdn.net/Expert/TopicView1.asp?id=954026
http://www.csdn.net/Expert/TopicView1.asp?id=1007608
经过大家的努力：
对于N＝36，目前的最佳结果是（by intfree）：
1 11 100 128 148 157 161 178 192 230 262 318 330 385 401 425 427 428 450 504 543 628 633 639 719 764 782 915 923 974 981 1027 1068 1087 1102 1149
对于N＝3到N＝16，目前已求出最优解，依次为
1 3 4
1 3 6 7
1 3 8 11 12
1 6 8 14 17 18
1 3 8 16 22 25 26
1 3 13 20 26 31 34 35
1 4 10 18 20 33 40 44 45
1 3 15 22 30 33 46 50 55 56
1 3 9 19 26 40 45 60 69 72 73
1 10 11 18 31 43 46 57 62 80 84 86
1 8 9 18 22 37 48 64 70 82 102 105 107
1 6 29 39 42 50 51 69 76 93 108 122 124 128
1 7 8 16 29 41 52 76 90 93 95 122 132 148 152
1 10 15 28 44 61 63 102 110 122 146 152 167 174 177 178
300分送给最先求出N＝17的最优解，或求出N＝36的更优解者（最大数＜1149）。

creation-zy · 2002-10-11

这和我去年解决的一问题很相似——十个自然数两两相加不等，求满足此条件的解中最小
的解。
http://www.delphibbs.com/delphibbs/dispq.asp?lid=0479090
http://www.delphibbs.com/delphibbs/dispq.asp?lid=0483016
(如果看不见，可以在离线数据库中查找)
有趣...

rustle · 2002-10-11

gz
我看需要很强的数学知识
把这个模型进一步抽象出来才可以

gofor · 2002-10-11

to creation-zy
　　一个是两两之差不等，一个是两两之和不等，问题确实相似。
　　但我的问题的关键是规模太大，我用穷举法搜索N＝16时的最优解，耗时6个多小时，
CPU是P4　1.5G。这是在对程序进行N次优化之后取得的成绩，此前有人用1天半的时间搜
索出N＝14时的最优解，而我现在的程序搜索N＝14的最优解，只要100多秒。参见我前面
给出的链接。
　　但随着N的增大，穷举的时间成指数增长，搜索N＝17（目前的最好结果是211，但不
知是否最优），已不从心，因此寻求大富翁的帮助。这是我首次在此发帖。

creation-zy · 2002-10-11

CSDN上的帖子已经看过了——高手太多了！想当年我最开始计算N=10就花了数千秒...
看来关键还是要在数学理论上深入才行。

gofor · 2002-10-11

是呀。
我也看了大富翁讨论“10个数两两相加不等”的帖子，讨论很热烈。并且发现我们的讨论
存在很多有趣的相似之处，比如顺推或倒推、固定两端或一端变动、穷举时找更多更强的
约束条件。
但你们的算法在以下几点上存在优化的潜力：
1、序列对偶性的应用：
如果a1,a2,...,an是满足条件的序列，则an-a1,an-a2,...,an-an也是满足条件的序列。
我把称为对偶性。你们发现了而没有用到它。实际上，我们只要找出最优解对偶序列中
的一个序列就行了，因此可规定序列前半部分小于后半部分，即a[n/2]<a[n]。这个简
单的约束条件，仅在n=13时，就可提高5倍的速度。
2、和值集合的表示：
集合运算是方便的，但是很慢。因为判断一个元素是否在集合中时，要逐个元素比较。
可以采用布尔数组来记录已经用过的和值，假设S是用过的和值，则令b=true。这样
判断一个和值是否用过，只须一次比较。
　　另外，我在求“两两之差不相同”的集合时，搜索过程中，假设已求到第i个元素，
还有n+1-i个元素待定，如果发现剩下未用的最小的n+1-i个差值之和已不能求出更优解，
即中止。这个约束条件，也可提高速度几倍，不知用于求“两两之和不相同”的集合的
效率如何。

温柔一刀 · 2002-10-11

呵呵，又在讨论这个问题了
我前一段出差的时候恰好看到CSDN上面这个帖，想起以前的事情
就把算法改造了一下，改为计算两两之差不相等，然后又优化了一通，
就当是无聊消磨时间了。。。：）
实际上，再怎么优化有什么意义呢？只要是穷举法，
时间复杂性明显是指数级的，N=36大约花多少时间，根据前面
各层之间的时间比，应该能估计出来了，根本是天文数字。
我个人的想法，你开头已经说得很明白了，这是个来自实践的问题，
就应该用实践中的办法解决：不必找什么“最优解”，问题本身
只是要尽可能小而已，以后有了好算法，找到更新的序列就是了。。。
因此“正道”就是在CSDN后来那样，使用各种手段来缩减最大值，
当然最好是有数学的理论基础，例如intfree给出的方法，一下子
缩减了那么多，不是任何算法优化可以实现的。
ps: gofor，你大概没有好好看大富翁上那几个帖子，我们应用的算法
很多地方都有优化，包括你说的对偶性，那种优化不可能不作的，
你大概没看出来。另外，那时候我已经把基于集合的方法改为基于数组了，
集合的问题并不在于慢，而在于计算的数字不能大于256，因此对于较大的n
毫无作用。不过由于觉得这个问题意义已经不大，就没再贴。
还有，你前面写的a[n/2]<a[n]，大概明显是笔误，不知你原意是指什么
见笑了~

gofor · 2002-10-12

对，手误，应该是a[n/2]<a[n]/2。其他的等会儿再讨论。

gofor · 2002-10-12

我只阅读了creation-zy给出的两个链接，而且由于内容不能显示（虽然我用的是IE6），
我是用查看网页源文件的方法进行阅读的，里面夹杂很多HTML标记，看起来比较费劲，所
以看得不够仔细，见谅。
1、关于对偶性的应用。我刚才重新阅读了原来的帖子，确实得到了应用。只是没有区分n
的奇偶性，若n=2k+1,则a[k+1]-a[1]<a[n]-a[k+1]；若n=2k,则a[k]-a[1]<a[n]-a[k+1]。
如此，对于n为偶数时有较大的速度提高。creation-zy最后的算法我没有看到，但利用n
较小时的结果与我的算法一样。
2、关于和集的表示。我没有做过测试，如果你的实验表明采用PASCAL的集合运算，速度
不受影响，那么可以肯定PASCAL编译程序对集合元素的表示就是用布尔数组来实现的，这
也可以解释为什么PASCAL规定集合元素的类型必须是有序类型。
3、关于进一步优化算法的意义。我总是怯于谈意义，对这个问题的关注仅仅因为兴趣。
算法上一点小小的改进，速度上一点小小的提高，就使我感到高兴。也许我是个完美主
义者。

4、对于n=36，用现在的穷举法求出最优解是不可能的。但我希望能讨论出某些规律，用
更有效率的方法搜索出更好的结果来，比如在概率较高的组合中进行搜索，或者用某种高
效的构造法。对于较小的n，我希望通过改进算法，求出最优解。
　　因此奉送300分给最先求出n=17的最优解，或n=36的更优解。如果觉得分数太小，我
总共1800分，全部奉送。
　　由于经过许多人的努力，再有突破很困难。我可以降低要求，如果某人能把我现在的
算法提速20%，即送300分。我的算法请看前面的链接。

温柔一刀 · 2002-10-12

对，我就猜到你是想写a[n/2]<a[n]/2，其他的等会儿再讨论

这无疑是正确的，可是你看看你前面给出的n=3~16的序列，
没有一个符合此不等式，为什么呢？因为他们恰好求出了那个“对偶解”，
那个算法是什么呢？谁写的呢？

gofor · 2002-10-12

算法是我写的，是反向求的。C++Builder 5
#include <vcl.h>
#pragma hdrstop
#pragma argsused
#include <iostream.h>
const int maxn=36;
const n=13;
int a[10000];
int b[maxn]={1};
int d[maxn]={1,2,4,7,12,18,26,35,45,56,73,86,107,128,152,178};
int c[maxn]={1,2,4,7,12,18,26,35,45,56,73,86,107,128,152,178};
bool found=false;
int t;
void FoundOne()
{
int i,j;
for (j=0;
j<n;
j++) cout<<b[j]-b[0]+1<<' ';
cout<<endl;
for (j=1;
j<n;
j++) cout<<b[j]-b[j-1]<<' ';//差值序列
cout<<endl;
cout<<"/tTime: "<<GetTickCount()-t<<endl;
/*
for (j=1;
j<b[n-1];
j++) //输出未覆盖的差值
if(!a[j]) cout<<j<<' ';
cout<<endl;
*/
//d[n-1]=b[n-1];
found=true;
}
main()
{
int i,j,k,x,y,m,s,yi[36],xj,xx;
cout<<"n="<<n<<" max=";
cin>>b[n-1];
found = false;
t=GetTickCount();
m=n/2;
j=n-1;
for (k=0;
k<n;
k++) c[k]=d[k];
c[m]=(b[n-1]+1)/2+1;
for (k=m+1;k<n-1;k++) if (c[k]-c[m]<c[k-m]-1) c[k]=c[m]+c[k-m]-1;
for (i=b[n-1];
i;
i--) a=false;
LB1: //找下一个位置
j--;
if (j<0) {
FoundOne();
for (i=n-1;
i>=0;
i--) {yi-=b[0];b-=b[0];
}
for (k=0;
k<n;
k++) c[k]=d[k];
c[m]=(b[n-1]+1)/2+1;
for (k=m+1;k<n-1;k++) if (c[k]-c[m]<c[k-m]-1) c[k]=c[m]+c[k-m]-1;
goto LB4;
}
if (j<=m){
for(i=1,y=1,k=j;k;i++)
if (a==false) {
y+=i;
k--;
}
for(;a;i++);
if (y+i>b[j+1]) goto LB4;
#if n%2==0
if (j==m-1 &&
y<b[n-1]-b[m]+2) y=b[n-1]-b[m]+2;//当n为偶数时
#endif
if (y<c[j]) y=c[j];
} else
y=c[j];
yi[j]=y;
b[j]=b[j+1];
LB2: //为b[j]选择一个合适的数
y=yi[j];
x=b[j];
do
{
do
{
x--;
}while (a[b[j+1]-x]&&x>y);
for (k=j+1;
k<n &&
!a[b[k]-x];
k++);
}while (k<n &&
x>=y);
if (x>=y){//可行解
b[j]=x;
for (k=j+1;
k<n;
k++) a[b[k]-x]=true;
//mark
goto LB1;
}
else
if (j<n-2) {
LB4: //回溯
j++;
x=b[j];
for (k=j+1;
k<n;
k++) a[b[k]-x]=false;
//unmark
goto LB2;
}
LB3: //搜索完
cout<<"/tTime: "<<GetTickCount()-t<<endl;
cin>>i;
}

jsxjd · 2002-10-14

我也做了一个算法，但存在效率问题。以下是解的过程：
02-10-14 1:44:18
n= 3 >> 1 2 4
n= 3 >> 1 3 4
02-10-14 1:44:18
n= 4 >> 1 2 5 7
n= 4 >> 1 3 6 7
02-10-14 1:44:18
n= 5 >> 1 2 5 10 12
n= 5 >> 1 3 8 11 12
02-10-14 1:44:18
n= 6 >> 1 2 5 11 13 18
n= 6 >> 1 6 8 14 17 18
02-10-14 1:44:19
n= 7 >> 1 3 4 11 17 22 26
n= 7 >> 1 5 10 16 23 24 26
02-10-14 1:44:20
n= 8 >> 1 2 5 10 16 23 33 35
n= 8 >> 1 3 13 20 26 31 34 35
02-10-14 1:44:27
n= 9 >> 1 2 6 13 26 28 36 42 45
n= 9 >> 1 4 10 18 20 33 40 44 45
02-10-14 1:46:12

DarwinZhang · 2002-10-14

to gofor:我没仔细看你的帖子，不过我认为如果要想求到更好的办法，
应该先明确一下概念，我自己总结了几个概念，希望您能把我遗漏的东西补充一下：
1.假设有 N个数的递增整数序列a1,a2,a3,....an,其第一个数为1,且序列中任意两个整数的差均不相同，
则称这个整数序列为 "合数"
2.合数的子集也仍然是合数
3.an+1-a1,an+1-a2,....,an+1-a(n-1),1也是合数；用一一对应可证明
4.合数的最大元素的最小值 min(an)有如下性质：
2^(n-1)>=min(an)>=(n-1)*n/2+1
证明：
应为有Cn2个不同的差，所以 min(an)>=1+2+3+...+(n-1) +1即 min(an)>=(n-1)*n/2 +1
另外，序列 1,2,4,8,16,.....一定是合数，所以 an<=2^(n-1)
根据2,4两条性质，取一个ai,对于两个集合 a1,..ai 和 ai,a(i+1),...an应当也是合数，
可以获得一些约束条件：
a(i)>=i*(i-1)/2 +1
an-(n-i+1)*(n-i)/2 -1>= a(i)
......

DarwinZhang · 2002-10-14

我现在想为什么不能够达到(n-1)*n/2+1的底限，
希望那位高手可以指点一二。

gofor · 2002-10-14

to DarwinZhang:
　　我不赞成用“合数”来命名，极易误会，不妨称“解序列”。
　　一个很重要的性质：如前所述，由于对偶性，若n=2k+1,则a[k+1]-a[1]<a[n]-a[k+1]；
若n=2k,则a[k]-a[1]<a[n]-a[k+1]。
　　为了尽快推进，前面辛苦得来的结果，必须加以利用。
　　由于n个数差，有C（n,2)种，即n(n-1)/2。下限由此得之。
　　大家加油！

gofor · 2002-10-14

to, creation-zy, 温柔一刀：
　　我发现两个问题的有趣联系：
　　由于a+b=c+d => a-c=d-b。所以如果某个集合满足“任意两数之差不等”，则必满足
“任意两数之和不等”。但反命题并不成立。

DarwinZhang · 2002-10-14

to gofor:
性质6：如果 n=2k+1,则a[k+1]-a[1]<a[n]-a[k+1]
若n=2k,则a[k]-a[1]<a[n]-a[k+1]
然后利用性质3可以获得它相对应的一组合数。
另外，那个约束也很有力:
an-(n-i)*(n-i+1)/2 -1 >= a(i) >= (i-1)*i/2 +1
我暂时把它称为推论5 好了
我想可以令an=n*(n-1)/2+1,然后利用推论5和性质6 依次搜索a(i-1),...一直到a(2)如过无解再令an
加1，一直求到有解的an 。

DarwinZhang · 2002-10-14

不过这没有根本改变本例爆炸行的灾难，还需要另外想办法......
另外，由于时间比较紧，上面写错了许多，还请原谅。
合数会和 “素数”“合数”的“合数”相混淆，确实不太好，
但解序列也不好，没有体现出他们的性质。
改成 "集数" 怎么样？

gofor · 2002-10-14

我有两个改进的想法，请大家讨论一下可行性：
1、“部分序列”的对偶性。在我们求n个元素的序列时，先得到前i个元素的序列，则前
i个元素的对偶序列也是可行解，一次求得了两个“部分序列”，然后分两支进行试探。
这样是否加快了搜索速度呢？
2、由于“任意两数之差不等”的集合，必然有“任意两数之和不等”，能否利用这一点
增强约束条件呢？

DarwinZhang · 2002-10-15

我已经明了为什么不能到达(n-1)*n/2+1的低限，现在我已经证明，
Min(an) >＝ (n-1)*n/2 + [n/5] 。其中 []是取整数函数。
证明比较多，大约有好几百字，其原理是：
任意有5个元素的集数一定会造成冗余，即使一个差数无法使用。
我还是发现这个冗余度一定会随着 n 的增加而增加，但它的规律我还没有发现。

一个来自实践的算法难题(300分)

gofor

Unregistered / Unconfirmed

creation-zy

Unregistered / Unconfirmed

rustle

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

creation-zy

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

温柔一刀

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

温柔一刀

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

jsxjd

Unregistered / Unconfirmed

DarwinZhang

Unregistered / Unconfirmed

DarwinZhang

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

DarwinZhang

Unregistered / Unconfirmed

DarwinZhang

Unregistered / Unconfirmed

gofor

Unregistered / Unconfirmed

DarwinZhang

Unregistered / Unconfirmed

Similar threads