0

  • 有 N 个孩子和有限的 T 组可区分的玩具；
  • 每个孩子都喜欢所有玩具的特定子集 T i；
  • 每个孩子都需要拥有一个确切的数字 t i <= |T i | 玩具，但仅限于孩子喜欢的玩具；
  • 有些玩具不止一个孩子喜欢。
  • 一个玩具不能由多个孩子拥有
.

可能有很多方法可以满足每个孩子对玩具的需求。

问题：给定 N、{T i }、{t i } 和一个种子 RNG，从儿童拥有的玩具的所有可能配置中，我需要选择一个均匀分布（或至少接近均匀分布）的配置，即从儿童映射到他们拥有的玩具。

生成所有可能的配置并选择第 j 个配置是行不通的——可能会有很多配置。

在下面的示例中，有 4 个孩子：红色、蓝色、绿色和黄色。红色需要拥有4个玩具，蓝色——5个，绿色——3个，黄色——3个。孩子喜欢的玩具在对应颜色的长方形里面。

渴望玩具的孩子

因此，我需要的是生成分布良好的算法大纲Map<Child, Set<Toy>>，或者任何有助于阅读以解决问题的链接。

4

1 回答 1

1

准备一个二分图，如下所示。对于每个孩子i，制作t_i顶点。对于每个玩具j，制作一个顶点。每当孩子i喜欢玩具j时，将 的所有i顶点连接到j的顶点。玩具给孩子的有效分配对应于该图中的完美匹配。使用您最喜欢的匹配算法（例如Hopcroft--Karp）计算一项分配，然后根据需要运行Jerrum 和 Sinclair的马尔可夫链。

于 2014-09-09T19:26:11.543 回答