算法：制作一个最佳儿童棒球队满足请求

尝试写一个算法，但我不知道很多图论因此，所有我在阿森纳现在是分支定界和遗传算法。不是很健壮，但我在这里学习。算法：制作一个最佳儿童棒球队满足请求

这里是我的问题：我们有一组n个孩子放成K队，每队选手大号。每个孩子要求最多3个朋友在他们的团队中玩。每个孩子都可以保证他们的一个请求得到满足。

我想最大限度地集合队伍，这样，我们最大限度地满足要求，每宗队球员大号该限制的数量和每个孩子都有至少一个满足要求。

我应该考虑研究对什么类型的算法？我想这是图论的一些应用，每个玩家都是一个节点，每个请求都是一个边缘。但是关于我的图形知识的程度。

来源

2012-04-02 JoshDG

这是一个家庭作业问题吗？如果是，请用'homework'标记，请=） – saluce 2012-04-02 19:47:30

它不是！只是我的一个朋友跑了一个联盟..让我帮他出去。 – JoshDG 2012-04-02 20:09:37

你可以做的是按照你所描述的创建图形，然后应用Prim算法（最小生成树）来确保每个玩家的请求中至少有一个被执行，然后从末端节点开始并遍历图形来计算团队（确保你将球队分为两个请求完成的球员）

这假设不会有多个子图（即两组玩家彼此请求但没有一个来自另一个组）至少通过运行Prim，你可以缩小哪个玩家与哪些朋友配对的领域。

来源

2012-04-02 20:16:19 saluce

如果你的MST算法选择了星形结构树，会发生什么？（即一个节点连接到每个其他节点）。由于每个边的权重相等，这是一种可能性。 – ElKamina 2012-04-02 21:31:58

@ElKamina这不太可能，但我明白你的观点。我没有在我原来的答复考虑的另一件事是，边缘应定向（此玩家选择该玩家），因为一个球员可能被别人捡到，但不会有任何的他或她的选择满足。 – saluce 2012-04-02 21:39:04

我不认为这不太可能。这将取决于小片用来挑选下一个边逻辑（将如何处理平等吗？如果它按节点编号，然后这种情况是非常有可能）。无论如何，你提到的担忧也很可能？你会如何解决它？您需要找到一组连接的子图，至少有一个循环，并且所有节点都有一个输出边。 – ElKamina 2012-04-02 22:20:22

算法：制作一个最佳儿童棒球队满足请求

回答

相关问题