无法实现的优先级分配
我正在研究 gnu prolog 的分发问题。我试图根据时间条件将教师分配到几个学校科目。理想情况的代码如下所示。
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 6,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 6,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
上面的变量 X 包含所有 3 位教师及其主题，他们能够教学。 T 代表教师，1 是人的 ID，M = 数学，E = 英语，H = 历史。 科目限制意味着每门科目每周需要教授 6 个小时。 教师限制规定了他们每周可以教学的最短和最长时数。
这个例子完美地工作，因为所有的约束都是偶数，并且方程简单地工作。但我面临着教师无法满足学科限制的情况。因此，如果发生这种情况，代码根本无法工作。
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
此代码不会返回任何解决方案。答案只是“不”。
这就是为什么我将主题限制放宽为 #<而不是 #= 但这...
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #=< 6,
T1E + T2E + T3E #=< 6,
T1H + T2H + T3H #=< 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
...将导致 X = [0,0,0,0,0,0,0,0,0] ？ 所以 Prolog 只是填充了最低条件。
为了描述我需要的结果，我会让它变得更加简单。
学校科目： 数学 - 英语 - 历史 这 3 个科目中的每一个都需要每周教授 6 个小时。
老师 1 可以教授数学和英语，每周总共 3 小时 老师2可以教授英语和历史，每周总共8小时 老师 3 每周可以教数学和历史总共 2 个小时
我的第一个要求是按给定的顺序排列科目的优先顺序。我的意思是，首先需要涵盖数学。因此，如果没有足够的老师，所有可能的时间都需要用于数学。如果数学获得了尽可能多的学时，即使这意味着它仍未完全覆盖，英语也是下一个要覆盖的科目。这也是我的第二个要求，尽可能接近要求，而不只是停留在最低限度。
对于上面给定的示例，我的预期结果是： 教师 1 和教师 3 被分配到数学，因为它是第一优先科目。他们都只会达到 5 小时，而不是所需的 6 小时，但我希望它尽可能接近。所以两位老师都100%数学。从2号老师开始，将分配6个小时的英语课。这是因为它是第二个优先主题，需要 6 个小时才能完成。剩下的2个小时将成为历史。
数学：5 小时（教师 1 + 教师 3） 英语：6小时（教师2） 历史：2小时（老师2）
我读到gnu-prolog中有fd_maximize。听起来它可能可以解决我的问题，但到目前为止我还无法让它发挥作用。它总是以错误的形式解决。 有什么办法可以达到我想要的目标吗？
预先感谢大家。
i'm working on a distribution issue with gnu prolog. Im trying to distribute teachers to several school subject based on time conditions. The Code for the ideal case looks like this.
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 6,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 6,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
The Variable X above holds all 3 Teachers with their subject, they are able to teach. T stands for Teacher, 1 is an ID for the person and M = Math, E = Englisch and H = History.
The subject constraits mean, that each subject needs to be taught 6 hours a week.
Teacher constraints hold the minimum and maximum weekly hours they can teach.
This example perfectly works because all contraints are even and the equation simply works. But im facing cases where Teachers can not match the subject constraints. So if that happens, the code simply doesnt work.
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
This code will not return any solution. The response is just "no".
Thats why i loosened the subject constraints to #< instead of #= but this...
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #=< 6,
T1E + T2E + T3E #=< 6,
T1H + T2H + T3H #=< 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
...will result in X = [0,0,0,0,0,0,0,0,0] ? So Prolog is just fullfilling the minimum condition.
To describe the outcome i need i will make it even more simple.
Subjects at the school: Math - English - History
Each of these 3 subject needs to be taught 6 hours per week.
Teacher 1 can teach Math and English with a total of 3 hours per week
Teacher 2 can teach English and History with a total of 8 hours per week
Teacher 3 can teach Math and History with a total of 2 hours per week
My first requirement is to prioritize the subjects in the given order. With that i mean, Math needs to be covered first. So if there aren't enough teachers, every possible hours needs to be directed to Math. If Math received the maximum possible hours, even tho that means its still not fully covered, Englisch is the next one to cover. This is also my second requirement, to get as close to the requirement as possible, not just stop at the minimum.
For the given Example above, my expected outcome would be:
Teacher 1 and Teacher 3 are assigned to Math because its the first prioritized subject. They both will only get to 5 instead of the needed 6 hours, but i want it to get as close a possible. So both teachers 100% to Math. From teacher 2, 6 hours will be assigned to English. This is because its the second prioritized subject and it needs 6 hours to be covered. The remaining 2 hours will go into History.
Math: 5 Hours (Teacher 1 + Teacher 3)
English: 6 Hours (Teacher 2)
History: 2 Hours (Teacher 2)
I read that there is fd_maximize in gnu-prolog. It sounds like it could possibly solve my issue but i cant make it work so far. It always resolves in an error.
Is there anyway to reach my desired goal?
Thanks everyone in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对科目的初始约束意味着所有 Tij 的总和 = 3 * 6 = 18。因此对教师的约束（这意味着不同顺序的相同总和）不能小于 1。 18. 因此，您的表述为：
没有解决方案（因此 gprolog 回答为
No）。顺便说一句，约束的形式为
0 #=< T1M + T1E + T1H 是无用的：所有变量都 ≥ 0，它们的总和也≥ 0。放宽所有约束，就像在各处用
#=<替换所有 '#=' 一样显然提供了很多解决方案，第一个解决方案都是 Tij = 0。您可以使用 fd_maximize 来寻找更有趣的解决方案（见下文）。这是一个版本，其中对科目的约束保持为 6，对教师的约束放宽为 ≤ 6（如上所述，不能 < 6）。它最大化总和（并将其返回为
F）。执行给出：
有 406 个解决方案。
如果您想“平衡”分配以最小化教师之间的差异，您可以最大化所有 Tij 的最小值，如下所示：
现在只有一种解决方案：
The initial constraints on subject imply that the sum of all Tij = 3 * 6 = 18. Thus the constraints on teachers (which imply the same sum in a different order) cannot be < 18. So your formulation with:
has no solution (thus the
Noanswered by gprolog).BTW, the constraints of the form
0 #=< T1M + T1E + T1Hare useless : all variables being ≥ 0, their sum is also ≥ 0.Relaxing ALL constraints as you did replacing all '#=' by
#=<everywhere provide obviously many solutions, the first one being all Tij = 0. You can usefd_maximizeto look for more interesting solutions (see below).Here is a version where the constraints on subjects are kept to 6 and constraints on teachers are relaxed to be ≤ 6 (cannot be < 6 as explained above). It maximizes the sum (and returns it as
F).Execution gives:
There are 406 solutions.
If you want to "balance" the distribution to minimize the difference between teachers you can maximize the minimum of all Tij as follows:
Now there is only one solution:
您最初的问题没有解决方案（我们称之为过度约束问题），但您希望找到一个放松一些约束的解决方案。
首先，过度约束的问题通常比承认至少一个解决方案的问题更难解决（因为发现它没有解决方案需要对搜索空间进行详尽的探索）。
在本例中，我们可以通过在有关主题的约束中添加人工变量来缓解问题：
成为
其中 A1，A2，A3 是新的人工变量。这样做时，我们将方程 (=) 替换为不等式 (≤)，因为所有 Aj 均为正数。为了避免所有 Tij = 0 的解决方案，我们可以要求一个使用
fd_minimize最小化总和 Aj 的解决方案。我们甚至可以考虑您的系数优先级（数学为 3，英语为 2，历史为 1）。我们将这些系数称为权重。程序如下：
解决方案：
有 101 个解决方案。
Your initial problem has no solution (we call this an over-constrained problem), but you would like to find a solution relaxing some constraints.
First, an over-constrained problem is generally (much?) more difficult to tackle than a problem admitting at least one solution (because discovering it has no solution requires an exhaustive exploration of the search space).
In the present case, we can relax the problem by adding artificial variables in constraints about subjects:
become
where
A1, A2, A3are new artificial variables. Doing this, we replace equations (=) by inequations (≤) since all Aj are positive. In order to avoid a solution with all Tij = 0 we can ask a solution which minimizes the sum Aj withfd_minimize. We can even take into account your priority with coefficients (3 for Math, 2 for English, 1 for History). We call these coefficients weights.Here is the program:
Solving it:
There are 101 solutions.
我想与您分享我一直在寻找的解决方案。我希望这可以帮助任何遇到同样问题的人。
所以我在寻找两件事。尽可能接近科目要求，并对科目进行优先排序。我的一个朋友想出了一个很酷的逻辑来解决这个问题。这是我在原始帖子中编写的示例的代码。
我希望您觉得这有帮助。至少它解决了我的问题。如果我最初的问题不够明确而无法得出此解决方案，我也深表歉意。
顺便说一下，我想与大家分享我在这个过程中的另外两个见解。我不清楚这个求解器只能处理整数值。我现实生活中的数据使用十进制值。我将这个解决方案用于一所拥有 45 名教师的真实学校。在这种情况下，由于值的数量，gnu-prolog 变得非常慢（2 小时是我等待的最长时间^^）。这就是我在这个项目中停止使用 GNU-Prolog 的原因，我现在尝试在 R 中解决它。
I want to share with you the solution i was looking for. I hope this might help anyone with the same problem.
So i was looking for 2 things. Getting as close to the subject requirements as possible and use a prioritization for the subjects. A friend of mine came up with a cool logic to solve it. Here is the Code for the example i wrote in my original post.
I hope you find this helpful. At least it solved my problem. I also apologize if my initial question wasn't clear enough to lead to this solution.
By the way i want to share with you 2 more insights i had during this process. It was unclear to me that this solver can only handle integer vlaues. My real life Data was using decimal values. I used this solution for a real school which had 45 teachers. In this case, gnu-prolog becomes extremely slow because of the number of values (2 hours was the longest i have waited^^). Thats the reason i stopped using GNU-Prolog on this project and i'm now trying to solve it in R.