t**********s
发帖数: 930 | 1 问题是这样的：
Describe a mathematical model for the following scheduling problem.
Given tasks T1, T2,…, Tn, which require times t1, t2,…,tn to complete, and
a set of constraints, each of form “Ti must be completed prior to the
start of Tj,” find the minimum time necessary to complete all tasks.
我觉得这是个有向图问题。任务是图的顶点，花费时间是边的权，constraints 就是边
的方向。再往下，就找不到线索了。谁能提示我一下？
谢谢 | D****g
发帖数: 2860 | 2 如果不能并行执行，时间加起来就完了
and
【在 t**********s 的大作中提到】
: 问题是这样的：
: Describe a mathematical model for the following scheduling problem.
: Given tasks T1, T2,…, Tn, which require times t1, t2,…,tn to complete, and
: a set of constraints, each of form “Ti must be completed prior to the
: start of Tj,” find the minimum time necessary to complete all tasks.
: 我觉得这是个有向图问题。任务是图的顶点，花费时间是边的权，constraints 就是边
: 的方向。再往下，就找不到线索了。谁能提示我一下？
: 谢谢
| k****f
发帖数: 3794 | 3 悟空你又调皮了。。。
这是数据结构的课本上的题目
【在 D****g 的大作中提到】
: 如果不能并行执行，时间加起来就完了
:
: and
| D****g
发帖数: 2860 | 4 可以并行画个DAG不就解决了嘛
【在 k****f 的大作中提到】
: 悟空你又调皮了。。。
: 这是数据结构的课本上的题目
| c*****t
发帖数: 1879 | 5 你在自学 algorithm ？基本功太弱。多做点题。
这道题其实就是先弄个 topological graph （已给）。然后就是用 greedy
的办法取时间最短的 root 。
and
【在 t**********s 的大作中提到】
: 问题是这样的：
: Describe a mathematical model for the following scheduling problem.
: Given tasks T1, T2,…, Tn, which require times t1, t2,…,tn to complete, and
: a set of constraints, each of form “Ti must be completed prior to the
: start of Tj,” find the minimum time necessary to complete all tasks.
: 我觉得这是个有向图问题。任务是图的顶点，花费时间是边的权，constraints 就是边
: 的方向。再往下，就找不到线索了。谁能提示我一下？
: 谢谢
| t**********s
发帖数: 930 | 6 到哪儿能找到这样的题和讲解呢？
topological graph=directed acyclic graph?
【在 c*****t 的大作中提到】
: 你在自学 algorithm ？基本功太弱。多做点题。
: 这道题其实就是先弄个 topological graph （已给）。然后就是用 greedy
: 的办法取时间最短的 root 。
:
: and
| c*****t
发帖数: 1879 | 7 看那本 Introduction to Algorithms 啊。
【在 t**********s 的大作中提到】
: 到哪儿能找到这样的题和讲解呢？
: topological graph=directed acyclic graph?
| k****f
发帖数: 3794 | 8 Page 550 (2nd edition)
【在 c*****t 的大作中提到】
: 看那本 Introduction to Algorithms 啊。
|
| N********n
发帖数: 8363 | 9 DFS on a DAG, the mother of all scheduling algorithms.
and
【在 t**********s 的大作中提到】
: 问题是这样的：
: Describe a mathematical model for the following scheduling problem.
: Given tasks T1, T2,…, Tn, which require times t1, t2,…,tn to complete, and
: a set of constraints, each of form “Ti must be completed prior to the
: start of Tj,” find the minimum time necessary to complete all tasks.
: 我觉得这是个有向图问题。任务是图的顶点，花费时间是边的权，constraints 就是边
: 的方向。再往下，就找不到线索了。谁能提示我一下？
: 谢谢
| m***t
发帖数: 254 | 10 为啥我觉得就是做min-spanning-tree呢？
and
【在 t**********s 的大作中提到】
: 问题是这样的：
: Describe a mathematical model for the following scheduling problem.
: Given tasks T1, T2,…, Tn, which require times t1, t2,…,tn to complete, and
: a set of constraints, each of form “Ti must be completed prior to the
: start of Tj,” find the minimum time necessary to complete all tasks.
: 我觉得这是个有向图问题。任务是图的顶点，花费时间是边的权，constraints 就是边
: 的方向。再往下，就找不到线索了。谁能提示我一下？
: 谢谢
| m***t
发帖数: 254 | 11 i was wrong, cormen 24.2...sigh.
【在 m***t 的大作中提到】
: 为啥我觉得就是做min-spanning-tree呢？
:
: and
|
|
