w****h
发帖数: 212 | 1 假如一个网络中，每条链路对应一个effort to eliminate that link from the
network.现在的问题是如何寻找最小的effort to block all links from a source
node to a sink node。
如何建立关于这个问题的数学模型？用线性问题LP方程求解？ |
m***i
发帖数: 86 | 2 Do you mean that you want to find the minimum cut set between the source and
the destination? |
w****h
发帖数: 212 | 3 差不多，但不完全是。
我需要屏蔽所有可能的 from source node to sink node之间的communication。
屏蔽每条链路有一个相应cost,现在需要寻找最小cost,用于屏蔽所有可能的从s到t的链
路。
and
【在 m***i 的大作中提到】
: Do you mean that you want to find the minimum cut set between the source and
: the destination?
|
m***i
发帖数: 86 | 4 What do you mean by 链路? do you mean link or path?
If you block any cut between the source and the sink, you block all the
possible communication paths between them.
【在 w****h 的大作中提到】
: 差不多，但不完全是。
: 我需要屏蔽所有可能的 from source node to sink node之间的communication。
: 屏蔽每条链路有一个相应cost,现在需要寻找最小cost,用于屏蔽所有可能的从s到t的链
: 路。
:
: and
|
w****h
发帖数: 212 | 5 链路指的是link,不是path
所以我要找any cut between s & t；但是有多种any cut，我要找最小的一个。
这个和最大流问题不一样。那是找最大，这是找最小。
【在 m***i 的大作中提到】
: What do you mean by 链路? do you mean link or path?
: If you block any cut between the source and the sink, you block all the
: possible communication paths between them.
|
m***i
发帖数: 86 | 6 Let us assume that each link has weight of c_{i}. Let C^{*}=\max{c_{i}}+1.
Next, we can change the weight of link i to c'_{i}=C^{*}=c_{i}.
Under the new set of weights, we solve for the maximum flow problem.
It is equivalent to solving the minimum flow problem in the original problem.
【在 w****h 的大作中提到】
: 链路指的是link,不是path
: 所以我要找any cut between s & t；但是有多种any cut，我要找最小的一个。
: 这个和最大流问题不一样。那是找最大，这是找最小。
|
w****h
发帖数: 212 | 7 多谢。那么这个weight c_{i}和cost_{i}有什么关系呢？
开始仅定义了每条链路的cost,也就是从网络中去掉这个链路的代价。
另外，你的c'_{i}=C^{*}=c_{i}应该写错了吧，觉得是c'_{i}=C^{*}－c_{i}
problem.
【在 m***i 的大作中提到】
: Let us assume that each link has weight of c_{i}. Let C^{*}=\max{c_{i}}+1.
: Next, we can change the weight of link i to c'_{i}=C^{*}=c_{i}.
: Under the new set of weights, we solve for the maximum flow problem.
: It is equivalent to solving the minimum flow problem in the original problem.
|
m***i
发帖数: 86 | 8
c_{i} seems to me as the effort to block that link. I donot know what is
cost_{i}.
confused about this statement.
Yes, you are right. It is a typo.
【在 w****h 的大作中提到】
: 多谢。那么这个weight c_{i}和cost_{i}有什么关系呢？
: 开始仅定义了每条链路的cost,也就是从网络中去掉这个链路的代价。
: 另外，你的c'_{i}=C^{*}=c_{i}应该写错了吧，觉得是c'_{i}=C^{*}－c_{i}
:
: problem.
|
w****h
发帖数: 212 | 9 C^{*}=\max{c_{i}}+1,为什么要加1？
总结，你的意思是，对于这个网络，首先寻找所有链路最大的effort of blocking,记
为c^{*},用这个最大c^{*}减去所有c_{i}得到各自链路的标记c，再用最大流方法求解
，所得的答案也就是本题要求的屏蔽从源到目标所有通信的最小代价问题。
【在 m***i 的大作中提到】
:
: c_{i} seems to me as the effort to block that link. I donot know what is
: cost_{i}.
: confused about this statement.
: Yes, you are right. It is a typo.
|
m***i
发帖数: 86 | 10
To avoid the possibility that some link might have zero cost. In fact, you
can use a very large number to do so.
you are right.
【在 w****h 的大作中提到】
: C^{*}=\max{c_{i}}+1,为什么要加1？
: 总结，你的意思是，对于这个网络，首先寻找所有链路最大的effort of blocking,记
: 为c^{*},用这个最大c^{*}减去所有c_{i}得到各自链路的标记c，再用最大流方法求解
: ，所得的答案也就是本题要求的屏蔽从源到目标所有通信的最小代价问题。
|
