求解一最优分割算法,是不是太多的开发工具让大家不再专注于算法研究了...... (300分)

Y

yzqangel

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-16

• #21

定义一个Nx维矩阵，以数量从小到大排列
形如：N1,N1
N2,N2
N3,N3,N3
然后从[1，1]+[i,2]+[j,3]...+ [k,x]中选取最大并且不超过L的数值。然后在这个矩阵中把此排列的所有点阵删除。形成新矩阵。第归一直到矩阵点为0。然后把这些count(最大值)就是所需钢管数。
没实际编程不知道是否可以实现。

 

N

nothingknown

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #22

不知道我的理解对不对：
基本思想是：先满足最长的钢管取材，一根钢管先可长的取，然后取短一点的；
就是短的和长的可以互补，S(短)+L(长)<L,这样就可以取两者中数量多的留下，少的
去掉；
不知道说清楚了没：）
我没时间，没试过，不知道行不行：）

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #23

对
http://www.delphibbs.com/delphibbs/dispq.asp?lid=681419
的富翁来说,这是道入门级的题目.

 

N

nothingknown

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #24

对不起：），我刚才又看了看题，好象有点问题：
要求领料最少，那就是(N1*Q1+..+Nx*Qx)/L，这个值肯定是最少的了，？？？？
如果比这个值还少，那肯定不对，因为长度不等？？
最多的就应该是(Q1+..+Qx);

我觉得是不是应该是截取的次数最少，才是最省料的？？？？：）

 

D

darkiss

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #25

首先张辉明的解法是可以的，redchild可能会有意见，先让我把话说完。
让我们先来看看问题。我一开始也以为是个线性规划的问题：
目标函数为：
Min(L-(X1*N1+X2*N2+....+Xn*Nn))
约束条件为：
Xi 在区间 [0,Qi]之间的正整数

如果可以求解，递归下去就可以了。

关键是线性规划的解法无法保证Xi的限制条件，即整数条件无法满足。
所以线性规划的解法是行不通的。
那么这个问题类似于操作系统中进程调度，或者是背包问题的变形情况。
对于调度问题，属于NP问题，用图灵机来处理，只有近似最优解，没有
最优解。对管子的排序无论是从小到大还是从大到小，进行求解，只是
一个求解策略问题，都可以得到近似最优解，但是不能保证是最优。
张辉明的算法很不错了，不菜阿，我觉得。但是对于变量数目过多的情
况，应该把递归变形成循环，否则容易出现调用栈溢出。
从问题的分析和解决上看，我觉得思路上张辉明很清晰。不要说别人的
基础不好。张辉明你不菜，对自己有点信心，呵呵。

 

R

redchild

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #26

To nothingknown
>要求领料最少，那就是(N1*Q1+..+Nx*Qx)/L，这个值肯定是最少的了，？？？？
这是理想上的最佳值.最终要求是就接近这个值.
> 如果比这个值还少，那肯定不对，因为长度不等？？
> 最多的就应该是(Q1+..+Qx);

没错,就是这样.
To Darkiss
哈哈,怎会有意见,我上面的话中有意见之辞吗,我可没有说谁基础不好,是不是这句
"欢迎在校的科班生来帮忙,你们可能比我们这些在外打工的于算法方面更
有方法一些"有问题呀?我原本意思是在校生比有工作的哥们可能更有心研究算法.
我并没有说张兄的方法一定不行,问题是把所有他所得到的单个最优解如何综合起来
求最优组合以及时综合起来求最优组合的运算量问题,可惜张兄太早想放弃了!
对于这个问题,我的看法也是一个背包问题的变种与提升,其实它的子算法即单一
组合最佳值本身就是要用背包问题来实现,但我也认为不应用递规.
对于你开出的目标函数,我想修改一下:
设一批基本钢管长为L
要分割为一批长度如下的钢管
长度为N1,数量为Q1
长度为N2,数量为Q2
.................
长度为Nx,数量为Qx
N1....Nx中任意一个数不会大于L
求领取基本钢管的最佳方案(即什么样的方案领料最省)即需要的L数量LQ最小
min(L*LQ-(Q1*N1+Q2*N2+....+Qx*Nx))
约束条件为
0<Ni<=L

 

R

redchild

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #27

To LeeChange:
LeeChange兄即然当时问起NOI/IOI的题目,相信一定参加过了,在校时,我只研究过ACM
的题目,很有意思的,可惜现在没那份心了,如果原意,烦请帮个忙解决一下这个入门级的题
目,有机会交个朋友也行呀,不然我再加分
不过
可用积分: 1214
不知够不够?

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #28

你有QQ或Mail吗?

 

R

redchild

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #29

To Leechange
当然有,我的QQ是7177136 Mail是redchild123@sina.com
>>如果我把题目换一下,你看看能找到思路吗?
有一根钢管长为L.
另有一批加工的任务单,其中需要
Q1根长度为L1的钢管,
...
Qn根长度为Ln的钢管
n<=20.
问用这根长度为L的钢管来加工,怎么做能使的所剩的边角料最少.
(当然,任务单中的任务不需要全部完成)
这样的话,就成了纯粹的背包问题了,一年一度的程序员考试教材中就有完整的分析,
在校时也还有自编的完整源程序,Leechange你可能没有仔细看我们前面的讨论,前面
已实现了你提的问题,现在的问题就是如何把这些结果组合起来,因为如果只先求得单
一的最佳结果就定下这一部分而不回溯的话,就得不到最优解,而成了贪婪算法了.这
样的结果并不是我想要的.

 

R

redchild

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #30

To all:
我不仅要得到最优解,而且要考虑运算量,当数据量大时也要让速度和资源耗用量
在可接受的范围.

 

张

张辉明

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-18

• #31

其实我还是比较关注这个问题的。这不不又来看了吗！
这个问题难就难在，找到一个min(L*LQ-(Q1*N1+Q2*N2+....+Qx*Nx))
后，要回溯，继续找。但是究竟回到什么时候就算完事了？有待大家讨论呀，我现在只有
做听客的份呀！！　：P

 

A

aimingoo

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #32

OH...是这个问题呀。哈哈~~~说实在的，我对这类算法问题倒是非常感兴趣，不过这两天我
要做一个工具软件，8.4号要交工，所以确实没时间来细想。
我先看着，收藏中，过些日子来讨论~
^-^

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #33

这是个NP问题,"当数据量大时也要让速度和资源耗用量
在可接受的范围."的要求不是任何时候都能满足的.有许多类似的实际问题也不得不退而求
其次,求出较优解.在竞赛中都会给出n的取值范围,好根据他选择算法,如果n的取值范围很大,
那么题目肯定是较优解也给大部分分数的.
如果在竞赛的仓促时间中让我解此题,我会选"分枝定界法".

 

R

redchild

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #34

TO aimingoo:
哈哈,终于请到你来了,这下应该能请到更多高手来了.不急,我反正把项目中这部
分功能无限期延后了,不过,商业上虽然延后,技术上我还是挺急的!aimingoo, 你还是
先把你的正事做好.我也不想因此耽搁大家的时间!
To all
我等到着呢

 

R

redchild

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #35

To: Leechange
在测试中如果发现要求得最优解所产生的速度和资源耗用量实在无法承受,我也
会退而求其次,但我还是想找出一种求最优解的最佳方法,这本是一个老问题
了,Leechange兄不妨把你的完整思路贴上来,让大家一起研究学习.不知意下如何?

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #36

打开你的QQ.
其实在我参加NOI的那几年碰到过类似的题目,不过有两点不同.
1.原料钢管的长度不一样.
2.每切割一次有长度损耗.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #37

2002-07-19 09:31:47 只懂Delphi
你对“分枝定界”应该不陌生吧。
(通过服务器中转)
2002-07-19 09:37:28 readchild
说句心里话,已有点不知东南西北了,不妨说来,实能检回失去的记忆
2002-07-19 09:37:18 只懂Delphi
深度优先没问题吧。
2002-07-19 09:39:10 readchild
还记得点呢,不过要去看看书先,还不知能不能找到我的书,沿途扔了许多了
2002-07-19 09:38:54 只懂Delphi
大致描述一下：
2002-07-19 09:39:45 readchild
ok,等着
2002-07-19 09:39:19 只懂Delphi
先用贪心法求一可行解。
2002-07-19 09:40:49 readchild
这个思路倒是最快的,先把单个最佳解一层一层剥下了
2002-07-19 09:41:02 只懂Delphi
再进行深度优先搜索，在搜索的基础上对每一个新生成结点进行估价
2002-07-19 09:42:20 readchild
然后依据路径回溯是吗?
2002-07-19 09:41:52 只懂Delphi
如果估价大于现有的最优解则剪枝，否则继续搜索。
2002-07-19 09:43:03 只懂Delphi
如得到另一可行解，将他与当前最优解比较，若更优，则将此解保存为当前最优解，否则剪枝。
(通过服务器中转)
2002-07-19 09:43:38 只懂Delphi
搜索完毕，当前最优解即为全局最优解。
(通过服务器中转)
2002-07-19 09:45:02 只懂Delphi
如果估价函数编的好，剪枝会发生的很早，会大大减小搜索空间。
(通过服务器中转)
2002-07-19 09:46:02 readchild
能不能把你的方案用C或PASCAL的数据结构表达式发过来,发到DFW,如果有时间的话,也不急,我手上反正有个项目31号要交,还刚开始,这几天要通宵了
2002-07-19 09:47:46 readchild
大体的思路都有差不多,但方要在中间的实现,可能性能相差会非常大的
2002-07-19 09:50:53 readchild
等我闲点,我会照你的方案写一个过程上来,评估一下,但我估计以我现在的情况来讲,我要得到更详细一点的数据结构表达才能完成

 

N

nothingknown

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #38

To redchild:
知道最小值，知道要求的是与最小值最接近的数，那么：
可不可以将所有的组合都列出来，然后，进行选择：）
或者，最根本的办法：先从一些小的数进行处理，然后总结，归纳，
找出规律，再进行建模：）

 

R

redchild

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-19

• #39

问题在于运算规模和具体的实现

 

B

beyondair

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-26

• #40

研究研究