影响米学生n组，但有限制？ [英] Affect m students to n groups, but with constraints?

问题描述

我问了一下最小费用最大流量几个星期前。 Kraskevich的回答是辉煌，解决了我的问题。我实现了它和正常工作（仅适用于法国，抱歉）。 Additionaly，该算法可以处理的assignement的我的（我的> 1）项目，以每个学生。

I asked about the minimum cost maximum flow several weeks ago. Kraskevich's answer was brilliant and solved my problem. I've implemented it and it works fine (available only in French, sorry). Additionaly, the algorithm can handle the assignement of i (i > 1) projects to each student.

现在我想的东西比较困难。我想在选择添加约束。在这种情况下一个人想影响的我的（我的> 1）项目，以每一个学生，我希望能够指定哪些项目是兼容的（对方）。

Now I'm trying something more difficult. I'd like to add constraints on choices. In the case one wants to affect i (i > 1) projects to each student, I'd like to be able to specify which projects are compatible (each other).

在这种情况下有些项目是不兼容的，我想该算法返回全局最优，即影响的我的项目，以每个学生最大限度地发挥全球幸福和 repecting相容约束。

In the case some projects are not compatible, I'd like the algorithm to return the global optimum, i.e. affect i projects to each student maximizing global happiness and repecting compatibility constraints.

链接的我的（在每一个步骤和检查约束）倍，原来的方法也无济于事，因为它只会返回一个局部最优。

Chaining i times the original method (and checking constraints at each step) will not help, as it would only return a local optimum.

有关正确的图中的任何想法，一起工作？

Any idea about the correct graph to work with ?

推荐答案

不幸的是，它不是在多项式时间（除非 P = NP 或有额外的限制）

Unfortunately, it is not solvable in polynomial time(unless P = NP or there are additional constraints).

下面是从（其已知是NP完全）的最大独立集问题的多项式时间减少到这一个：

Here is a polynomial time reduction from the maximum independent set problem(which is known to be NP-complete) to this one:

给定图和若干 K ，请执行以下操作：

Given a graph G and a number k, do the following:

1. 在图中每个顶点创建一个项目，说有两个项目是不兼容的当且仅当出现在<$ C $对应的顶点之间的边缘çG 。

1. Create a project for each vertex in the graph G and say that two project are incompatible iff there is an edge between the corresponding vertices in G.

创建一个学生谁喜欢每一个项目一样（我们可以假设，幸福每一个项目给他等于 1 ）。

Create one student who likes each project equally(we can assume that the happiness each project gives to him is equal to 1).

查找使用一种算法，解决你的问题说问题，最大的幸福。让我们把它叫做 ^ h 。

Find the maximum happiness using an algorithm that solves the problem stated in your question. Let's call it h.

一组项目可以拿起当且仅当它们都是兼容的，这意味着的回升顶点形成一个独立的组（由于我们的方式构成的图）。

A set of projects can be picked iff they all are compatible, which means that the picked vertices of G form an independent set(due to the way we constructed the graph).

因此​​， ^ h 等于最大独立集的大小。

Thus, h is equal to the size of the maximum independent set.

返回 H＆GT; = K 。

这是什么在实践中意味着什么？这意味着，这是不合理的寻找一个多项式时间解决这个问题。有可以做的几件事情：

What does it mean in practice? It means that it is not reasonable to look for a polynomial time solution to this problem. There are several things that can be done:

1. 如果输入的是小的，你可以使用穷举搜索。

1. If the input is small, you can use exhaustive search.

如果不是的话，你可以用启发式和/或近似找一个比较好的解决方案（没有必要最优的，虽然）。

If it is not, you can use heuristics and/or approximations to find a relatively good solution(not necessary the optimal one, though).

这篇关于影响米学生n组，但有限制？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！