求解2处理机处理n个作业问题 ( 积分: 100 )

X

xiaoyu10

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-05-12

• #1

题目：用两台处理机A和B处理n个作业，设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要bi。对于某些i，由可能ai>=bi,对于某些j，有aj<bj。不能将一个作业
分开由两台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使
得两台机器处理完这n个作业的时间最短。
数据：
（a1,a2,a3,a4,a5,a6）=(2,5,7,10,5,2)
(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)
我做了很长时间了，在网上也查了很长时间，也不知道怎么做啊，你们有谁知道的，快告诉我啊，谢谢！

 

X

xiaoyu10

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-05-12

• #2

题目：用两台处理机A和B处理n个作业，设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要bi。对于某些i，由可能ai>=bi,对于某些j，有aj<bj。不能将一个作业
分开由两台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使
得两台机器处理完这n个作业的时间最短。
数据：
（a1,a2,a3,a4,a5,a6）=(2,5,7,10,5,2)
(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)
我做了很长时间了，在网上也查了很长时间，也不知道怎么做啊，你们有谁知道的，快告诉我啊，谢谢！

 

X

xiaoyu10

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-05-12

• #3

怎么没人回答啊，好可怜啊

 

X

xiaoyu10

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-05-12

• #4

我在这个地方找到过和我一样问题的，但是，那里的解答好象有问题，老师说用动态规划可以做的话，就应该是正确解的，我用了那种方法求出的解是16，而正确的解应该是15啊，请大虾们帮忙啊，我很想做出来，老师给了我一个方案，不过想想就知道是错的，到底该怎么做呢？？？

 

X

xiaoyu10

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-05-12

• #5

[blue][red]以下是有人解的方案，如他所说的，有时候解出来是正确的，但是有时候是错的，针对这道例题我解出来就错了，有人有不同的算法吗，难到真的是没有能解决这个问题的更好的解了吗？？？[/blue]
此问题用动态规划算法解决。
设F[j]表示在前i个任务中，将j个任务分配给A完成，将i-j个任务分配给B完成所需要的最短时间，其中A完成j个任务的时间记为Fa[j]，B完成i-j个任务的时间记为Fb[i-j]，则有

对于F[j]有如下递推式：
上式的含义为，在前i个任务中由A完成j个的最短时间等于，在前i-1个任务中由A完成j-1个、B完成i-j个、第i个任务由A完成的最短时间，和在前i-1个任务中由A完成j个，B完成i-j-1个、第i个任务由B完成的最短时间的最小值。
所以完成全部任务的最短时间T为

同时，为了记录结果，还要引入数组G，将G[j]定义如下：

G[j]的值可以记录F[j]的值是由哪个子问题得到的，由此可以得到具体的任务分配方案。

该问题是一个NP难问题，第16期给出的动态规划算法是不正确的。
NP难问题是一类这样的问题，它们一般被认为不存在多项式时间算法，即一般情况下只能用穷举的方法来解决。至今，人们已发现了几百个NP难或NP完全问题，例如子集和问题、集合划分问题、旅行商(TSP)问题、整数规划问题、0-1背包问题等等，这些问题都找不到一个快速的算法。当然，只要其中一个问题找到快速算法，其余问题也能找到快速算法。但是至今还没有人能做到。
证明一个问题是NP难问题的方法就是问题化简，也就是将一个已知的NP难问题化简为要证明的问题。如果我们能够通过调用问题B的过程来实现问题A，我们就说问题A化简成问题B，记为A ∝ B。显然，如果问题A是NP难问题，那么，问题B至少与问题A一样难。
这里我们将把一个已知的NP难问题－集合划分问题，化简为任务安排问题，来证明任务安排问题也是NP难问题，即证明：集合划分问题 ∝ 任务安排问题。
集合划分问题可以描述如下：已知一个由n个数构成的集合X，问怎样将X划分为两个子集合X1与X2，使得X1与X2中各元素之和的最大值达到最小。也就是如何尽可能均匀地将X划分成两个子集合。设X的各个元素为xi，i＝0,1,…,n，可按如下方法将集合划分问题化简为任务安排问题：取A、B两人完成各个任务的时间都为xi，即取ai＝bi＝xi。很容易论证，集合划分问题取得最优解当且仅当这个任务划分问题取得最优解。所以，编程沙龙中的任务划分问题是NP难问题。
所以对于该问题，通常情况下多项式时间的算法是不存在的，网站上给出的动态规划算法时间复杂度为O(n2)，所以不可能保证任何情况下均得出正确答案。事实也是这样，当我们以A={1,3,5,7}和B={1,3,5,7}，来验证算法1（动态规划算法）的C＋＋程序时，其给出的最优完成时间为9。不难验证，这个例子的最优完成时间为8。
那么对于这个问题应该怎么解呢？一般来说，只能用穷举法。网站上给出的算法2虽然采用的是穷举法，但是它只能解决n是固定数值的情况。本文附带的算法是一个可以适合于任意n值的C＋＋程序，它采用的回溯递归思想，可以保证对任意大小的n都能正确运行。但是，由于算法的时间复杂度是O(2n)，所以当n>20时，程序的运行时间可能需要几小时甚至几年，这也是没办法的事情。

 

X

xiaoyu10

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-05-12

• #6

今天看来是没人回答了，我明天再来看看吧！！