基于动态规划和图形算法，一个不错的问题 [英] A Dynamic Programming or Graph Algorithm, a Nice Questions

问题描述

代理是 N 生产者和 M 消费者之间的作品。 我日生产，产生 S_I 糖果和Ĵ日消费消耗 b_j 糖果在今年。对于每一个糖果的销售，代理获得 1 美元的回报。对于一些问题，一是严格的规则中定义一个制片人应该是销售的糖果生产商的任何它们之间的距离不大于 100 KM（千米）更大。如果我们有所有对生产者 - 消费者的列表使它们之间的距离比 100 KM，以下算法中的哪一个混日子寻找最大收益降低？ （假设 S_I 和 b_j 可能会变得非常大）。

An agent is works between n producer and m consumers. ith producer, generates s_i candy and jth consumer consumes b_j candy in this year. For each candy that sales, agent get 1 dollar payoff. For some problems, one strict rule was defined that a producer should be sales candy to any producer that the distance between them is not greater than 100 KM (kilometers). if we have list of all pairs of producer-consumer that the distance between them is lower than 100 KM, which of the following algorithm is goof for finding maximum payoffs? (suppose s_i and b_j may be becomes very large).

1) Maximal Matching

2) Dynamic Programming

3) Maximum Flow 

4) 1 , 3

这是对DS当然2013-期末考试最后一个问题。任何提示或想法？

this is a last question on 2013-Final Exam on DS course. Any hint or idea?

推荐答案

据我了解，这个问题是可以解决的作为的最大偶匹配的，然而，建模需要的图形相对于原始输入到比较大;每一个可行的边缘（S_I，b_j）介绍 S_I 的制片分区节点和 b_j 为消费者分区的每个生产节点连接到他们每个用户节点。

To my understanding, the problem can be solved as a Maximum Bipartite Matching, however the modelling requires the graph to be relatively large compared to the original input; for every feasible edge (s_i,b_j) introduce s_i nodes for the producer partition and b_j for the consumer partition and connect each producer node of the to each consumer node of them.

这个问题可以看作是最大流问题在二部图，但是，每个可行边缘的流动（S_I，b_j）从下方受制于 0 和分{S_I，b_j} 从上面，因为流量必须是非负的，但可能会超过既不是生产者还是消费者的能力。

The problem can be modelled as Maximum Flow Problem on a bipartite graph, however; the flow on each feasible edge (s_i,b_j) is constrained by 0 from below and min{s_i,b_j} from above, as the flow must be nonnegative, but may exceed neither the producer's nor the consumer's capacity.

关于通过动态Prgramming ，考虑最多二部复发关系如下图所示：匹配。让 N 和 M 表示节点的数量在第一和第二个分区，分别为。修正了一个节点 A 在第一分区;无论是 A 不匹配或匹配到它的邻国之一;在这两种情况下，每个可能性进行评估时，递归地评价一个实例，其中分区具有 N-1 和 M 或 N-1 和 M-1 节点，分别为;最好这些选择的取

Concerning a solution via Dynamic Prgramming, consider the following sketch of a recurrence relation for Maximum Bipartite Matching. Let n and m denote the number of nodes in the first and second partition, respectively. Fix a node a in the first partition; either a is not matched or matched to one of its neighbors; in either case, each possibility is evaluated, recursively evaluating an instance where the partitions have n-1 and m or n-1 and m-1 nodes, respectively; the best of these choices is taken.

要把它概括地说，显然所有建议的办法得到有效的解决方案;然而，建模为网络流似乎是最自然的。

To put it all in a nutshell, apparently all of the proposed approaches yield valid solutions; however, the modelling as network flow seems to be most natural.

这篇关于基于动态规划和图形算法，一个不错的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！