在 MATLAB 中加速蛮力寻找具有特定均值的分布

Question

我有以下关于课程成绩的信息，

共有 21 名学生。
3 个已知等级是：一个 1.3、一个 1.7 和一个 1.8。
我知道有 20 名学生的成绩在 1.6 和 2.5 之间。
一名学生的成绩介于 1.0 和 1.5 之间 - 这显然是 1.3 的成绩。
课程平均分是 1.9
成绩保留到小数点后一位，例如2.2 或 2.3 但永远不会 2.25.

以下代码计算其他 18 名学生的可能成绩，其中成绩必须在上述限制范围内。

我正在使用蛮力方法来执行此操作，例如：

clear all

grades = zeros([1,21])

%certain grades
grades(1) = 1.3;
grades(2) = 1.7;
grades(3) = 1.8;

a = 1.6
b = 2.59
cnt = 0;
while 1
    grades(4:end) = round(((b - a).*rand(21 - 3,1) + a)/0.1)*0.1;
    if mean(grades) == 1.9
       cnt = cnt + 1;
       savedres(cnt,:) = grades; 
    end
end

首先我想知道没有"brute force attack"如何解决这个问题，其次我想知道上面的方法是否正确？

最后，有没有办法知道我需要多少种不同的解决方案（这样我就可以预先分配 savedres 向量）？

Answer 1

真正的蛮力方法会测试每个成绩组合，而不仅仅是随机选择成绩。

成绩必须是 1.6 <= g <= 2.5，给出 1d.p 的 10 种可能性。
[1.6, 1.7, 1.8, ..., 2.4, 2.5]
你有 18 个未知成绩

这意味着您有 10^18 种可能的成绩组合。这对蛮力来说太过分了。

减少约束:

我们知道 3 个成绩：[1.3,1.7,1.8]，21 个成绩的平均值是 1.9。所以得到剩余18个成绩的平均值（avg）：

(1/21) * (1.3 + 1.7 + 1.8 + avg*18) = 1.9
                       4.8 + avg*18 = 39.9
                                avg = 1.95

现在我们可以忘记您的一些限制，并在这些新限制下工作：

18 名学生
1.95 的平均值
成绩保留到小数点后一位

更智能的算法

我们不想强制执行此操作，您可能会运行失去耐心、RAM 或呼吸困难。您可以理论上使用

获得所有可能的组合

v = 1.6:0.1:2.5;
combs = combvec(v,v,v,v,v,v,v,v,v,v);

但这会 return 一个 1440 亿千兆字节的矩阵（8 字节 * 18 行 * 10^18 个选项），我敢打赌你无法存储它，更不用说生成所需的时间了!

你需要限制问题的范围，因为我们可以很容易地找到一个结果（9 名学生得分 1.9，9 名学生得分 2.0），并且我们可以很容易地生成不那么琐碎的结果通过将分数对更改 +0.1 和 -0.1，例如

[1.9, 1.9, 1.9, 1.9, 1.9, 1.9, 1.9, 1.9, 1.8, 2.1, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0]

正在生成而不是匹配条件

所以让我们找出一种方法来生成令人满意的结果，而不是获取所有可能的结果然后看看哪个合适！

您可以按相反的数量重复更改对（确保成绩保持在 1.6 和 2.5 的范围内）以制作任意数量的组合。在你运行无限可能之前你会感到无聊，因为有 153 对（18 选 2），你可以根据需要重复配对。

在 MATLAB 中执行此操作的简单方法：

v = [repmat(1.9,1,9), repmat(2.0,1,9)];
for ii = 1:100;
    % Choose two random indices to alter
    idx = randperm(18,2);
    % Change by +0.1 and -0.1
    v(idx) = v(idx) + [0.1, -0.1];
    % Check if still within bounds, if not then revert!
    if any(v(idx) < 1.6) || any(v(idx) > 2.5)
        v(idx) = v(idx) + [-0.1, 0.1];
    end
end
% Add in previously known grades
v = [1.3, 1.7, 1.8, v];
% Random process so result different every time, e.g.
% v = [1.3,1.7,1.8,1.8,1.8,1.7,1.9,2.1,1.7,1.9,2,1.7,2.2,2,2.3,2.4,1.8,2.4,1.8,1.9,1.7]
% Test using 
disp(mean(v)); % outputs 1.9 as desired

Answer 2

解决方案，使用整数线性规划（将所有 1 位小数乘以 10 得到整数）

N=21;
Avg=19;
Sum=N*Avg;%399;
f=ones(N,1);
Nc=1;
Aeq=zeros(Nc,N);
beq=zeros(Nc,1);
Aeq(1,:)=ones(1,N); beq(1)=Sum;
 Aeq(2,1)=1;beq(2)=13;
Aeq(3,2)=1;beq(3)=17;
Aeq(4,3)=1;beq(4)=18;
lb=16*ones(N,1); lb(1)=10;
ub=25*ones(N,1); ub(1)=16;
[x,fval,exitflag,output]  = intlinprog(f,N,[],[],Aeq,beq,lb,ub);
disp(x')

输出（除以 10 得到 1 个小数等级）：

13    17    18    16    16    16    16    16    16    16    16    16    16    25    25    25    25    25    25    25    16

Answer 3

这是可以使用递归解决的问题，并且使用 backtracking 可以大大提高（性能方面）。我只是提供两种基于递归的解决方案，一种相当于问题中出现的 "guessing" 技术，另一种是一种更智能的解决方案，它丢弃了某些会导致失败的猜测：

function gradeCandidates = q45707993(methodNum)
%% Handling inputs:
if nargin < 1
  methodNum = 2;
end
%% Definitions:
N_STUD = 21;
R_AVG = 19;
G_LIM = [16 25];

%% "Initial conditions":
grades = zeros(N_STUD,1,'uint16');
grades(1:3) = [13 17 18];

%% Solution:
switch methodNum
  case 1 % "do-while" loop:    
    gradeCandidates = nextGrade(grades,4);
    % Without backtracking or a heuristic, we just test the overall validity of the  
    %   solution, and discard it entirely if it does not meet the requirements.
    while gradeCandidates(end) < G_LIM(1) || gradeCandidates(end) > G_LIM(2)
      gradeCandidates = nextGrade(grades,4);
    end
  case 2 % using a heuristic
    gradeCandidates = nextGradeH(grades,4);
    assert(mean(gradeCandidates) == R_AVG)
end
% Prepare the output:
gradeCandidates = double(gradeCandidates)/10;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Recursive functions:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% "Trial and error":
function newGrades = nextGrade(currGrades,nextStud) 
  newGrades = currGrades;
  if nextStud == N_STUD % If this is the last grade, we get it by an equation on the mean
    newGrades(nextStud) = N_STUD*R_AVG-sum(newGrades);
  else % ...otherwise, just generate another grade and call the function again
    newGrades(nextStud) = randi(G_LIM);
    newGrades = nextGrade(newGrades, nextStud+1);
  end        
end

% "Heuristic":
function newGrades = nextGradeH(currGrades,nextStud)  
  newGrades = currGrades;
  if nextStud == N_STUD % If this is the last grade, we get it by an equation on the mean
    newGrades(nextStud) = N_STUD*R_AVG-sum(newGrades);
  else % ...otherwise, just generate another grade and call the function again
    newGrades(nextStud) = randi(G_LIM);
    % Heuristic that checks if a solution is even possible, by testing if the 
    % "remaining sum" is within G_LIM*(num_students_left)
    H_bounds = G_LIM*(N_STUD - nextStud) - (N_STUD*R_AVG - sum(newGrades));
    if H_bounds(1) <= 0 && H_bounds(2) >= 0
      newGrades = nextGradeH(newGrades, nextStud+1);
    else % regenerate the current grade
      newGrades = nextGradeH(newGrades, nextStud);
    end
  end        
end

end

我建议您阅读有关 BFS, DFS and search heuristics 的内容。

P.S。尽管我将第二种解决方案称为 "heuristic-based"，但我不确定这是否符合启发式方法，而是一种用于修剪搜索树的特定技术。

在 MATLAB 中加速蛮力寻找具有特定均值的分布

Speed up brute force for finding distribution with specific mean in MATLAB

search

matlab

combinatorics

brute-force

constraint-programming