在MATLAB中加速暴力求解具有特定均值的分布

真正的蛮力方法将测试每个分数组合,而不仅仅是随机选取分数。

• 等级必须为 1.6 <= g <= 2.5
[1.6, 1.7, 1.8, ..., 2.4, 2.5]
• 你有18个未知成绩

这意味着你有10^18个可能的年级组合。这对暴力来说太多了。

:

[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

理论上 使用获取所有可能的组合

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

但这将返回1440亿GB的矩阵(8字节*18行*10^18个选项),我敢打赌你无法存储,更不用说生成所需的时间了!

你需要限制问题的范围,因为我们可以很容易地找到一个结果(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 

这是可以使用递归解决的问题,并且可以使用 backtracking . 我只是提供了两个基于递归的解决方案,一个相当于问题中出现的“猜测”技术,另一个是一个更智能的解决方案,它放弃了某些可能导致失败的猜测:

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 和 search heuristics .

虽然我将第二种解决方案称为“基于启发式”,但我不确定这是否符合启发式,而是用于修剪搜索树的某种技术。

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')

输出(1个小数级除以10):

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