1701007300

1701007301

1701007302

1701007303 图6-1　国际象棋盘

1701007304

1701007305 经典的解法是回溯法，但效率较低，编程较困难。现采用随机算法，效率要提高一倍多，但算法有可能失败，成功的近似概率为0.99。

1701007306

1701007307 具体的算法流程如下。

1701007308

1701007309 Step1：置k＝1，在第一行随机选择一个位置放置一个皇后，k＋＋；

1701007310

1701007311 Step2：计算k行所有可行的位置，即在这些位置放置一个皇后不会与前面已经放置的皇后相互攻击；

1701007312

1701007313 Step3：如果找不到可行的位置，则返回失败，程序结束；否则从可行的位置中随机选择一个位置放置一个皇后，k＋＋；

1701007314

1701007315 Step4：如果k＞8，则返回成功并输出八皇后放置的结果，程序结束；否则转Step2。

1701007316

1701007317 相应程序如下：

1701007318

1701007319     function ysw1_8                                      %八皇后问题       clc,clear,close all            %清屏和清除变量    warning off                       %消除警告       Q= Queens(8)                   %调用函数    end        function Q= Queens(n)    global Indexes;                   %全局变量    A=ones(n,n);                      %初始化棋盘    Indexes=zeros(1,n);               %记录皇后的位置坐标    i=1;                              %行号    j=1;                              %列号    count=0;                          %统计解的个数    while (i>0)       while j<=n          if canPlace(i,j)            %找不会攻击其他皇后的位置               A(i,j)=8;              %8代表皇后               Indexes(i)=j;               break;                 %跳出本循环          else             j=j+1;                   %探查下一个位置          end       end              if j<=n                        %如果找到合适的位置，则找下一个            i=i+1;            j=1;       else                           %如果找不到合适的位置，则回溯，退回到上一行          i=i-1;          if i~=0               j=Indexes(i);               A(i,j)=1;              %还原值               Indexes(i)=0;          %去掉保留的坐标               j=j+1;                 %从上一个皇后的后面一个位置开始找          end       end              if (Indexes(n)~=0)             %如果找到一个解           count=count+1;           disp(A);                                               %输出矩阵       end    end    disp([num2str(n),‘皇后问题解的个数为:’,num2str(count)]);      %输出解的个数    end        %子函数，判断能否放在位置（x,y）    function p=canPlace(x,y)    global Indexes;    %判断是否会攻击已放置的皇后（位于同一对角线或同一行列上）    for a=1:x-1                                                   %a为行号       b=Indexes(a);%b为已放置皇后所在列号       %      if (x-y==a-b || x+y==a+b || x==a || y==b)%判断是否位于同一对角线和同一行列上       if (x-y==a-b || x+y==a+b || y==b)%判断是否位于同一对角线和同一列上，^_^             p=0;             return;                                              %退出子函数       end    end    p=1;    end

1701007320

1701007321 运行程序，将输出92组解。在这92个解中，很多解在棋盘上有对称关系，每一个棋子都有8个对称位置，如果一个解和另外一个解所有的棋子都呈同一种对称，那么这两个解之间就是对称关系。例如，右边两个解实际上沿着垂直轴翻转，就是一个，因此不是独立的。相互间没有对称关系的解是独立解。虽然一个解可以有8个对称位置，但是有些解经过对称操作后和没有操作前是一样的。

1701007322

1701007323 在一个标准的8×8的棋盘中，92个解当中有12个解是独立的。

1701007324

1701007325 给出一种8×8棋盘的独立解如下：

1701007326

1701007327          1     1     1     1     1     1     1     8         1     1     1     8     1     1     1     1         8     1     1     1     1     1     1     1         1     1     8     1     1     1     1     1         1     1     1     1     1     8     1     1         1     8     1     1     1     1     1     1         1     1     1     1     1     1     8     1         1     1     1     1     8     1     1     1

1701007328

1701007329 不过不采用计算机推理，单凭人的按部就班的推导，工作量极其大，并且极容易出差错，辅助计算机分析，将得到问题的更多解。

1701007330

1701007331

1701007332

1701007333

1701007334 我和数学有约：趣味数学及算法解析 [:1701004221]

1701007335 我和数学有约：趣味数学及算法解析 6.2　利润如何分配

1701007336

1701007337 利润如何分配？这个问题没那么简单。

1701007338

1701007339 我们考虑一个小组完成了一个项目，从而获得一笔资金，那么如何分配资金呢？甲说：“我作为项目承担者，我做的事情最多，我应该得到更多”，乙说：“我接的项目，没有我，就没有这个钱，我应该多分点”，丙说：“我做项目，干事情也是很积极，里面的攻关任务，我贡献了很多，我应该多分点”，……反过来，这个项目资金到底该如何分配呢？

1701007340

1701007341 【问题】这个项目资金到底该如何分配呢？

1701007342

1701007343 【分析】

1701007344

1701007345 对于资金分配问题，我们先来考虑一个概念——夏普利值（Shapley）。

1701007346

1701007347

1701007348

1701007349

[ 上一页 ]  [ :1.7010073e+09 ]  [ 下一页 ]