0%

问题归约——梵塔问题

Posted on Edited on In Valine:

问题归约（problem reduction）是一种基于状态空间的问题描述与求解方法。已知问题的描述，通过一系列变换把此问题最终变为一个本原问题集合。

梵塔问题描述

  有3根柱子1、2、3柱和N个不同尺寸的圆盘，初始圆盘套在1柱上，盘的尺寸由下到上依次变小。要求将圆盘全部搬到3柱，搬运过程中要遵守下面规定：

  1. 每次只能移动一个圆盘；
  2. 大盘不能叠在小盘上面。

求解思路

  原问题可以拆分成下列子问题。（以4圆盘问题为例，圆盘从小到大分别是A、B、C、D）

  1. 移动圆盘A、B和C至柱2（3圆盘问题）
  2. 移动圆盘D到柱3（单圆盘问题）
  3. 移动圆盘A、B和C至柱3（3圆盘问题）

如此将4圆盘问题化为两个3圆盘问题和一个单圆盘问题，而3圆盘问题还可继续分解，直到化为单圆盘问题（本原问题）的集合。这便是问题归约。

Matlab代码

调用代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
clear; %清除变量

% 设置的圆盘个数n
n = 4;

if n < 1
    fprintf('圆盘个数需为正整数。\n');
else
    HannoiStep = hannoi(n, 'A', 'B', 'C'); % 解梵塔问题
    HannoiStep
    clear hannoi % 清除hannoi文件的变量
    if n <= 7
       StepAnimation(HannoiStep); % 动画演示步骤 
    else
        fprintf('圆盘太多了，没位置画，圆盘数1～7可以演示。\n');
    end
end

核心代码

hannoi.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
% n个圆盘，返回步骤矩阵
function HannoiStep = hannoi(n, A, B, C)
% 创建步骤矩阵
persistent steps;
if isempty(steps)
    steps = ones(1,n);
end

% 如果是一个圆盘，直接从A移动到C
if n == 1
    [r, ~] = size(steps);
    step = steps(r,:);
    step(1) = C-'A'+1;
    steps = [steps; step];
%     fprintf('1 号碟 : %s  ---> %s\n', A, C);
    HannoiStep = steps;
else
    % 否则，先将n-1个圆盘从A经过C移动到B
    hannoi(n-1, A, C, B);
    
    % 将第n个圆盘从A移动到C
    [r, ~] = size(steps);
    step = steps(r,:);
    step(n) = C-'A'+1;
    steps = [steps; step];
%     fprintf('%d 号碟 : %s  ---> %s\n', n, A, C);
    
    % 将n-1个圆盘从B经过A移动到C
    hannoi(n-1, B, A, C);
    HannoiStep = steps;
end
end

动画代码

StepAnimation.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
function StepAnimation(HannoiStep)
[r,~] = size(HannoiStep);
for index = 1 : 1 : r
    step = HannoiStep(index,:);
    pause_times = 1;
    DrawFrame(step)
    pause(pause_times);
    if index < r
        clf; % 清除图形
    end
end
end

function DrawFrame(step)
[~,n] = size(step); % n为圆盘数

% 初始颜色数组
coArray = [
    [0 0.4470 0.7410];
    [0.8500 0.3250 0.0980];
    [0.4660 0.6740 0.1880];
    [0.9290 0.6940 0.1250];
    [0.3010 0.7450 0.9330];
    [0.4940 0.1840 0.5560];
    [0.6350 0.0780 0.1840];
    ]; 

% 初始x坐标数组
xArray = linspace(0.5,1.5,n);

for i = 1:3
    subplot(1,3,i);
    axis([-1.5,1.5,0,3]);
    % 绘制柱  
    line([0 0],[0.5 3],'LineWidth',10,'Color',[0.3 0.3 0.3]);
    line([-1.5 1.5],[0.5 0.5],'LineWidth',10,'Color',[0.3 0.3 0.3]);
    % 绘制圆盘
    for index = n : -1 : 1
        % 如果该圆盘在这根柱上       
        if step(index) == i
            Ynum = 0;
            for j = n : -1 : index+1
                if step(j) == i
                    Ynum = Ynum+1;
                end
            end
            % 画圆盘
            line([-xArray(index) xArray(index)],[0.7+0.3*Ynum...
                0.7+0.3*Ynum],'LineWidth',30,'Color',coArray(index,:));
        end
    end
    axis off;
end
end

解答

  以4圆盘问题为例，运行上述代码，可求解。

  • 与或图

  • 步骤