从经典的AOV网、AOE网想到的问题 - swgr's Blog

从经典的AOV网、AOE网想到的问题

swgr posted @ 2010年9月01日 09:34 in algorithm with tags AOV AOE , 5002 阅读

晚上煮点心吃的时候,突然想到一个问题。

----------------------我是混个陷----------------------

首先经典的工序问题的模型一般是,给出一个工程(比如做晚餐),包括工序之间的拓扑关系和每道工序所需要的时间。(比如洗米需要5min,洗锅需要3min,完成洗米、洗锅以后才能煮饭,煮饭需要30min...)

然后就可以在这个模型上做各种事了,譬如求一个可行的完成顺序(拓扑排序),或者求一个最短的完成时间(关键路径)等等。

----------------------还是混个陷----------------------

好吧,现在来说说我想到的问题。

在这个工序问题模型的基础上加入一个限制条件:同时进行的工序数不能超过m(可以理解为厨房一共有m个人在忙活)。显然,当m=1时,问题就变成了拓扑排序;当m=∞时,问题就变成了关键路径。

那么,当m不是1也不是无穷大时,如果想求工程的最短的完成时间,要如何做呢?

我还没有认真想这个问题的算法,我觉得某种类似关键路径的贪心方法可以做掉。

ACM_DIY群上有大牛无责任猜想是费用流做,不会网络流的菜鸟我表示压力很大。

----------------------就是混个陷----------------------

其实这里还涉及到一个如何把AOV网转成AOE网的问题。

以下是我无责任猜想的做法,不多说,直接上图。(鼠绘,渣技术,我自重)

AOV网转AOE网

ftiasch 说:
2010年9月01日 17:11

果断路过打酱油。

Avatar_small
swgr 说:
2010年9月01日 19:36

@ftiasch: 郭神大驾光临,寒舍蓬荜生辉...


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee