d********g
发帖数: 8 | 1 要求证明是np-complete.
怎样从subset sum 问题 转化到这个问题。
Subset sum:
Given a set U of natural numbers {a1,a2....an) and a W, is there any subset
of U whose sum is equal to W.
Assume we know this problem is NP-COMPLETE
a directed graphG==(V,E),there is a weight w(e) for every edege e, which
would be positive or negative. Zero-weight-cycle problem is to decide if
there is a simple cycle in G so that sum of the edges weight is 0. | g*****a
发帖数: 7 | 2 听上去像是家庭作业
粗略想来很简单，直接告诉你答案的话你印象不深
自己再好好想想
subset
【在 d********g 的大作中提到】
: 要求证明是np-complete.
: 怎样从subset sum 问题 转化到这个问题。
: Subset sum:
: Given a set U of natural numbers {a1,a2....an) and a W, is there any subset
: of U whose sum is equal to W.
: Assume we know this problem is NP-COMPLETE
: a directed graphG==(V,E),there is a weight w(e) for every edege e, which
: would be positive or negative. Zero-weight-cycle problem is to decide if
: there is a simple cycle in G so that sum of the edges weight is 0.
| d********g
发帖数: 8 | 3 想了很久，没有得出答案。
而且马上要交了。。。。 | l****x
发帖数: 58 | |
|
