l*****a
发帖数: 135 | 1 请教一个算法，请看附图，如果有一个有向图，每个点代表一个任务，任务有先后关系。
我要产生一个集合K, K中的每个元素代表了一个所有任务的状态。
（比如abcd代表“abcd这四个任务完成，其他的没完成”这一状态，并且abcd是符合图
中的先后关系的。又比如没有状态af,因为根据图中的关系，不可有“af这两个任务完
成，而其他的任务没完成”这一状态。）
请问最好的算法是什么？有python的package吗？
我能想到的是写个constraint programming(CP) model，让CP solver去解决，是不是
太傻了？ | p***o
发帖数: 1252 | 2 Check closure problem on wiki. Most likely you don't need CP and
a network flow solver is good enough.
系。
【在 l*****a 的大作中提到】
: 请教一个算法，请看附图，如果有一个有向图，每个点代表一个任务，任务有先后关系。
: 我要产生一个集合K, K中的每个元素代表了一个所有任务的状态。
: （比如abcd代表“abcd这四个任务完成，其他的没完成”这一状态，并且abcd是符合图
: 中的先后关系的。又比如没有状态af,因为根据图中的关系，不可有“af这两个任务完
: 成，而其他的任务没完成”这一状态。）
: 请问最好的算法是什么？有python的package吗？
: 我能想到的是写个constraint programming(CP) model，让CP solver去解决，是不是
: 太傻了？
| h*******u
发帖数: 15326 | 3 你这个没定义清楚。比如a和b无关，ab是不是等价ba？在K里面你想怎么处理？
系。
【在 l*****a 的大作中提到】
: 请教一个算法，请看附图，如果有一个有向图，每个点代表一个任务，任务有先后关系。
: 我要产生一个集合K, K中的每个元素代表了一个所有任务的状态。
: （比如abcd代表“abcd这四个任务完成，其他的没完成”这一状态，并且abcd是符合图
: 中的先后关系的。又比如没有状态af,因为根据图中的关系，不可有“af这两个任务完
: 成，而其他的任务没完成”这一状态。）
: 请问最好的算法是什么？有python的package吗？
: 我能想到的是写个constraint programming(CP) model，让CP solver去解决，是不是
: 太傻了？
| b***e
发帖数: 1419 | 4 Seems it's just a queue construct starting from the super set of roots. For
your example, start with:
{{}|{a,b}, {a}|{b}, {b}|{a}, {a,b}|{}}
Note we use S1|S2 to denote a state where the nodes in S1 must appear and
nodes in S2 must not appear in any future extension.
Pop {}|{a,b}. You can not reach more with empty starting set, so this is it.
Pop {a}|{b}, which means a is in and b is out. This state only reaches {a,c
}|{b}, so we push that in.
Pop {b}|{a}. This state doesn't reach anywhere, so this is it.
Pop {a,b}|{}. This state reaches {a,b,c}{}, so we push it.
Pop {a,c}|{b}, which we just added. This reaches no further where.
Pop {a,b,c}|{}, this reaches the following:
- {a,b,c,d}|{e}
- {a,b,c,e}|{d}
- {a,b,c,d,e}|{}
So we push all them in the queue.
{a,b,c,d}|{e} pops and is final.
{a,b,c,e}|{d} is pops and is final.
{a,b,c,d,e}|{} pops and reaches {a,b,c,d,e,f}|{}.
{a,b,c,d,e,f}|{} pops and is final.
The queue is empty, so we are done.
So all we need is to understand what're the reachable states from S1|S2.
Here's the semantics:
From the original graph, remove all the nodes in S2 as well as any nodes
that are reachable from any nodes in S2. Let A = {all the nodes in the
remaining graphs whose upstream dependencies is a subset of S1}. Let SA be
the super set of A. Then all the reachable state from S1|S2 is:
{S1+A1|S2+A2 | A1 <- SA, A2 = A - A1}
where we use + for set union, and - for set diff.
系。
【在 l*****a 的大作中提到】
: 请教一个算法，请看附图，如果有一个有向图，每个点代表一个任务，任务有先后关系。
: 我要产生一个集合K, K中的每个元素代表了一个所有任务的状态。
: （比如abcd代表“abcd这四个任务完成，其他的没完成”这一状态，并且abcd是符合图
: 中的先后关系的。又比如没有状态af,因为根据图中的关系，不可有“af这两个任务完
: 成，而其他的任务没完成”这一状态。）
: 请问最好的算法是什么？有python的package吗？
: 我能想到的是写个constraint programming(CP) model，让CP solver去解决，是不是
: 太傻了？
| l*****a
发帖数: 135 | 5 ab == ba,代表了一个“ab两个任务都完成了”这么一个状态
【在 h*******u 的大作中提到】
: 你这个没定义清楚。比如a和b无关，ab是不是等价ba？在K里面你想怎么处理？
:
: 系。
| l*****a
发帖数: 135 | 6 thanks for replying!
For
it.
,c
【在 b***e 的大作中提到】
: Seems it's just a queue construct starting from the super set of roots. For
: your example, start with:
: {{}|{a,b}, {a}|{b}, {b}|{a}, {a,b}|{}}
: Note we use S1|S2 to denote a state where the nodes in S1 must appear and
: nodes in S2 must not appear in any future extension.
: Pop {}|{a,b}. You can not reach more with empty starting set, so this is it.
: Pop {a}|{b}, which means a is in and b is out. This state only reaches {a,c
: }|{b}, so we push that in.
: Pop {b}|{a}. This state doesn't reach anywhere, so this is it.
: Pop {a,b}|{}. This state reaches {a,b,c}{}, so we push it.
| q*c
发帖数: 9453 | 7 topological sorting.
系。
【在 l*****a 的大作中提到】
: 请教一个算法，请看附图，如果有一个有向图，每个点代表一个任务，任务有先后关系。
: 我要产生一个集合K, K中的每个元素代表了一个所有任务的状态。
: （比如abcd代表“abcd这四个任务完成，其他的没完成”这一状态，并且abcd是符合图
: 中的先后关系的。又比如没有状态af,因为根据图中的关系，不可有“af这两个任务完
: 成，而其他的任务没完成”这一状态。）
: 请问最好的算法是什么？有python的package吗？
: 我能想到的是写个constraint programming(CP) model，让CP solver去解决，是不是
: 太傻了？
|
|
