求救一道经典算法问题

Jackal · 发表于 2003-10-15 21:35

以下是引用f_qc在2003-10-14 11:17:00的发言： 我想如果用程序实现确实不管对于多少不同方法,都是无法减少计算工作量的,对于100个不同长度,总计算量确实是相当大的.30楼的方法是先将所有的组合列在表中,然后再进行判断,计算量一点也不会少.而且从程序来看,计算量应该是刚好一倍,如果在放置所有可能时直接判断,与嵌套的计算量刚好一样
[此贴子已经被作者于2003-10-14 11:26:20编辑过]

试用了一下30楼的程序，发现资源占用太大，实际的例子就无法计算了（跟踪了一下，程序生成了一个320000元素的数组

）。其实，改变一下算法就可以占用很少的资源了。我按照人工求方案的算法，编写了VBA程序，自动根据输入的数据生成切割方法，然后用规划求解得出最后方案。可惜EXCEL的规划求解有200个的变量限制，不过我想在实际的日常应用中应该也够了。

Npb244oV.rar (12.37 KB, 下载次数: 130)

f_qc · 发表于 2003-10-16 16:14

谢谢jackal,看了你的文件,我对规划求解有了一定的认识,也知道了楼主提出的这个问题是解决此类问题的第一步.我考虑了一下,不过想的不全,用程序将整个过程实现确实很困难,我还没有想到更好的办法,我初步按常规思路做了一段程序,可以实现,但不是最优的方案.在当前的条件下,也是85根,但我知道这个算法有问题.不知你有没有更好的方案? 帖子太长了影响观看,我将程序删了,不过我不知道如何上传文件?

[此贴子已经被作者于2003-10-16 16:47:52编辑过]

wangyuwy · 发表于 2003-10-16 16:17

Jackal 的算法确有精妙之处，不过却难以理解，请Jackal 详细说说解决思路。

Jackal · 发表于 2003-10-16 17:44

以下是引用f_qc在2003-10-16 16:14:00的发言： 谢谢jackal,看了你的文件,我对规划求解有了一定的认识,也知道了楼主提出的这个问题是解决此类问题的第一步.我考虑了一下,不过想的不全,用程序将整个过程实现确实很困难,我还没有想到更好的办法,我初步按常规思路做了一段程序,可以实现,但不是最优的方案.在当前的条件下,也是85根,但我知道这个算法有问题.不知你有没有更好的方案? 帖子太长了影响观看,我将程序删了,不过我不知道如何上传文件?
[此贴子已经被作者于2003-10-16 16:47:52编辑过]

不要用快速回复，用每个帖子上面的回复，然后：文件上传=>浏览=>上传。我的VBA代码因为写的仓促，可读性不是很好，也没有结构化，以后有时间了再重新写一下，否则到时候连自己都可能弄不明白了。[em12]

Jackal · 发表于 2003-10-16 21:55

49秒，30721种切法。

wangyuwy · 发表于 2003-10-17 07:35

我还是希望jackal详细解释一下算法思路。请Spide注意，我给出的题目，只是一实例，实际工程中情况是复杂的，它的切法长度需要远不止几十种，而且多变。如果Spide先生对“回溯”算法比较了解或精通，也诚恳邀请你给大家上一课。

f_qc · 发表于 2003-10-17 10:15

看来这是一个最热的主题了,我每天都上来看一看.我想知道,在没有用规划求解之前,是如何解决此类问题的? 按照一般人的思维,我想应该是让每一根都是最小的余料量,但我们知道,这肯定不是最剩料的方法,但在许多情况下,这往往也是最省料的一种方案. 规划求解有法得到多组解吗?另外,如果可变单元数量超过200怎么办呢? spide :在多重循环的每一重循环的循环参数的最大值是“动态变动的”，也就是余料整除本层循环切割长度?我没明白?能否解释一下?循环确实可以节约不少工作量,我认真考虑一下,因为尺寸可以按大小顺序排列.谢谢spide 楼主的问题与初始问题确实有很大的不同,我开始也不明白,后来看了jackal的文件我才明白,他要用vba替代的是一根材料对不同尺寸的切法,然后,再用规划求解. 一高兴,就输入了这么多,手都有点累了.我干脆把程序也附上,请大家共同想一下有没有更好的办法.这个程序可以将所有的所有的根数一次输出,如果无法用规划求解倒可以直接替代一下

[此贴子已经被作者于2003-10-21 14:55:22编辑过]

Jackal · 发表于 2003-10-17 14:06

回溯算法 http://202.113.96.10/ini/arithetics/No44.htm

f_qc · 发表于 2003-10-23 11:00

以下是引用wangyuwy在2003-10-17 7:35:00的发言： 我还是希望jackal详细解释一下算法思路。请Spide注意，我给出的题目，只是一实例，实际工程中情况是复杂的，它的切法长度需要远不止几十种，而且多变。如果Spide先生对“回溯”算法比较了解或精通，也诚恳邀请你给大家上一课。

“回溯”算法看的我头都大了,这几天没怎么上网.这个问题怎么不更新了?实际工作中还有更复杂的问题,再给一个更实际的实际的实例.另外,我想知道,如果用规划求解无法处理(超过200个可变单元)怎么办呢?原先不借助此类工具怎么做呢?

goots · 发表于 2003-10-23 12:57

据我所知，商业下料（套裁表）软件一般原理，不是使用穷举法，而是使用矩阵算法。记得曾经查阅过一本小小的书——《最优化算法》，作者是日本人，对最优化有精辟的论述，有志者不妨去参考一下。在这里，本人想提醒楼上各位，线材下料套裁表是最简单的，数据运算量也相对要小，板材下料是一个二维的问题，难度更大。其实，这两个问题，在数据库领域得到了很好的解决。建议有志者用VBA操纵ACCESS来解决这类问题。（不要再去用EXCEL的规划求解了！）

		自动登录	找回密码
密码			免费注册

求救一道经典算法问题

这是一个好主意 A good idea